树

一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。

基本术语：

1. 树结点：包含一个数据元素及若干指向子树的分支；
2. 孩子结点：结点的子树的根称为该结点的孩子；
3. 双亲结点：B 结点是 A 结点的孩子，则 A 结点是 B 结点的双亲；
4. 兄弟结点：同一双亲的孩子结点；
5. 堂兄结点：同一层上结点；
6. 结点层次：根结点的层定义为 1；根的孩子为第二层结点，依此类推；
7. 树的高（深）度：树中最大的结点层
8. 结点的度：结点子树的个数
9. 树的度： 树中最大的结点度。
10. 叶子结点：也叫终端结点，是度为 0 的结点；
11. 分枝结点：度不为 0 的结点（非终端结点）；
12. 森林：互不相交的树集合；
13. 有序树：子树有序的树，如：家族树；
14. 无序树：不考虑子树的顺序；

二叉树

二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。注意区分：二叉树、二叉查找树 / 二叉排序树 / 二叉搜索树、二叉平衡 (查找) 树

二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。

二叉树与树是不同的，二叉树不等价于分支树最多为二的有序树。当一个结点只包含一个子节点时，对于有序树并无左右孩子之分，而对于二叉树来说依然有左右孩子之分，所以二叉树与树是两种不同的结构。

性质：

1. 在二叉树的第 i 层上至多有 2^i-1 个结点。
2. 深度为 k 的二叉树上至多含 2^k-1 个结点（k≥1）
3. 对任何一棵二叉树，若它含有 n₀ 个叶子结点、n₂ 个度为 2 的结点，则必存在关系式：n₀= n₂+1。
4. 具有 n 个结点的完全二叉树的深度为⎣log₂ n⎦+1 。
5. n 个结点的二叉树中，完全二叉树具有最小的路径长度。

6. 如果对一棵有 n 个结点的完全二叉树的结点按层序编号, 则对任一结点 i（1<=i<=n), 有：

   • 如果 i＝1，则结点 i 无双亲，是二叉树的根；如果 i>1，则其双亲的编号是 i/2(整除）。
   • 如果 2i>n，无左孩子；否则，其左孩子是结点 2i。
   • 如果 2i＋1>n，则结点 i 无右孩子；否则，其右孩子是结点 2i＋1。

二叉树的存储结构

1. 顺序存储结构：仅仅适用于满或完全二叉树，结点之间的层次关系由性质 5 确定。
2. 二叉链表法：每个节点存储左子树和右子树。三叉链表：左子树、右子树、父节点，总的指针是 n+2
3. 在有 n 个结点的二叉链表中，值为非空的链域的个数为 n-1。在有 N 个结点的二叉链表中必定有 2N 个链域。除根结点外，其余 N-1 个结点都有一个父结点。所以，一共有 N-1 个非空链域，其余 2N-(N-1)=N+1 个为空链域。
4. 二叉链存储法也叫孩子兄弟法，左指针指向左孩子，右指针指向右兄弟。而中序遍历的顺序是左孩子，根，右孩子。这种遍历顺序与存储结构不同，因此需要堆栈保存中间结果。而中序遍历检索二叉树时，由于其存储结构跟遍历顺序相符，因此不需要用堆栈。

遍历二叉树和线索二叉树

遍历二叉树：使得每一个结点均被访问一次，而且仅被访问一次。非递归的遍历实现要利用栈。

• 先序遍历 DLR：根节点 -> 左子树 -> 右子树
• 中序遍历 LDR：左子树 -> 根节点 -> 右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序
• 后续遍历 LRD：左子树 -> 右子树 -> 根节点。需要栈的支持。
• 层次遍历：用一维数组存储二叉树时, 总是以层次遍历的顺序存储结点。层次遍历应该借助队列。

线索二叉树：对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。

如何线索化？以中序遍历为例，若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。前驱就是在这一点之前走过的点，不是下一将要去往的点。

加上结点前趋后继信息（结索）的二叉树称为线索二叉树。n 个结点的线索二叉树上每个结点有 2 个指针域（指向左孩子和右孩子），总共有 2n 个指针域；一个 n 个结点的树有 n-1 条边，那么空指针域 = 2n - (n-1) = n + 1，即线索数为 n+1。指针域 tag 为 0，存放孩子指针，为 1，存放前驱 / 后继节点指针。

线索树下结点 x 的前驱与后继查找：设结点 x 相应的左（右）标志是线索标志，则 lchild(rchild) 就是前驱 (后继），否则：

• LDR–前驱：左子树中最靠右边的结点；后继：右子树中最靠左边的结点
• LRD–前驱：右子树的根，若无右子树，为左子树跟。后继：x 是根，后继是空；x 是双亲的右孩子、x 是双亲的左孩子，但双亲无右孩子，双亲是后继；x 是双亲的左孩子，双亲有右孩子，双亲右子树中最左的叶子是后继
• DLR–对称于 LRD 线索树—将 LRD 中所有左右互换，前驱与后继互换，得到 DLR 的方法。

• 为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点，约定：

  • 头结点的 lchild 域：存放线索链表的根结点指针；
  • 头结点的 rchild 域: 中序序列最后一个结点的指针；
  • 中序序列第一结点 lchild 域指向头结点;
  • 中序序列最后一个结点的 rchild 域指向头结点;

中序遍历的线索二叉树以及线索二叉树链表示意图

一棵左右子树均不空的二叉树在前序线索化后, 其中空的链域的个数是 1。前序和后续线索化后空链域个数都是 1，中序是 2。二叉树在线索化后，仍不能有效求解的问题是前序求前序先驱，后序求后序后继。

中序遍历的顺序为：左、根、右，所以对于每一非空的线索，左子树结点的后继为根结点，右子树结点的前驱为根结点，再递归的执行上面的过程，可得非空线索均指向其祖先结点。在中序线索二叉树中, 每一非空的线索均指向其祖先结点。

在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历, 此时，不需栈，也不需递归。基本步骤：

1. p=T->lchild; p 指向线索链表的根结点；

2. 若线索链表非空，循环：

   • 循环，顺着 p 左孩子指针找到最左下结点；访问之；
   • 若 p 所指结点的右孩子域为线索，p 的右孩子结点即为后继结点循环： p=p->rchild； 并访问 p 所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）
   • 一旦线索 “中断”，p 所指结点的右孩子域为右孩子指针，p=p->rchild，使 p 指向右孩子结点；

树和森林

树的存储结构：

1. 双亲表示法
2. 孩子表示法
3. 利用图表示树
4. 孩子兄弟表示法（二叉树表示法）：链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点

将树转化成二叉树：右子树一定为空

1. 加线：在兄弟之间加一连线
2. 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
3. 旋转：以树的根结点为轴心，将整树顺时针转 45°

森林转换成二叉树：

1. 将各棵树分别转换成二叉树
2. 将每棵树的根结点用线相连
3. 以第一棵树根结点为二叉树的根

树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历

哈弗曼树 / 霍夫曼树

一些概念

1. 路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
2. 路径长度：路径上的分支数目称为路径长度；
3. 树的路径长度：从根到每个结点的路径长度之和。
4. 结点的权：根据应用的需要可以给树的结点赋权值；
5. 结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；
6. 树的带权路径长度 = 树中所有叶子结点的带权路径之和；通常记作 WPL=∑w_i×l_i
7. 哈夫曼树：假设有 n 个权值 (w₁, w₂, … , w_n)，构造有 n 个叶子结点的二叉树，每个叶子结点有一个 w_i 作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。

前缀码的定义：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码，可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树，若有 n 个节点，则共有 (n+1)/2 个码子

给定 n 个权值作为 n 的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树 (Huffman Tree)。霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

假设哈夫曼树是二叉的话，则度为 0 的结点个数为 N，度为 2 的结点个数为 N-1，则结点总数为 2N-1。哈夫曼树的结点个数必为奇数。

哈夫曼树不一定是完全二叉树，但一定是最优二叉树。

若度为 m 的哈夫曼树中, 其叶结点个数为 n, 则非叶结点的个数为 [(n-1)/(m-1)]。边的数目等于度。

图遍历与回溯

图搜索 -> 形成搜索树

1. 穷举法。
2. 贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数。
3. 回溯法。根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理。