树

树 是 $n$ 个结点的有限集合，其中：

• 最多只有一个根结点；
• 除根结点外，其余结点可分为 $m$ 个 互不相交 的有限集 $T_1, T_2, ..., T_m$，其中每个集合本身又是一棵树，称为根的 子树 。

当 $n=0$ 时，称为 空树 。

若树中结点的各子树从左至右是有次序的，则称该树为 有序树 ；否则称为 无序树 。

m 叉树 ：每个结点最多有 $m$ 个子树的树。

森林 是 $m$ 棵互不相交的树的集合。

树的属性

结点的度：结点拥有的子树的个数，度为 $0$ 的结点称为 叶子结点 ；

结点的深度：从根结点到该结点的唯一路径上的结点总数；

结点的高度：从该结点到一片树叶的最长路径上的结点总数；

树的度：树中所有结点的度的最大值；

树的深度：从根结点出发的最长路径上的结点总数。

常考性质

结点数 = 总度数 + 1（根结点）

度为 $m$ 的树中第 $i$ 层至多有 $m^{i-1}$ 个结点

高度为 $h$ 的 $m$ 叉树至多有 $m^0 + m^1 + m^2 + ... + m^{h-1}$ 个结点，即 $\frac{1 - m^h}{1- m}$ 个结点

高度为 $h$ 的 $m$ 叉树至少有 $h$ 个结点；高度为 $h$ 且度为 $m$ 的树至少有 $h+m-1$ 个结点

具有 $n$ 个结点的 $m$ 叉树的最小高度应当满足 $\frac{1 - m^{h-1}}{1- m} < n \leq \frac{1 - m^h}{1- m}$ ，即 $\lceil \log_m(n(m-1)+1) \rceil$

二叉树

二叉树 是每个结点最多有两个子树的有序树。其中，每个结点最多有两个子树，分别称为 左子树 和 右子树 ，子树也是二叉树。

满二叉树

满二叉树是高度为 $h$ 且有 $2^h - 1$ 个结点的二叉树。特点有：

• 只有最后一层有叶子结点；
• 不存在度为 $1$ 的结点；
• 若按层从左到右编号，则编号为 $i$ 的结点，其左子树编号为 $2i$ ，右子树编号为 $2i+1$ 。

完全二叉树

从上到下、从左到右依次填满结点的二叉树即为完全二叉树。特点有：

• 只有最后两层可能有叶子结点；
• 最多只有一个度为 $1$ 的结点，且该结点只有左子树；
• 与满二叉树一致，编号为 $i$ 的结点，其左子树编号为 $2i$ ，右子树编号为 $2i+1$ 。

二叉排序树

二叉排序树是一种二叉树，且具有以下性质：

• 若左子树不为空，则左子树上所有结点的值均小于根结点的值；
• 若右子树不为空，则右子树上所有结点的值均大于根结点的值；
• 左、右子树也分别为二叉排序树。

平衡二叉树

平衡二叉树是一种二叉排序树，且树上任意结点的左、右子树的深度差不超过 $1$ 。

常考性质

设二叉树中结点总数为 $n$ ，度为 $i$ 的结点数为 $n_i$ ，有：

• $n = n_0 + n_1 + n_2$
• $n_0 = n_2 + 1$
• 完全二叉树中，$n_1 = 0$ 或 $1$

二叉树的存储

顺序存储

这样的存储方式适合完全二叉树，它能保证空间充分利用。

#define MAX_SIZE 100
struct TreeNode {
    Element value;
    bool isEmpty;
}

int main() {
    TreeNode tree[MAX_SIZE];
    // ...
}

表中约定：

• 数组第一个元素可以抛弃，即从下标为 $1$ 开始存储；
• 结点 $i$ 的左孩子为 $2i$ ，右孩子为 $2i+1$ ；
• 结点 $i$ 的父结点为 $\lfloor \frac{i}{2} \rfloor$ ；
• 结点 $i$ 的深度为 $\lceil \log_2(i + 1) \rceil$ 。

对于结点数为 $n$ 的完全二叉树：

• 判断结点 $i$ 是否为叶子结点：$i \leq \lfloor \frac{n}{2} \rfloor$ ；
• 判断结点 $i$ 是否有左孩子：$2i \leq n$ ；
• 判断结点 $i$ 是否有右孩子：$2i+1 \leq n$ 。

链式存储

typedef struct TreeNode {
    Element value;
    TreeNode *left, *right;
} TreeNode, *Tree;

二叉树的遍历

• 先序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根
• 层次遍历：利用队列，从根结点开始，依次将左右孩子入队，然后出队，直到队列为空。

手算的请注意验证。

至少需要两种遍历才能确定一棵二叉树，且其中一种遍历必须是中序遍历。

线索二叉树

线索二叉树中，每个结点都有两个线索，分别指向（遍历序列中的）前驱和后继。

typedef struct TreeThreadNode {
    Element value;
    TreeNode *left, *right;
    bool leftTag, rightTag;
} TreeThreadNode, *ThreadTree;

中序线索化

void visit( ThreadTree tree, ThreadTree &pre) {
    if (!tree->left) {
        tree->left = pre;
        tree->leftTag = true;
    }
    if (pre && !pre->right) {
        pre->right = tree;
        pre->rightTag = true;
    }
    pre = tree;
}

void inThread(ThreadTree tree, ThreadTree &pre) {
    if (tree) {
        inThread(tree->left, pre);
        visit(tree, pre);
        inThread(tree->right, pre);
    }
}

void createThread(ThreadTree tree) {
    ThreadTree pre = NULL;
    if (tree) {
        inThread(tree, pre);
        // 处理最后一个结点
        pre->right = NULL;
        pre->rightTag = true;
    }
}

中序线索二叉树的遍历

先写一个函数，用于找到中序遍历中的第一个结点：

ThreadNode *first(ThreadNode *tree) {
    while (tree->leftTag == false) {
        tree = tree->left;
    }
    return tree;
}

找到一个节点在中序遍历中的后继：

ThreadNode *next(ThreadNode *tree) {
    if (tree->rightTag == false) {
        return first(tree->right);
    } else {
        return tree->right;
    }
}

反之，前驱结点的寻找与后继结点的寻找类似。

中序遍历：

void inOrder(ThreadNode *tree) {
    for (ThreadNode *p = first(tree); p != NULL; p = next(p)) {
        visit(p);
    }
}

先序线索二叉树的遍历

由于"根左右"的遍历顺序，所以找前驱会比较困难。可以引入三叉链表，即多一个 parent 指针，指向父结点。

寻找先序前继的规则如下：

• 若结点 $p$ 为根结点，则它的先序前继为 NULL ；
• 若结点 $p$ 为左孩子，则它的先序前继为它的父结点；
• 若结点 $p$ 为右孩子：
  • 若其根结点的左孩子 $q$ 为空，则它的先序前继为根结点；
  • 若其根结点的左孩子 $q$ 不为空，则它的先序前继为 $q$ 的最右后代。

后序线索二叉树的遍历

寻找后序遍历中的后继规则如下：

• 若结点 $p$ 的 rightTag 为 true，则它的后序后继为它的右孩子；
• 若结点 $p$ 的 rightTag 为 false ：
  • 若结点 $p$ 为根结点，则它的后序后继为 NULL ；
  • 若结点 $p$ 为右孩子，则它的后序后继为它的父结点；
  • 若结点 $p$ 为左孩子，且它的父结点的右孩子 $q$ 为空，则它的后序后继为它的父结点；
  • 若结点 $p$ 为左孩子，且它的父结点的右孩子 $q$ 不为空，则它的后序后继为 $q$ 的最左后代。

树的存储

不同的应用场景可以选择不同的存储方式。

双亲表示法

对于每个结点，仅需记录它的值即父节点的指针即可：

#define MAX_TREE_SIZE 100
typedef struct {
    Element value;
    int parent;
} PTNode;

typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int n;
} ParentTree;

特点：找父节点容易，找孩子节点需要遍历整个表。

双亲表示法也可以用来存储森林。

孩子表示法

对于每个结点，需要用一个链表来存储它的孩子结点：

typedef struct {
    int child;
    struct CTChildNode *next;
} *CTChildNode;

typedef struct {
    Element value;
    CTChildNode firstChild;
} CTNode;

typedef struct {
    CTNode nodes[MAX_TREE_SIZE];
    int n;
} ChildTree;

孩子表示法也可以用来存储森林，但需要额外的数组来存储每个树的根结点。

孩子兄弟表示法

typedef struct CSNode {
    Element value;
    struct CSNode *firstChild;  // 第一个孩子结点
    struct CSNode *nextSibling; // 右兄弟结点
} CSNode, *CSTree;

孩子兄弟表示法也可以用来存储森林。

树、森林与二叉树的转换

1. （森林转树）假想一个根结点，将每个森林作为其孩子；
2. 对于一个根结点，将其所有孩子用右子树连接起来；
3. 将第一个孩子结点作为该根结点的左孩子；
4. 递归进行。

树的遍历

• 先根遍历；
• 后根遍历；
• 层次遍历。

森林的遍历

• 先序遍历（先根）；
• 中序遍历（后根）。

哈夫曼树

结点的权：带有意义的数值。

结点的带权路径长度：根到该结点的路径长度与权的乘积。

树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和。

WPL: Weighted Path Length

哈夫曼树：带权路径长度最小的二叉树，也称 最优二叉树 。

性质

设一共有 n 个结点来组建哈夫曼树，则：

• 权值越小的结点离根越远；
• 哈夫曼树中没有度为 $1$ 的结点；
• 结点总数为 $2n-1$ ；
• 哈夫曼树并不唯一，但 WPL 是唯一的。

构建

1. 自底向上构建树；
2. 每次从集合中选出两个权值最小的结点，构建一个新的结点，权值为两个结点的权值之和，将新结点放入集合中；
3. 重复上述步骤，直到集合中只剩下一个结点。

哈夫曼编码

可变长度编码：不同字符的编码长度不同。

前缀编码：任何一个字符的编码都不是另一个字符编码的前缀。

构造哈夫曼编码：

1. 从根结点出发，左分支为 $0$ ，右分支为 $1$ ；
2. 每当到达一个叶子结点，就得到一个字符的编码；
3. 重复上述步骤，直到所有字符的编码都得到。

并查集

1. 建立双亲数组，每个结点初始化为 -1 ；
2. 合并两个集合时，将其中一个集合的根结点的值改为另一个集合的根结点的值；
3. 查找某个结点所在集合的根结点时，不断向上查找，直到找到根结点。

优化 1 ：小树并入大树。

1. 根结点的值为集合中元素个数的负数；
2. 合并两个集合时，将元素个数少的集合并入元素个数多的集合。注意更新根结点的值。

优化后树高不会超过 $\log_2(n) + 1$ 。

优化 2 ：路径压缩。

1. 先找到根结点；
2. 从该结点开始，将路径上的所有结点的根结点都改为根结点。