树和二叉树

基本概念

树

有 $n(n\geq 0)$ 个节点的有限集，任何一棵非空树满足：

1. 有且仅有一个特定的称为 根 的结点；
2. $n>1$ 时，其余结点可以分为一些互不相交的有限集合，每个集合本身又是一棵树；

树适合表示具有层次结构的数据。

基本术语

层：根节点为第一层，根的孩子都属于第二层，孩子的孩子属于第三层，以此类推；

度：节点的孩子个数；

树的度：所有节点的最大度；

有序树和无序树：节点的孩子顺序是否可以交换；

路径和路径长度：两个节点之间的所经过的节点序列，长度则是指路径上所经过边的个数；

caution

由于树中的 有向的，从双亲指向孩子，因此路径都是从上至下的，同一双亲的两个节点不存在路径。

高度、深度：高度从下往上，深度从上往下。

森林：森林是 $m(m\geq 0)$ 棵互不相交的树的集合。

树的性质

1. 树中的节点个数等于所有节点的度数之和加一（加上根节点）；
2. 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个节点 ($i\geq 1$)；
3. 高度为 $h$ 的 $m$ 叉树至多有 $\frac{{m^h-1}}{m-1}$ 个节点；
4. 具有 $n$ 个节点的 $m$ 叉树的最小高度为 $[\log(n(m-1)+1)]$.

二叉树

tip

每个节点至多有两个子树，且子树有左右顺序之分，因此树的度为 2.

度为 2 的树至少有 3 个节点，而二叉树可以为空。

满二叉树：树的每层都含有最多的节点

二叉树的每一层最多有 $2^{i-1}, i=1,2,3\cdots$，因此一个高为 $h$ 的满二叉树有 $2^h-1$ 个节点。

双亲节点与孩子节点下标 （从 1 开始，下同）的关系为：若双亲编号为 $[i/2]$，则左孩子为 $2i$，右孩子为 $2i+1$.

完全二叉树：节点的孩子按照从左到右的顺序出现，每个节点和编号一一对应

有如下性质：

1. 叶节点只可能在最后的两层；
2. 度为 1 的节点只可能有 1 个，且一定只有左孩子；
3. 若 $i<[n/2]$，则 $i$ 为分支节点，不然则为叶节点；
4. 若 $i$ 为叶节点或只有左孩子，则编号大于 $i$ 的节点都是叶节点；
5. 若 $n$ 是奇数，则每个分支都有左孩子和有孩子；$n$ 为偶数，则编号最大的分支节点 $[n/2]$ 没有右孩子；
6. 当 $i>1$ 时，其双亲节点是 $[i/2]$，$i$ 为偶数则是左孩子；
7. 当 $2i\leq n$ 时，节点 $i$ 的左孩子编号为 $2i$，否则无左孩子；
8. 当 $2i+1\leq n$ 时，节点 $i$ 的右孩子编号为 $2i+1$，否则无右孩子；
9. 节点 $i$ 所在层次为 $[\log_{2}(i)] + 1$，则拥有 $n$ 个节点的完全二叉树高为 $[\log_{2}(n)]+1$ 或者 $[\log_{2}(n+1)]$.

有 n 个叶子节点的完全二叉树有最多有多少个节点？

这个问题需要额外考虑一种情况，即当完全二叉树的叶子节点相同时，其结构不唯一，如

二叉排序树：左子树上的所有节点的关键字都小于右子树，右子树上的所有节点的关键字都大于左子树，且左右子树都是二叉排序树；

平衡二叉树：任意节点的左右子树深度（或者说高度）不超过 1.

性质

非空二叉树上叶节点数等于度为 2 的结点数加 1，即 $n_{0}=n_{2}+1$

证明

设度为 $0,1,2$ 的节点个数为 $n_{0},n_{1},n_{2}$ 个，节点总数为 $n=n_{0}+n_{1}+n_{2}$，设分支数为 $B$

由于分支节点是度为 $1$ 或 $2$ 的节点射出（可以得到结论，对于任意一棵树，节点数为 $n$，则边数为 $n-1$），因此 $B=2n_{2}+n_{1}$，因此 $B+1=n$，化简即可。

非空二叉树上第 $k$ 层上至多有 $2^{k-1}$ 个节点（等比数列求和）

高度为 $h$ 的二叉树至多有 $2^{k}-1$ 个节点（等比数列求和）

二叉树的存储结构

顺序存储结构

使用一维数组以从上到下，从左到右的顺序存储二叉树，即将对应编号的节点存入对应的位置，因此比较适合存储完全二叉树，一般二叉树则需要使用填充。

需要注意这是节点标号从 1 开始，而数组下标从 0 开始，因此不能直接根据性质计算孩子节点下标，需要进行转换，或是直接从下标为 1 的地方开始存储。

链式存储结构没啥好说的了，需要注意的是，含有 $n$ 个节点的二叉链表中，每个节点有 2 个指针域，除了根节点，每个节点都对应了一个指针域，则共有 $n+1$ 个指针域为空（后面可以应用于线索二叉树）。

二重指针在二叉树中的应用（待续）；

二叉树遍历

遍历

二叉树的遍历分为前序、中序、后序和层次遍历，

前三种的前、中、后表示的是访问根节点的顺序（左子树总是大于右子树），层次遍历则是按照从上至下、从左至右的方式。

递归的代码比较好写，下面讨论一下非递归的实现。

非递归实现可以选用栈来实现，以中序遍历为例：

1. 从根开始出发，一路向左遍历所有左孩子，加入栈中；
2. 栈顶出栈，若其右孩子不为空，则以右孩子为根，执行上一步；否则继续执行该步骤。

待续…

caution

后序遍历是最难的。

层次遍历可以借由队列来实现——首先入队根节点，接下来执行出队，同时将该节点的左右孩子分别入队，直到队列为空。

由遍历结果构造二叉树

info

由中序和前序/后序遍历，可以唯一确定一颗二叉树，但是前序和中序遍历有多种对应二叉树。

待续…

由字符串构造二叉树

与遍历结果不同，为空的孩子一般使用一个特殊的字符表述，这样皆可以通过一个字符串构造出一个唯一的二叉树。

待续…

线索二叉树

tip

以一定规则将二叉树中的节点排列为一个线性序列，从而得到几种遍历序列，使得该序列的中的每个结点都有一个直接的前驱和后继，进而 加速查找节点前驱和后继的速度；可以说线索二叉树是利用树中的空余指针来存储额外信息，从而达到线性遍历二叉树的目的。

简单来说，就是将所有空的右指针，指向该节点在 中序遍历 中的后继，左指针改为在中序遍历中的前驱，因此为了区分指针存储的是孩子还是前驱后继，线索二叉树的节点结构有所改变：

lchild | ltag | data | rtag | rchild

额外添加了两个标志域，用于表示对应的指针域存放的是孩子还是前驱/后继（使用 $0$ 表示存放的是孩子）。

info

这里顺便证明一下一个节点数量为 $n$ 的二叉树的空指针个数：显然空指针个数等于度为 $1$ 的节点个数 $n_{1}$ 加上二倍的度为 $0$ 的节点个数 $n_{0}$，又由于非空二叉树上叶节点数等于度为 $2$ 的结点数加 $1$，即

$$n_{1}+2n_{0}=n_{1}+2n_{2}+2=n_{1}+n_{2}+n_{0}+1=n+1$$

线索化：将二叉树中的空指针改为前驱或后继，实际上是遍历一次二叉树。

线索化时需要使用两个指针分别表示当前节点和前一个节点，这样就能标记前驱和后继。

info

可以添加一个头节点，这样遍历序列的第一个节点的前驱和最后一个节点的后继都是头节点，类似于一个双向线索链表，方便对线索二叉树进行前后遍历。

线索二叉树的遍历

要求对应的遍历序列，首先需要找到第一个结点的位置，比如中序遍历的第一个结点应该是最左下的结点（不一定是叶子节点，有可能没有左孩子），在访问该节点的后继节点，直到遇到右孩子节点，由于右孩子也是一颗中序线索二叉树，因此找到其第一个节点，如此循环皆可。

树和森林

树的存储结构

双亲表示法

使用一组连续的空间来存储，每个节点除了自身的值之外，还存储了双亲在这个数组中的位置。

caution

树的顺序存储结构和二叉树的并不相同，二叉树根据完全二叉树的下标进行存储，即表示了节点的编号，又表示了二叉树中各个节点的关系。

使用链表表示时，每个节点指向双亲。

孩子表示法

将每个节点的孩子用单链表连接为一个线性结构。

孩子兄弟表示法（二叉树表示法）

使用二叉链表来表示树，节点结构为

data | firstchild | nextsibling

分别表示数据域、第一个孩子、指向下一个兄弟，并可以找到所有兄弟。

这种存储方式比较灵活，可以方便的实现二叉树的转换，易于查找节点的孩子等，但是查找双亲比较麻烦，可以额外添加一个指针指向双亲。

树、森林和二叉树的转换

可以通过二叉链表为媒介到处树与二叉树的对应关系——即给定一颗树，可以找到唯一的一颗二叉树与之对应。从物理结构上它们是相同的，只是解释不同。

tip

实际上就是将树转换为二叉树表示的格式（孩子兄弟法），二者是等价的，不过有不同的解释。

转换规则 ：每个节点左指针指向其第一个孩子，右指针指向他在树中的相邻右兄弟，称为 左孩子右兄弟.

由于根节点没有兄弟，因此其对应的二叉树没有右子树，

对应的画法上就是，在兄弟节点之间增加一条连线，除了第一个节点与双亲相连，其他节点的连接全部断开。

森林转换为二叉树：先将每棵树转换为二叉树，连接每个根即可。

二叉树转换为森林：断开右链、并对得到的右子树执行同样的操作。

树和森林的遍历

树的遍历

类似于二叉树，但是只有先根遍历（与其对应的二叉树的先序遍历相同）和后根遍历（与其对应的二叉树的中序遍历相同，因此也有一说是中根遍历），以及层次遍历。

树转换的二叉树的过程中，节点的右兄弟会转换为节点的右孩子，因此对原树的后根遍历（即先访问当前节点，再访问右兄弟，最后访问双亲节点），与对二叉树的中序遍历（先访问当前节点，再访问右孩子，而右孩子就是原先的右兄弟，最后访问双亲）。

森林有两种遍历方法：

1. 先序遍历森林，按照顺序先序遍历所有的树，与森林对应的二叉树的先序遍历相同；
2. 中序遍历森林，按照顺序中序遍历所有的树，与森林对应的二叉树的中序遍历相同。

由于树对应的二叉树的根是没有右子树的，因此形成二叉树时根的右子树是其他所有树构成的二叉树（可以递归定义），因此中序遍历还是和二叉树的中序遍历相同。

应用

哈夫曼树和哈夫曼编码

tip

使得带权路径长度最小的树被称为哈夫曼树，为左右子树编号 01，则最终叶子节点得到的编码是哈夫曼编码。

构造过程

1. 从节点集合（实际上是一个森林）中选择根权值最小的两个，构造一个新节点，权值为这两个节点权值之和，以新节点为根，构造一个 2 层二叉树，删除原来的两个节点，将新的树加入集合中；
2. 重复上述步骤直到集合中只剩一颗树。

特点

1. 初始节点都将称为叶节点，权值越小的节点距离根节点路径越长；
2. 新构造了 $n-1$ 个节点，因此哈夫曼树总节点个数为 $2n-1$；
3. 不存在度为 1 的节点；
4. 哈夫曼编码是一种前缀编码（没有一个编码是另一个编码的前缀）。

并查集

tip

一种简单的集合表示，用于处理集合合并及查询连通性问题的数据结构。它可以高效地判断两个元素是否在同一个集合中，并支持将两个 不同 的集合合并为一个集合。并查集常用于图论算法中，如最小生成树、最短路等算法的实现。

子集的表示

通常使用树或森林的 双亲表示 作为并查集的存储结构，每个子集使用一棵树表示，初始时，每个子集中通常只有一个元素，在经过一段时间的计算后，这些子集会相互合并为一些稍大的子集，子集的根为负数，表示有多少个元素（初始时为 $-1$），每个节点指向双亲的下标，如：

 0   1   2   3   4
-4  -1   0   0   0 

则表示第 0、2、3、4 是一个子集，并且 0 为根，1 号元素单独是一个子集。

子集的并

只需要将一个子集的根指向另一个子集的根即可，其孩子并不需要更新，因为查找根的时候需要判断根的值是否为负数。

判断两元素是否属于同一子集

只需要判断两元素的根是否相同即可。

相关代码

判断二叉树是否是二叉排序树

#include<limit.h>
#include<stdbool.h>
bool _isBST(PNode node, int min, int max) {
  if (!node)
    return true;

  if (node->val < min || node->val > max)
    return false;

  return _isBST(node->left, min, node->val) &&
         _isBST(node->right, node->val, max);
}

bool isBST(PNode root) { return _isBST(root, INT_MIN, INT_MAX); }

判断二叉树是否是平衡二叉树

int _isAVL(PNode node, int min, int max) {
  if (!node)
    return 0;

  if (node->val < min || node->val > max) // check whether input tree is BST.
    return -1;
  // -1 represents not a AVL or BST.

  int left_height = _isAVL(node->left, min, node->val);
  int right_height = _isAVL(node->right, node->val, max);

  if (left_height == -1 ||
      right_height == -1) // used for short-circuit, this is necessary.
    return -1;

  if (abs(left_height - right_height) >
      1) // check whether input tree is an AVL.
    return -1;

  // return the height of this tree.
  return (left_height > right_height) ? (left_height + 1) : (right_height + 1);
}

bool isAVL(PNode node) {
  int res = _isAVL(node, INT_MIN, INT_MAX);
  if (res != -1) // convert to bool manully, cause only 0 represents false
    return true;
  return false;
}

可以同时判断是否是平衡二叉树和二叉排序树，若只需要判断是否是平衡二叉树则将 max, min 相关的去掉即可。 思路以后再写。