树

Posted Oct 14, 2025 Updated Oct 22, 2025

By 何翌闻

19 min read

树

树和图是最常见的非线性数据结构

树的性质总结，使用小猫神力展开领域！

以下是树（包括一般树和二叉树）的主要性质总结（仅结论）：

一、一般树的性质

节点数与边数的关系
- 一棵有 \(n\) 个节点的树有 \(n-1\) 条边。
度与节点数的关系
- 设树中度为 \(i\) 的节点数为 \(n_i\)，则总节点数： \(n = n_0 + n_1 + n_2 + \cdots + n_m\)
- 总分支数（边数）： \(n - 1 = n_1 + 2n_2 + 3n_3 + \cdots + m n_m\)
- 结合两式可得： \(n_0 = 1 + n_2 + 2n_3 + \cdots + (m-1)n_m\) 特别地，对于二叉树（m=2）：\(n_0 = n_2 + 1\)

二、二叉树的性质

第 i 层的最大节点数
- 第 \(i\) 层最多有 \(2^i\) 个节点（\(i \ge 0\)）。
高度为 h 的二叉树的最大节点数
- 最多有 \(2^{h+1} - 1\) 个节点。
叶子节点与度为 2 的节点数的关系
- 对任何非空二叉树：\(n_0 = n_2 + 1\)
具有 n 个节点的二叉树的最小高度
- 最小高度为 \(\lceil \log_2(n+1) \rceil - 1\)
- 或 \(\lfloor \log_2 n \rfloor\)
具有 n 个节点的二叉树的最大高度
- 最大高度为 \(n-1\)（退化为链表）

三、满二叉树（Full Binary Tree）

高度为 \(h\) 的满二叉树有 \(2^{h+1} - 1\) 个节点。
叶子节点全部在第 \(h\) 层。
不存在度为 1 的节点。

四、完全二叉树（Complete Binary Tree）

节点编号性质（根节点编号为 0）：
- 节点 \(i\) 的父节点编号：\(\lfloor (i-1)/2 \rfloor\)
- 节点 \(i\) 的左孩子编号：\(2i + 1\)
- 节点 \(i\) 的右孩子编号：\(2i + 2\)
高度：
- 具有 \(n\) 个节点的完全二叉树高度为 \(\lfloor \log_2 n \rfloor\)
叶子节点只出现在最后两层，且最后一层的叶子都靠左排列。

五、树、森林与二叉树的转换

树 → 二叉树：左孩子-右兄弟表示法
森林 → 二叉树：将每棵树转为二叉树，再将根节点用右链相连
二叉树 → 森林：断开根节点的右链，每棵右子树转为森林中的树

六、遍历序列性质

已知先序 + 中序 或 后序 + 中序 可唯一确定一棵二叉树。
已知先序 + 后序 不能唯一确定二叉树（除非是真二叉树）。

七、哈夫曼树（Huffman Tree）

带权路径长度（WPL）最小
没有度为 1 的节点
具有 \(n\) 个叶子节点的哈夫曼树共有 \(2n-1\) 个节点
权值越小的节点离根越远

一、树的基本概念

1. 定义

树是节点的有限集合。
可以为空，否则包含一个根节点和若干子树。

2. 术语

度：节点的子节点数。—树的度：度中找max
叶子：度为0的节点。
分支节点：度不为0的节点。
层次：根为0或1，逐层递增。
深度/高度：树中节点的最大层次。

二、二叉树

1. 定义

有限节点集合，每个节点最多有两个子树（左、右）。

2. 与一般树的区别

每个节点最多有两个子树。
子树有顺序（左、右）。

3. 性质

有 n 个节点的二叉树有 n-1 条边。
第 i 层最多有 2^i 个节点。
高度为 h 的二叉树节点数在 h+1 到 2^(h+1)-1 之间。
叶子节点数 n0 = n2 + 1（度为2的节点数）。
高度 h 满足：
\(\lceil \log_2(n+1) \rceil - 1 \leq h \leq n-1\)

4. 特殊二叉树

满二叉树：高度 h，节点数为 2^(h+1)-1。
完全二叉树：从满二叉树中删除最后 k 个节点。（叶子层删几个节点）

三、二叉树的存储表示

1. 顺序存储（数组）

适用于完全二叉树。
节点 i 的左子：2i+1，右子：2i+2，父：⌊(i-1)/2⌋。

2. 链式存储

  
class BinaryNode {
public:
    BinaryNode() { Left = Right = 0; }
    BinaryNode(Object e) { element = e; Left = Right = 0; }
    BinaryNode(Object e, BinaryNode* l, BinaryNode* r) {
        element = e; Left = l; Right = r;
    }
    Object element;
    BinaryNode* Left;
    BinaryNode* Right;
};

3. 游标表示法（模拟链表）

使用数组存储节点，leftchild 和 rightchild 存储子节点索引。

四、二叉树的操作与遍历

1. 基本操作

Create(), IsEmpty(), Root(), MakeTree(), BreakTree()

  
template<class T>
class BinaryTree {
public:
    // 构造函数和析构函数
    BinaryTree() { root = 0; };
    ~BinaryTree() { Destroy(root); };
    
    // 基本判断操作
    bool IsEmpty() const { 
        return (root) ? false : true; 
    }
    
    // 获取根节点值
    bool Root(T& x) const {
        if (root) {
            x = root->element;
            return true;
        }
        return false;
    }
    
    // 构建二叉树
    void MakeTree(const T& data, BinaryTree<T>& leftch, BinaryTree<T>& rightch);
    
    // 分解二叉树
    void BreakTree(T& data, BinaryTree<T>& leftch, BinaryTree<T>& rightch);
    
    // 遍历操作
    void PreOrder(void(*visit)(BinaryNode<T>* u)) { 
        PreOrder(visit, root); 
    }
    
    void InOrder(void(*visit)(BinaryNode<T>* u)) { 
        InOrder(visit, root); 
    }
    
    void PostOrder(void(*visit)(BinaryNode<T>* u)) { 
        PostOrder(visit, root); 
    }
    
    void LevelOrder(void(*visit)(BinaryNode<T>* u));

private:
    BinaryNode<T>* root;
    
    // 私有递归遍历方法
    void PreOrder(void(*visit)(BinaryNode<T>* u), BinaryNode<T>* t);
    void InOrder(void(*visit)(BinaryNode<T>* u), BinaryNode<T>* t);
    void PostOrder(void(*visit)(BinaryNode<T>* u), BinaryNode<T>* t);
    
    // 销毁二叉树
    void Destroy(BinaryNode<T>* t);
};

2. 遍历方式

先序：VLR
中序：LVR
后序：LRV
层序：按层次遍历

3. 递归遍历代码

只要用递归写出来的算法，都是深度优先的；而按层次遍历是广度优先

先序遍历

  
template<class T>
void PreOrder(BinaryNode<T>* t) {
    if (t) {
        visit(t);
        PreOrder(t->Left);
        PreOrder(t->Right);
    }
}

中序遍历

  
template<class T>
void InOrder(BinaryNode<T>* t) {
    if (t) {
        InOrder(t->Left);
        visit(t);
        InOrder(t->Right);
    }
}

后序遍历

  
template<class T>
void PostOrder(BinaryNode<T>* t) {
    if (t) {
        PostOrder(t->Left);
        PostOrder(t->Right);
        visit(t);
    }
}

层序遍历（使用队列）

  
template<class T>
void LevelOrder(BinaryNode<T>* t) {
    LinkedQueue<BinaryNode<T>*> Q;
    while (t) {
        visit(t);
        if (t->Left) Q.Add(t->Left);
        if (t->Right) Q.Add(t->Right);
        try { Q.Delete(t); }
        catch (OutOfBounds) { return; }
    }
}

五、非递归遍历算法

1. 中序遍历（使用栈）

  
void Inorder(BinaryNode<T>* t) {
    Stack<BinaryNode<T>*> s(10);
    BinaryNode<T>* p = t;
    for (;;) {
        while (p != NULL) {
            s.push(p);
            p = p->Left;
        }
        if (!s.IsEmpty()) {
            p = s.pop();
            cout << p->element;
            p = p->Right;
        } else return;
    }
}

2. 后序遍历（使用栈和标记）

  
struct StkNode {
    BinaryNode<T>* ptr;
    int tag;
};

void Postorder(BinaryNode<T>* t) {
    Stack<StkNode<T>> s(10);
    StkNode<T> Cnode;
    BinaryNode<T>* p = t;
    for (;;) {
        while (p != NULL) {
            Cnode.ptr = p;
            Cnode.tag = 0;
            s.push(Cnode);
            p = p->Left;
        }
        Cnode = s.pop();
        p = Cnode.ptr;
        while (Cnode.tag == 1) {
            cout << p->element;
            if (!s.IsEmpty()) {
                Cnode = s.pop();
                p = Cnode.ptr;
            } else return;
        }
        Cnode.tag = 1;
        s.push(Cnode);
        p = p->Right;
    }
}

六、二叉树的构建方法

1. 使用 `MakeTree`

  
void MakeTree(const T& data, BinaryTree<T>& leftch, BinaryTree<T>& rightch) {
    root = new BinaryNode<T>(data, leftch.root, rightch.root);
    leftch.root = rightch.root = 0;
}

2. 使用先序和中序序列

  
void CreateBT(String pres, String ins, BinaryNode<Type>*& t) {
    int inpos;
    String prestemp, instemp;
    if (pres.length() == 0) t = NULL;
    else {
        t = new BinaryNode;
        t->element = pres.ch[0];
        inpos = 0;
        while (ins.ch[inpos] != t->element) inpos++;
        prestemp = pres(1, inpos);
        instemp = ins(0, inpos - 1);
        CreateBT(prestemp, instemp, t->left);
        prestemp = pres(inpos + 1, pres.length() - 1);
        instemp = ins(inpos + 1, ins.length() - 1);
        CreateBT(prestemp, instemp, t->right);
    }
}

3. 使用广义表表示

例如：A(B(D), C(E(.,G), F(H,I)))

七、树与森林

森林是 m (m≥0) 棵互不相交的树的集合。

重要关系：

如果把一棵树的根结点删除，就得到了一个森林
反之，给一个森林加上一个根结点，森林就变成了一棵树

1. 树的存储表示

广义表、双亲表示法、左子女-右兄弟表示法

  
//双亲表示法
#define MAX_SIZE 100
typedef struct PTNode {
    char data;
    int parent; // 双亲位置下标
} PTNode;

typedef struct {
    PTNode nodes[MAX_SIZE];
    int n; // 结点数
} PTree;

  
//左子女-右兄弟表示法：最常用
typedef struct CSNode {
    char data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

2. 树转二叉树

左子女-右兄弟表示法

我们可以画个图图勒

A → B → C → D
    |    |    |
    V    V    V
    E    ∅    G
    |         |
    V         V
    F         ∅
    |
    V
    ∅

这棵树可以用这个表示法转化成：

      A
     /|\
    B C D
   / \   \
  E   F   G

也就是说：任何复杂的树都可以转换为二叉树！

3. 森林转二叉树：左孩子，右兄弟，森林相连成一家

每棵树转为二叉树，根用右链相连

具体地，我们可以看一个例子：

树1:    A      树2:    D      树3:    G
       / \             |             / \
      B   C            E            H   I
          |           / \
          F          J   K

最终转化为：

  A
 / \
B   D
 \   \
  C   G
 /   / \
F   H   I
   /
  E
 / \
J   K

转换算法的形式化描述

用递归的方式可以这样描述：

  
// 假设结点结构
typedef struct TreeNode {
    char data;
    struct TreeNode *firstchild;    // 指向第一个孩子
    struct TreeNode *nextsibling;   // 指向下一个兄弟
} TreeNode;

// 森林转二叉树的递归算法
TreeNode* ForestToBinaryTree(TreeNode* forest) {
    if (forest == NULL) return NULL;
    
    // 创建二叉树根结点
    TreeNode* binaryRoot = (TreeNode*)malloc(sizeof(TreeNode));
    binaryRoot->data = forest->data;
    
    // 左指针：指向第一个孩子转换的二叉树
    binaryRoot->firstchild = ForestToBinaryTree(forest->firstchild);
    
    // 右指针：指向下一个兄弟转换的二叉树（即森林中的下一棵树）
    binaryRoot->nextsibling = ForestToBinaryTree(forest->nextsibling);
    
    return binaryRoot;
}

4. 树的遍历

先根遍历 ↔ 二叉树的先序遍历
后根遍历 ↔ 二叉树的中序遍历

八、线索二叉树

起源于中序遍历—左子树 -> 根结点 -> 右子树，我们得到了一个node的线性序列

线索二叉树是一种对普通二叉树的改造，其规则是：

将二叉树中所有为 NULL 的左孩子指针域，改为指向其中序遍历序列中的前驱结点；将所有为 NULL 的右孩子指针域，改为指向其中序遍历序列中的后继结点。

这些指向前驱和后继的指针，被称为 “线索”。

为了区分一个指针指向的是真正的孩子还是线索，我们需要在结点结构中增加两个标志位。

1. 目的

利用空指针域指向遍历序列的前驱或后继

2. 节点结构

  
struct ThreadedNode {
    int data;
    struct ThreadedNode* left;
    struct ThreadedNode* right;
    int lTag; // 左标志位：0 表示left指向左孩子，1 表示left指向前驱线索
    int rTag; // 右标志位：0 表示right指向右孩子，1 表示right指向后继线索
};

3. 中序线索树的遍历

  
ThreadNode<Type>* First() {
    while (current->leftThread == 0) current = current->leftchild;
    return current;
}

ThreadNode<Type>* Next() {
    ThreadNode<Type>* p = current->rightchild;
    if (current->rightThread == 0)
        while (p->leftThread == 0) p = p->leftchild;
    current = p;
}

九、哈夫曼树与编码

哈夫曼树要解决的核心问题是：如何用最短的二进制编码来表示一组给定的字符（或符号），以实现数据压缩？

—贪心算法构造带权路径长度最短的二叉树

1. 哈夫曼树

eg.{5,6,2,9,7}

       29
      /  \
    13    16
   /  \   / \
  6    7 7   9
      / \
     2   5

带权路径长度最小的二叉树

2. 哈夫曼编码

用于数据压缩，前缀编码

3. 性质

没有度为 1 的结点（只有度为 0 和度为 2 的结点）。
n 个叶子结点的哈夫曼树共有 2n - 1 个结点。
权值越小的叶子到根的路径长度通常越长（但不绝对，因为要保证 WPL 最小）。
同一组权值可能构造出不同结构的哈夫曼树，但 WPL 相同。
- 原因：合并时若遇到多个相同最小权值，选择不同会导致形态不同。
树中任意非叶结点的权值一定不小于其直接子结点的权值（因为父结点权值 = 子结点权值之和）。
最初两个最小权值的结点在哈夫曼树中一定是兄弟结点（因为第一次合并的就是它们）。
哈夫曼树不一定是完全二叉树（完全二叉树要求所有层全满，除了最后一层且最后一层结点靠左）。
哈夫曼树也不一定是平衡二叉树（左右子树高度差可能大于 1）。
对于 n 个权值（n ≥ 2）且权值互不相同的情况，哈夫曼树仍然可能形态多样，不唯一。

十、广义表

  
typedef enum { ATOM, LIST } ElemTag; // ATOM=0, LIST=1
typedef struct GLNode {
    ElemTag tag; // 标志域
    union {
        char data; // 原子结点的值域
        struct {
            struct GLNode* hp; // 指向表头
            struct GLNode* tp; // 指向表尾，即兄弟结点，ATOM和LIST都要有tp指针
        } ptr;
    };
} GLNode, *GList;

1. 定义

元素可以是原子或子表的有序序列

2. 存储结构

使用联合体表示不同类型节点

3. 基本操作

head(), tail(), depth(), copy(), equal()

4. 递归算法示例

求深度

  
int GenList::depth(GenListNode* ls) {
    if (ls->tlink == NULL) return 1;
    GenListNode* temp = ls->tlink;
    int m = 0;
    while (temp != NULL) {
        if (temp->utype == LST) {
            int n = depth(temp->value.hlink);
            if (m < n) m = n;
        }
        temp = temp->tlink;
    }
    return m + 1;
}

数据结构与算法

笔记

This post is licensed under CC BY 4.0 by the author.

一、一般树的性质

二、二叉树的性质

三、满二叉树（Full Binary Tree）

四、完全二叉树（Complete Binary Tree）

五、树、森林与二叉树的转换

六、遍历序列性质

七、哈夫曼树（Huffman Tree）

一、树的基本概念

1. 定义

2. 术语

二、二叉树

1. 定义

2. 与一般树的区别

3. 性质

4. 特殊二叉树

三、二叉树的存储表示

1. 顺序存储（数组）

2. 链式存储

3. 游标表示法（模拟链表）

四、二叉树的操作与遍历

1. 基本操作

2. 遍历方式

3. 递归遍历代码

先序遍历

中序遍历

后序遍历

层序遍历（使用队列）

五、非递归遍历算法

1. 中序遍历（使用栈）

2. 后序遍历（使用栈和标记）

六、二叉树的构建方法

1. 使用 MakeTree

2. 使用先序和中序序列

3. 使用广义表表示

七、树与森林

1. 树的存储表示

2. 树转二叉树

3. 森林转二叉树：左孩子，右兄弟，森林相连成一家

转换算法的形式化描述

4. 树的遍历

八、线索二叉树

1. 目的

2. 节点结构

3. 中序线索树的遍历

九、哈夫曼树与编码

1. 哈夫曼树

2. 哈夫曼编码

3. 性质

十、广义表

1. 定义

2. 存储结构

3. 基本操作

4. 递归算法示例

求深度

Trending Tags

1. 使用 `MakeTree`