数据结构：树与二叉树

树

树是N（N大于等于0）个节点的有限集合，当N=0时，称为空树。

显然树的定义是递归的，适合表示具有层次结构的数据

• 树中一个节点的子节点的个数称为该节点的度，树中节点的最大度数称为树的度
• 度大于0的节点称为分支节点，度为0的节点称为叶子节点

树的性质

• 树中的节点数等于所有节点的度数加1
• 度为m的树中第i层最多有m^(i-1)个节点
• 高度为h的m次树至多(m^h-1)/(m-1)个节点
• 具有n个节点的m次树的最小高度为logm( n(m-1) + 1 )向上取整

总结点数=总分支数+1

二叉树

二叉树是n（n大于等于0）个节点的有序集合

• 或者为空二叉树，即n=0
• 或者由一个根节点和两个互不相交的被称为跟的左子树和右子树组成。左子和右子树又分别是一颗二叉树

二叉树是有序树，若将其左、右子树颠倒，就成为了另一颗不同的二叉树。

• 非空二叉树上叶子节点数等于度为2的节点数加1
• 非空二叉树上第K层上至多有2^(k-1)个节点（K大于等于1）
• 高度为H的二叉树至多有2^H-1个节点（H大于等于1）

存储结构

1. 顺序存储结构

二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的节点元素，即将完全二叉树上编号为i的节点元素存储在某个数组下边为i-1的分量中。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中节点的序号可以唯一地反映节点之间的逻辑关系，这样既能最大可能地节省存储空间，又可以利用数组元素的下标值确定节点在二叉树中的位置，以及节点之间的关系。但对于一般的二叉树，为了让数组下标能反映二叉树中节点之间的逻辑关系，只能添加一些并不存在的空节点让其每个节点与完全二叉树上的节点相对照，再存储到一维数组的相应分量中。然而，最坏的情况下，一个高度为H且只有H的节点的单分支却需要占据接近2^H-1个存储单元。

在树的顺数存储结构中，数组下标代表结点的编号，下标上做存储的内容指示了节点之间的关系。而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，也指示了树中各结点之间的关系。

2. 链式存储结构

由于顺序存储对空间利用率较低，因此，一般二叉树都采用链式存储结构。二叉树至少包含3个域：数据域data、左指针域lchild、右指针域rchild。

利用指针域我们便可以完美的存储非完全二叉树，如下：

在含有n个结点的二叉树链表中含有n+1个空链域

二叉树遍历

所谓二叉树的遍历是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次而且仅被访问一次。

• 先序遍历：根-左-右（ABCDEFG）
• 中序遍历：左-根-右（BADCFEG）
• 后序遍历：左-右-根（BDFGECA）
• 层次遍历：要进行层次遍历需要借助一个队列

我们首先将A加入队列， 此时对列 中只有    ⇐[A]
我们将A出弹出队列，并将它的左右子树 BC加入队列，此时队列中有 ⇐[BC] ，打印出 A
我们将B出弹出队列，它没有子树，我们不做任何操作，此时队列中有 ⇐[C] ，打印出 ABC
我们将C出弹出队列，并将它的左右子树 DE加入队列，此时队列中有 ⇐[DE] ，打印出 ABC
我们将D出弹出队列，它没有子树，我们不做任何操作，此时队列中有 ⇐[E] ，打印出 ABCD
我们将E出弹出队列，并将它的左右子树 FG加入队列，此时队列中有 ⇐[FG] ，打印出 ABCDE
我们将F出弹出队列，它没有子树，我们不做任何操作，此时队列中有 ⇐[G] ，打印出 ABCDEF
我们将G出弹出队列，它没有子树，我们不做任何操作，此时队列中有 ⇐[null] ，打印出 ABCDEFG

结论：根据轨迹我们不难发现，队列是保证层序遍历的基础，因为它保证了先加入队列的上层元素会必后加入队列的下层元素优先出队列。

前三种遍历算法中递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次，故时间复杂度O(n)。在递归遍历中，递归工作栈的栈深度恰好为树的深度，最坏的情况下二叉树是有n个结点且递归深度为n的单支树，遍历算法的空间复杂度为O(n)；最好的情况下二叉树达到平衡状态，此时空间复杂度为O(log₂n)。

由二叉树的先序遍历和中序遍历可以唯一确定一颗二叉树

由二叉树的后序遍历和中序遍历可以唯一确定一颗二叉树

由二叉树的层次遍历和中序遍历可以唯一确定一颗二叉树

满二叉树

一颗高度为h，并含有2^h-1个节点的二叉树称为满二叉树，即树中的每一层都含有最多的节点。

可以对满二叉树按层序编号：约定编号从根节点起（根节点编号为1），自上而下，自左向右。这样每个节点对应一个编号，对于编号为i的节点，如果有双亲，其双亲为i/2(向下取整)，如果有做孩子，则左孩子为2i；如果有右孩子，则右孩子为2i+1；

完全二叉树

设高度为h，有n个节点的二叉树，当且仅当其每一个节点都与高度为h的满二叉树中编号为1~n的节点一一对应时，称为完全二叉树。

• 如果有度为1的节点，只可能有一个，且该节点只有左孩子而无右孩子
• 按层序编号后，一旦出现某个节点为叶子节点或者只有左孩子，则编号大于i的节点都为叶子节点
• 若n为奇数，则每个分支节点都有左子女和右子女；若n为偶数，则编号最大的分支节点只有左子女，没有右子女，其余分支节点左、右子女都有

线索二叉树

引入线索二叉树是为了加快查找节点前驱和结点后继的速度。

线索二叉树的结点结构

通常规定：若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继结点。

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

1. 线索二叉树构造

对二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左、右指针域是否为空，若为空，将他们改为指向前驱结点或后继结点的线索。

有时为了方便，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点。并令其lchild域指向二叉树的根节点，其rchild域指针指向中序遍历时访问的最后一个结点；反之，令二叉树中序遍历中的第一个节点的lchild域的指针和最后一个结点的rchild域的指针均指向头结点，这好比为二叉树建立一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

中序线索化二叉树主要是为了访问运算符服务的，这种遍历不再需要借助栈，因为它的结点中隐含了线索二叉树的前驱和后继信息。利用线索二叉树，可以实现二叉树遍历的非递归算法。

二叉排序树

二叉排序树（BST）又称二叉查找树。二叉排序树或者是一颗空树，或者具有以下特例的非空二叉树：

• 若左子树非空，则左子树上所有结点关键字均小于根结点的关键字
• 若右子树非空，则右子树上所有结点关键字均大于根结点的关键字
• 左右子树本身也分别是一颗二叉排序树

根据二叉排序树的定义，有左子树结点值 < 根结点值 < 右子树结点值，所以二叉排序树进行中序遍历，可以得到一个递增的有序序列。

如果有相同的值，可以将该节点放在左子节点或右子节点

1. 二叉排序树构造

构造一颗二叉排序树就是依次输入数据元素，并将它们插入到二叉排序树中的适当位置上的过程。具体过程是，每读入一个元素，就建立一个新结点，若二叉排序树非空，则将新结点的值与根结点的值比较，如果小于根结点的值，则插入到左子树，否则插入到右子树中；若二叉排序树为空，则新结点作为二叉排序树的根结点。

2. 二叉排序树查找

二叉排序树的查找是从根节点开始，沿某一个分支逐层向下进行比较的过程。若二叉排序树非空，将给定值与根节点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字大于给定关键字时，在根结点的左子树中查找，否则在根结点的右子树中查找。

对于高度为H的二叉排序树，其插入和删除操作的运行时间都是O(H)。但在最坏的情况下，即构造二叉排序树输入序列是有序的，则会形成一个倾斜的单分支，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数N。

二叉排序树查找算法的平均查找长度，主要取决于树的高度，即与二叉树的形态有关。

• 如果二叉排序树是一个只有右（左）孩子的单分支（类似于有序的单链表），其平均查找长度与单链表相同，为O(n)
• 如果二叉排序树的左、右子树的高度差的绝对值不超过1，这样的二叉排序树称为平衡二叉树。它的平均查找长度达到O(log₂n)

3. 二叉排序树插入

插入节点的过程是，若原二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点关键字，则插入到左子树中，若关键字k大于根结点关键字，则插入到右子树。

插入的新结点一定是某个叶子结点

4. 二叉排序树删除

• 如果删除的节点z是叶结点，则直接删除，不会破坏二叉树的性质

(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的 父结点 parent
(3) 确定 targetNode 是 parent 的左子结点 还是右子结点
(4) 根据前面的情况来对应删除 左子结点 parent.left = null 右子结点 parent.right = null;

• 若节点z只有一颗左子树或者右子树，则直接让z的子树成为z父结点的子树，替代z的位置

(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的 父结点 parent
(3) 确定 targetNode 的子结点是左子结点还是右子结点
(4) targetNode 是 parent 的左子结点还是右子结点
(5) 如果 targetNode 有左子结点
    5.1 如果 targetNode 是 parent 的左子结点parent.left = targetNode.left;
    5.2 如果 targetNode 是 parent 的右子结点 parent.right = targetNode.left;
(6) 如果 targetNode 有右子结点
    6.1 如果 targetNode 是 parent 的左子结点 parent.left = targetNode.right;
    6.2 如果 targetNode 是 parent 的右子结点 parent.right = targetNode.right

• 若节点z有左、右两棵树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转换成了第一或第二种情况

(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的父结点 parent
(3) 从 targetNode 的右子树找到最小的结点
(4) 用一个临时变量，将最小结点的值保存 temp = 11
(5) 删除该最小结点
(6) targetNode.value = temp

平衡二叉树

为了避免树的高度增长过快，降低二叉排序树的性能，我们规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差绝对值不超过1，将这样的二叉树称为平衡二叉树，简称平衡树（AVL）。

平衡二叉树可定义为它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。

1. 平衡二叉树查找

在平衡二叉树上进行查找的过程和二叉树排序树相同，因此，在查找的过程中和给定的值进行比较的关键字个数不超过树的深度。假设以N(h)表示深度为h的平衡树中含有的最少结点数，显然，N(0) = 0、N(1) = 1、N(2) = 2，并且有N(h)=N(h-1)+N(h-2)+1，可以证明，含有n个结点的平衡二叉树的最大深度为log₂n，因此平衡二叉树的平均查找长度为O(log₂n)。

2. 平衡二叉树插入&删除

二叉排序树保证平衡的基本思想：每当在二叉排序树中插入（删除）一个节点时，首先要检查其插入路径上的节点是否因为此次操作而导致了不平衡。如果导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子绝对值大于1的节点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

• LL平衡旋转

由于在结点A的左孩子（L）的左孩子（L）上插入新结点，A的平衡因子由1增为2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右旋转代替A成为根节点，将A结点向右下旋转成为B的右子树的根节点，而B的原右子树则作为A结点的左子树。

• RR平衡旋转

由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由原来的的-1减至-2，导致以A为根的子树失去平衡，需要一次向左旋转操作。将A的右孩子B向左旋转替代A成为根节点，将A结点向左下旋转成为B的左子树的根节点，而B的原左子树则作为A结点的右子树。

• LR平衡旋转

由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根节点C向左上旋转提升到B结点的位置，然后再把孩子C结点向右上旋转提升到A结点的位置。

• RL平衡旋转

由于在A的右子树（R）的左子树（L）上插入新结点，A的平衡因子由-1减为-2，导致以A为根节点的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。

哈夫曼树

树中节点常常被赋予一个表示某种意义的数值，称为该结点的权，从树根节点到任意结点的路径长度（经过的边数）与该结点上权值的乘积称为该结点的带权路径长度。其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树。

1. 哈夫曼树的构造

1. 将这N个结点分别作为N棵仅含一个结点的二叉树。构成森林F
2. 构造一个新结点，并从F中选取两颗根节点权值最小的树作为新结点的左、右子树，并且将新结点的权重置为左、右子树上根节点的权值之和
3. 从F中删除刚才远出的两颗树，同时将新得到的树加入F中
4. 重复以上步骤，直到F中只剩下一颗树为止

2. 哈夫曼树特点

• 每个初始节点最终都会成为叶子结点，并且权重越小的结点到根节点的路径越长
• 构造过程中共新建了N-1个新结点（双分支节点），因此哈夫曼树中总结点数2N-1
• 每次构造都选择2颗树作为新结点的孩子，因此哈夫曼树中不存在读为1的结点
• 叶子节点个数是n，那么主循环的次数是n-1，循环体内要进行优先队列的出队和入队操作，每一次的时间复杂度是O(og₂n)，两者的乘积构成了哈夫曼树的时间复杂度O(nlog₂n)

3. 哈夫曼编码

哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码，由一颗哈夫曼树而来。如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

哈夫曼编码实现的两个目标：

• 任何一个字符编码，都不是其他字符编码的前缀。
• 信息编码的总长度最小。

哈夫曼编码的生成过程：

假如一段信息里只有a，b，c，d这4个字符，他们出现的次数依次是7次，5次，2次，4次，对应的权重即为出现的次数。

哈夫曼树的每一个结点包括左、右两个分支，二进制的每一位有0、1两种状态，我们可以把这两者对应起来，结点的左分支当做0，结点的右分支当做1。

这样一来，从哈夫曼树的根结点到每一个叶子结点的路径，都可以等价为一段二进制编码：

上述过程借助哈夫曼树所生成的二进制编码，就是哈夫曼编码。

• 这样生成的编码有没有前缀问题带来的歧义呢：

答案是没有歧义。因为每一个字符对应的都是哈夫曼树的叶子结点，从根结点到这些叶子结点的路径并没有包含关系，最终得到的二进制编码自然也不会是彼此的前缀。

• 这样生成的编码能保证总长度最小吗：

答案是可以保证。哈夫曼树的重要特性，就是所有叶子结点的（权重 X 路径长度）之和最小。放在信息编码的场景下，叶子结点的权重对应字符出现的频次，结点的路径长度对应字符的编码长度。所有字符的（频次 X 编码长度）之和最小，自然就说明总的编码长度最小。

WPL=7*1+5*2+(2+4)*3 = 35

0表示转向左孩子，1表示转向右孩子

树、森林

树存储结构

树的存储方式很多，既可以采用顺序存储结构，也可以采用链式存储结构。

• 双亲表示法：这种存储方式采用一组连续空间存储每个结点

该存储结构利用了每个节点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但是求结点的孩子需要遍历整个结构。

• 孩子表示法：是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，则N个结点就有N个孩子链表（叶子节点的孩子链表为空表）。

对于这种存储方式寻找子女的操作非常直接，而寻找双亲操作需要遍历N个结点中孩子链表指针域所指向的N个孩子链表

• 孩子兄弟表示法：又称为二叉树表示法，即以二叉链表作为存储结构。孩子兄弟表示法是使每个结点包括三部分：结点值、指向结点第一个孩子结点的指针和指向结点下一个兄弟结点的指针（沿此线可以找到结点的所有兄弟结点）。

优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等。

树、森林与二叉树转换

从物理结构上看，树的孩子兄弟表示法与二叉树的二叉链表表示法相同（左孩子右兄弟），即每个结点共有两个指针，分别指向结点第一个孩子和结点的下一个兄弟结点，而二叉链表中使用双指针。因此，就可以用同一存储结构的不同解释将一棵树转化为二叉树。·

树转化为二叉树的规则：每个结点左指针指向它的第一个孩子结点，右指针指向它在树中的相邻兄弟结点，可表示为“左孩子右兄弟”。

森林转化为二叉树的规则：先将森林中的每一颗树转化为二叉树，再将第一棵树的根作为转化后的二叉树的根，第一棵树的左子树作为转化后二叉树根的左子树，第二颗树作为转化后二叉树的右子树，第三课树作为转换后二叉树根的右子树的右子树，依次类推，就可以将森林转化为二叉树。

树和森林遍历

1. 树的遍历

是以某种方式访问树中的每一个结点，且仅访问一次。树的遍历操作主要有先序遍历和后序遍历。

• 先序遍历：若树非空，则先访问根结点，再按从左到右的顺序遍历根节点的每一颗子树。其访问顺序与这颗树相应二叉树的现需遍历顺序相同。
• 后序遍历：若树非空，则按从左到右的顺序遍历根节点的每一颗子树，之后再访问根节点。其访问顺序与这棵树相应二叉树的中序遍历顺序相同。

森林遍历

• 先序遍历森林：若森林非空，访问森林中第一棵树的根结点，先序遍历第一棵树中根结点的子树森林，再先序遍历除去第一颗树之后剩余的树构成的森林。
• 中序遍历森林：若森林非空，中序遍历森林中第一颗树的根结点子树森林，再访问第一棵树的根结点，最后中序遍历除去第一颗树之后的剩余的树构成的森林。