数据结构（八）树
图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说，和数据 B、C、D 有关系；对于数据 B 来说，和 E、F 有关系。这就是“一对多”的关系。
这种存储结构为“树型”存储结构。
图1：树的示例
树的结点
结点：树结构存储的每一个数据元素都被称为“结点”
父节点（双亲节点）：图1中 结点A是B、C、D结点的父节点。
子节点）（孩子结点）：：B、C、D都是A的子节点
兄弟结点（）：对于B、C、D来说他们都有相同的父节点，所以他们互为兄弟结点。
根结点 ：每一个非空树都有且只有一个被称为根的节点。A为根结点
叶子结点：如果结点没有子结点，那么结点称为叶子结点。
子树和空树
子树：如图1中，整棵树的根结点为A，而如果单看B、E、F、K、L组成的部分来说，也是棵树，而且结点B是这棵树的根结点。所以成BEFKL这几个节点组成的树为整棵树的子树；同样结点E、K、L构成的也是一颗字数，根结点为E。
注意：单结点也是一棵树，只不过根结点就是他本身。图1中K、L、F等都是树，且都是整棵树的子树
空树：如何集合本身为空，name构成的树就被称为空树。空树中没有结点。
补充：在树结构中，对于具有同一个根结点的各个子树，相互之间不能有交集。例如，图 1（A）中，除了根结点 A，其余元素又各自构成了三个子树，根结点分别为 B、C、D，这三个子树相互之间没有相同的结点。如果有，就破坏了树的结构，不能算做是一棵树。
结点的度和层次
- 度：对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）。例如，图 1（A）中，根结点 A 下分出了 3 个子树，所以，结点 A 的度为 3。
一棵树的度是树内各结点的度的最大值。图 1（A）表示的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。
- 结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。对于图1来说，A结点在第一层B、C、D为第二层，E、F、G、H、I、J在第三层，K、L、M在第四层。
一棵树的深度（高度）是树中结点所在的最大的层次。图 1（A）树的深度为 4。
有序树和无序树
如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。
在有序树中，一个结点最左边的子树称为"第一个孩子"，最右边的称为"最后一个孩子"。
拿图 1（A）来说，如果是其本身是一棵有序树，则以结点 B 为根结点的子树为整棵树的第一个孩子，以结点 D 为根结点的子树为整棵树的最后一个孩子。
森林
由 m（m >= 0）个互不相交的树组成的集合被称为森林。图 1（A）中，分别以 B、C、D 为根结点的三棵子树就可以称为森林。
前面讲到，树可以理解为是由根结点和若干子树构成的，而这若干子树本身是一个森林，所以，树还可以理解为是由根结点和森林组成的。用一个式子表示为：
Tree = (root,F)
其中，root 表示树的根结点，F 表示由 m（m >= 0）棵树组成的森林。
树的表示方法
除了图 1（A）表示树的方法外，还有其他表示方法：
图2：树的表示形式
图 2（A）是以嵌套的集合的形式表示的（集合之间绝不能相交，即图中任意两个圈不能相交）。
图 2（B）使用的是凹入表示法（了解即可），表示方式是：最长条为根结点，相同长度的表示在同一层次。例如 B、C、D 长度相同，都为 A 的子结点，E 和 F 长度相同，为 B 的子结点，K 和 L 长度相同，为 E 的子结点，依此类推。
最常用的表示方法是使用广义表的方式。图 1（A）用广义表表示为：
(A , ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I , J ) ) )
二叉树
简单地理解，满足以下两个条件的树就是二叉树：
- 1.本身是有序树；
- 2.树中包含的各个结点度不能超过2 即只能是0、1、2；
例如，图3 a)就是一棵二叉树，而图3 b) 则不是。
图3：二叉树示意图
二叉树的性质
经过前人的总结，二叉树具有以下几个性质：
1.二叉树中，第i层最多有2i-1个结点
2.如果二叉树的深度为K,那么此二叉树最多有2k-1个结点
3.二叉树中，终端结点树(叶子结点树)为n0，度为2的节点数为n2，则n0=n2+1
满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
图4：满二叉树示意图
满二叉树除了满足普通二叉树的性质，还具有以下性质：
1.满二叉树中第 i 层的节点数为 2n-1 个。
2.深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
3.满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4.具有 n 个节点的满二叉树的深度为 log2(n+1)。
完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
图5：完全二叉树示意图
如图 3a) 所示是一棵完全二叉树，图 3b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。
⌊log2n⌋ 表示取小于 log2n 的最大整数。例如，⌊log24⌋ = 2，而 ⌊log25⌋ 结果也是 2。
对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
- 当i >1 时，父亲节点为结点[i/2].(i=1时，表示的是根结点，无父亲结点)。
- 2.如果2*i > n （总结点的个数），则结点i肯定没有左子结点，否则左子结点是i * 2 。
- 3.如果2 * i + 1> n,则结点i 肯定没有右孩子，否则右子结点是i * 2 + 1。
二叉树的顺序存储
- 二叉树的存储结构有两种，分别为顺序存储和链式存储。
顺序存储
二叉树的顺序存储，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。如果想存储普通二叉树，需要提前将普通的二叉树转化为完全二叉树。
普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些空结点，将其拼凑成完全二叉树即可。
图6：普通二叉树的转化
完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。
图7：完全二叉树示意图
例如，存储图 7 所示的完全二叉树，其存储状态如图 8 所示：
图8：完全二叉树存储状态示意图
同样，普通二叉树转化的完全二叉树也是如此：
图9：普通二叉树的存储状态
不仅如此，从顺序表中还原完全二叉树也很简单。我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,...），若节点 i 有左右孩子，则其左孩子节点为 2i，右孩子节点为 2i+1。此性质可用于还原数组中存储的完全二叉树，也就是实现由图 8 到图 7、由图 9 到图 6 的转变。
链式存储结构
其实二叉树并不适合用数组存储，因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或多会存在空间浪费的现象。
图10：普通二叉树示意图
如图10所示，若将其采用连式存储，则只需从树的根结点开始，将各个结点及其左右子结点使用链表存储即可：
图11：二叉树链式存储结构示意图
采用链式存储二叉树时，其节点结构由 3 部分构成（如图 12 所示）：
- 1.指向左子结点的指针（Lchild）;
- 2.结点存储的数据（data）；
- 3.指向右子结点的指针（Rchild）;
图12：二叉树结点结构
其实，二叉树的链式存储结构远不止图11 所示的这一种。例如，在某些实际场景中，可能会做 "查找某节点的父节点" 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点，如图 13 所示：
图13：自定义二叉树的链式存储结构
这样的链表结构，通常称为三叉链表。
二叉树的（4种）遍历算法
图14：二叉树示意图
遍历二叉树无非有两种方式
- 1.层次遍历 ：通过对树中各层的节点从左到右依次遍历。
- 2.普通遍历 ：按照 "从上到下，从左到右" 的顺序遍历整棵二叉树。 普通遍历又分为：
- 1.先序遍历
- 2.中序遍历
- 3.后序遍历
图15：层次遍历示意图
图16：普通遍历示意图
首先观察图15 中的层次遍历，整个遍历过程只经过各个节点一次，因此在层次遍历过程，每经过一个节点，都必须立刻访问该节点，否则错失良机，后续无法再对其访问。
而普通遍历方式则不同，通过观察图 3 可以看到，整个遍历二叉树的过程中，每个节点都被经过了 3 次（虽然叶子节点看似只经过了 2 次，但实际上可以看做是 3 次）。以图 16 中的节点 2 为例，如图 17 所示，它被经过了 3 次。
图17：遍历结点2过程示意图
因此，在编程实现时，我们可以设定真正访问各个节点的时机，换句话说，我们既可以在第一次经过各节点时就执行访问程序，也可以在第二次经过各节点时访问，甚至可以在最后一次经过各节点时访问。
这也就引出了以下 3 种遍历二叉树的算法：
- 1.先序遍历：每遇到一个节点，先访问，然后再遍历其左右子树（对应图 17 中的 ①）；
- 2.中序遍历：第一次经过时不访问，等遍历完左子树之后再访问，然后遍历右子树（对应图 17 中的 ②）；
- 3.后序遍历：第一次和第二次经过时都不访问，等遍历完该节点的左右子树之后，最后访问该节点（对应图 17 中的 ③）；
先序遍历算法访问节点的先后次序为：
1 2 4 5 3 6 7
中序遍历算法访问节点的次序为：
4 2 5 1 6 3 7
后序遍历访问节点的次序为：
4 5 2 6 7 3 1
二叉树的层次遍历
按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。
层次遍历的实现过程
层次遍历图 15 中的二叉树：
- 首先，根结点1入队；
- 根结点1出队，出队的同时将左子结点2 和右子结点3 分别入队
- 队头结点2出队，出队同时将结点2的左子结点4和右子结点5依次入队。
- 队头结点3出队，出队同时将结点3的左子结点6和右子结点7依次入队。
- 不断地循环，直至队列内为空。
二叉树的前序遍历(递归与非递归)
二叉树先序遍历的实现思想
1.访问根结点；
2.访问当前结点的左子树；
3.若当前结点无左子树，访问当前结点的右子树；
图18：完全二叉树示意图
以图 18 为例，采用先序遍历的思想遍历该二叉树的过程为：
- 访问该二叉树的根节点，找到 1；
- 访问节点1的左子树，找到节点2；
- 访问节点2的左子树，找到节点4；
- 由于访问节点4左子树失败，且访问右子树也失败，因此节点4为根结点的子树遍历完成。但结点2还没有遍历其右子树。因此开始遍历，访问节点5；
- 由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；
- 访问节点 3 左子树，找到节点 6；
- 由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
- 节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；
上述为递归实现流程
非递归实现
先拿到结点打印，然后压入栈中，然后获取左子结点，进入下一次循环，如果左子结点为空，弾栈获取栈中数据的右子结点进入下一次循环。如果右子结点为空 继续弾栈。
public static void preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while(null != current || !stack.isEmpty()) {
if(null != current) {
System.out.print(current.getData());
stack,push(current);
current = current.getLeft();
}else {
current = stack.pop().getRight();
}
}
}
二叉树的中序遍历(递归与非递归)
递归非常简单，所以此处不描述。
非递归实现
与前序流程完全相同，只是在数据弾栈的时候打印。
public static void inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while(null != current || !stack.isEmpty()) {
if(null != current) {
stack,push(current);
current = current.getLeft();
}else {
current = stack.pop();
System.out.print(current.getData());
current = current.getRight();
}
}
}
二叉树的后序遍历(递归与非递归)
递归非常简单，所以此处不描述。
非递归实现
后序非递归与前序和中序有很大区别 需要压栈两次，并且子结点压栈需要从右子结点开始。
将数据压入栈中2次。如果弾出栈的数据与栈顶数据相同，那么将此结点的右子树（如果存在）压入栈2次，再将左子树（如果存在）压入栈两次。如果弾出栈的数据与栈顶数据不同，那么说明已经遍历过该结点左右子树，直接输出结点值即可。
public static void postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
stack.push(current);
stack.push(current);
while( !stack.isEmpty()) {
current = stack.pop();
if(!stack.isEmpty() && current = stack.peek()) {
//注意：需要先放右子结点
if(null != current.getRight()) {
stack.push(current.getRight());
stack.push(current.getRight());
}
if(null != current.getLeft()) {
stack.push(current.getLeft());
stack.push(current.getLeft());
}
}else {
System.out.print(current.getData());
}
}
}
线索二叉树
按照某种方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列，在该序列中，除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结点有且仅有一个直接后继结点；
按照某种方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列，在该序列中，除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结点有且仅有一个直接后继结点；
能利用这些空指针域来存放指向该节点的直接前驱或是直接后继的指针，则可由此信息直接找到在该遍历次序下的前驱结点或后继结点，从而比递归遍历提高了遍历速度，节省了建立系统栈所使用的存储空间；
这些被重新利用起来的空指针就被称为线索（Thread），加上了这些线索的二叉树就是线索二叉树；如图：
图19：二叉树链表存储结构示意图
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种；
图20：线索二叉树中结点的结构
LTag 和 RTag 为标志域。实际上就是两个布尔类型的变量：
- LTag 值为 0 时，表示 lchild 指针域指向的是该结点的左孩子；为 1 时，表示指向的是该结点的直接前趋结点；
- RTag 值为 0 时，表示 rchild 指针域指向的是该结点的右孩子；为 1 时，表示指向的是该结点的直接后继结点。
表示二叉树时，使用图 20 所示的结点结构构成的二叉链表，被称为线索链表；构建的二叉树称为线索二叉树;
二叉树的线索化
- 我们对二叉树进行中序遍历，将所有的节点右子节点为空的指针域指向它的后继节点。如图21：
图21：二叉树中序遍历右子结点线索化示意图
-
接下来将这颗二叉树的所有节点左指针域为空的指针域指向它的前驱节点。如图22：
图22：二叉树中序遍历左子结点线索化示意图
-
通过上面两步完成了整个二叉树的线索化，最后结果如下图：
图23：二叉树线索化结果示意图
通过观察上图（蓝色虚线代表后继、绿色虚线代表前驱），可以看出，线索二叉树，等于是把一棵二叉树转变成了一个“特殊的双向链表“(后面会解释为什么叫特殊的双向链表），这样对于我们的新增、删除、查找节点带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。
图24：线索化后生成的双向链表
- 线索化的实质就是将二叉链表中的空指针改为指向前驱节点或后继节点的线索；
- 线索化的过程就是修改二叉链表中空指针的过程，可以按照前序、中序、后序的方式进行遍历，分别生成不同的线索二叉树；
- 有了线索二叉树之后，我们再次遍历时，就相当于操作一个双向链表。
- 使用场景：如果我们在使用二叉树过程中经常需要遍历二叉树或者查找节点的前驱节点和后继节点，可以考虑采用线索二叉树存储结构。
public class ThreadBinaryTree {
private Node preNode; //线索化时记录前一个节点
//节点存储结构
static class Node {
String data; //数据域
Node left; //左指针域
Node right; //右指针域
boolean isLeftThread = false; //左指针域类型 false：指向子节点、true：前驱或后继线索
boolean isRightThread = false; //右指针域类型 false：指向子节点、true：前驱或后继线索
Node(String data) {
this.data = data;
}
}
/**
* 通过数组构造一个二叉树（完全二叉树）
* @param array
* @param index
* @return
*/
static Node createBinaryTree(String[] array, int index) {
Node node = null;
if(index < array.length) {
node = new Node(array[index]);
node.left = createBinaryTree(array, index * 2 + 1);
node.right = createBinaryTree(array, index * 2 + 2);
}
return node;
}
/**
* 中序线索化二叉树
* @param node 节点
*/
void inThreadOrder(Node node) {
if(node == null) {
return;
}
//处理左子树
inThreadOrder(node.left);
//左指针为空,将左指针指向前驱节点
if(node.left == null) {
node.left = preNode;
node.isLeftThread = true;
}
//前一个节点的后继节点指向当前节点
if(preNode != null && preNode.right == null) {
preNode.right = node;
preNode.isRightThread = true;
}
preNode = node;
//处理右子树
inThreadOrder(node.right);
}
/**
* 中序遍历线索二叉树，按照后继方式遍历（思路：找到最左子节点开始）
* @param node
*/
void inThreadList(Node node) {
//1、找中序遍历方式开始的节点
while(node != null && !node.isLeftThread) {
node = node.left;
}
while(node != null) {
System.out.print(node.data + ", ");
//如果右指针是线索
if(node.isRightThread) {
node = node.right;
} else { //如果右指针不是线索，找到右子树开始的节点
node = node.right;
while(node != null && !node.isLeftThread) {
node = node.left;
}
}
}
}
/**
* 中序遍历线索二叉树，按照前驱方式遍历（思路：找到最右子节点开始倒序遍历）
* @param node
*/
void inPreThreadList(Node node) {
//1、找最后一个节点
while(node.right != null && !node.isRightThread) {
node = node.right;
}
while(node != null) {
System.out.print(node.data + ", ");
//如果左指针是线索
if(node.isLeftThread) {
node = node.left;
} else { //如果左指针不是线索，找到左子树开始的节点
node = node.left;
while(node.right != null && !node.isRightThread) {
node = node.right;
}
}
}
}
/**
* 前序线索化二叉树
* @param node
*/
void preThreadOrder(Node node) {
if(node == null) {
return;
}
//左指针为空,将左指针指向前驱节点
if(node.left == null) {
node.left = preNode;
node.isLeftThread = true;
}
//前一个节点的后继节点指向当前节点
if(preNode != null && preNode.right == null) {
preNode.right = node;
preNode.isRightThread = true;
}
preNode = node;
//处理左子树
if(!node.isLeftThread) {
preThreadOrder(node.left);
}
//处理右子树
if(!node.isRightThread) {
preThreadOrder(node.right);
}
}
/**
* 前序遍历线索二叉树（按照后继线索遍历）
* @param node
*/
void preThreadList(Node node) {
while(node != null) {
while(!node.isLeftThread) {
System.out.print(node.data + ", ");
node = node.left;
}
System.out.print(node.data + ", ");
node = node.right;
}
}
public static void main(String[] args) {
String[] array = {"A", "B", "C", "D", "E", "F", "G", "H"};
Node root = createBinaryTree(array, 0);
ThreadBinaryTree tree = new ThreadBinaryTree();
tree.inThreadOrder(root);
System.out.println("中序按后继节点遍历线索二叉树结果：");
tree.inThreadList(root);
System.out.println("\n中序按后继节点遍历线索二叉树结果：");
tree.inPreThreadList(root);
Node root2 = createBinaryTree(array, 0);
ThreadBinaryTree tree2 = new ThreadBinaryTree();
tree2.preThreadOrder(root2);
tree2.preNode = null;
System.out.println("\n前序按后继节点遍历线索二叉树结果：");
tree.preThreadList(root2);
}
}
对于后序线索化二叉树，在结点中需要增加一个parent指针，否则会在某个结点的左右都有子结点时，找不到下一个结点的指针，这个时候使用parent结点去寻找下一个节点。
后序遍历线索化：
public class PostThreadBinaryTree {
private Node preNode; //线索化时记录前一个节点
//节点存储结构
static class Node {
String data; //数据域
Node left; //左指针域
Node right; //右指针域
Node parent; //父节点的指针（为了后序线索化使用）
boolean isLeftThread = false; //左指针域类型 false：指向子节点、true：前驱或后继线索
boolean isRightThread = false; //右指针域类型 false：指向子节点、true：前驱或后继线索
Node(String data) {
this.data = data;
}
}
/**
* 通过数组构造一个二叉树（完全二叉树）
* @param array
* @param index
* @return
*/
static Node createBinaryTree(String[] array, int index) {
Node node = null;
if(index < array.length) {
node = new Node(array[index]);
node.left = createBinaryTree(array, index * 2 + 1);
node.right = createBinaryTree(array, index * 2 + 2);
//记录节点的父节点（后序线索化遍历时使用）
if(node.left != null) {
node.left.parent = node;
}
if(node.right != null) {
node.right.parent = node;
}
}
return node;
}
/**
* 后序线索化二叉树
* @param node 节点
*/
void postThreadOrder(Node node) {
if(node == null) {
return;
}
//处理左子树
postThreadOrder(node.left);
//处理右子树
postThreadOrder(node.right);
//左指针为空,将左指针指向前驱节点
if(node.left == null) {
node.left = preNode;
node.isLeftThread = true;
}
//前一个节点的后继节点指向当前节点
if(preNode != null && preNode.right == null) {
preNode.right = node;
preNode.isRightThread = true;
}
preNode = node;
}
/**
* 后续遍历线索二叉树，按照后继方式遍历（思路：后序遍历开始节点是最左节点）
* @param node
*/
void postThreadList(Node root) {
//1、找后序遍历方式开始的节点
Node node = root;
while(node != null && !node.isLeftThread) {
node = node.left;
}
Node preNode = null;
while(node != null) {
//右节点是线索
if(node.isRightThread) {
System.out.print(node.data + ", ");
preNode = node;
node = node.right;
} else {
//如果上个处理的节点是当前节点的右节点
if(node.right == preNode) {
System.out.print(node.data + ", ");
if(node == root) {
return;
}
preNode = node;
node = node.parent;
} else { //如果从左节点的进入则找到有子树的最左节点
node = node.right;
while(node != null && !node.isLeftThread) {
node = node.left;
}
}
}
}
}
public static void main(String[] args) {
String[] array = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};
Node root = createBinaryTree(array, 0);
PostThreadBinaryTree tree = new PostThreadBinaryTree();
tree.postThreadOrder(root);
System.out.println("后序按后继节点遍历线索二叉树结果：");
tree.postThreadList(root);
}
}
前序、中序、后序线索化比较
- 前序遍历的顺序是：根左右，所以从根节点开始，沿着左子树进行处理，当子节点的left指针类型是线索时，说明到了最左子节点，然后处理子节点的right指针指向的节点，可能是右子树，也可能是后继节点，无论是哪种类型继续按照上面的方式（先沿着左子树处理，找到子树的最左子节点，然后处理right指针指向），以此类推，直到节点的right指针为空，说明是最后一个，遍历完成。
- 中序遍历的顺序是：左根右，因此第一个节点一定是最左子节点，先找到最左子节点，依次沿着right指针指向进行处理（无论是指向子节点还是指向后继节点），直到节点的right指针为空，说明是最后一个，遍历完成。
- 后序遍历线索化二叉树最为复杂，通用的二叉树数节点存储结构不能够满足后序线索化，因此我们扩展了节点的数据结构，增加了父节点的指针。后序的遍历顺序是：左右根，先找到最左子节点，沿着right后继指针处理，当right不是后继指针时，并且上一个处理节点是当前节点的右节点，则处理当前节点的右子树，遍历终止条件是：当前节点是root节点，并且上一个处理的节点是root的right节点。
双向线索二叉树
在线索二叉树的基础上，额外添加一个结点。此结点的作用类似于链表中的头指针，数据域不起作用，只利用两个指针域（由于都是指针，标志域都为 0 ）。
左指针域指向二叉树的树根，确保可以正方向对二叉树进行遍历；同时，右指针指向线索二叉树形成的线性序列中的最后一个结点。
这样，二叉树中的线索链表就变成了双向线索链表，既可以从第一个结点通过不断地找后继结点进行遍历，也可以从最后一个结点通过不断找前趋结点进行遍历。
图25：双向线索二叉树链表结构
- 双向线索二叉树遍历时，如果正向遍历，就从树的根结点开始。整个遍历过程结束的标志是：当从头结点出发，遍历回头结点时，表示遍历结束
- 2.逆向遍历线索二叉树的过程即从头结点的右指针指向的结点出发，逐个寻找直接前趋结点，结束标志同正向遍历一样。
普通二叉树
树的双亲表示法
图26：普通树存储结构
如图 26 所示，这是一棵普通的树，该如何存储呢？通常，存储具有普通树结构数据的方法有 3 种：
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
双亲表示法
双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。
图27：双勤表示法存储普通树示意图
孩子表示法
孩子表示法存储普通树采用的是顺序表+链表的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。
如果节点没有孩子节点（叶子节点），则该节点的链表为空链表。
图28：孩子表示法存储普通树示意图
使用孩子表示法存储的树结构，正好和双亲表示法相反，适用于查找某结点的孩子结点，不适用于查找其父结点。
其实，我们还可以将双亲表示法和孩子表示法合二为一，那么图 a) 中普通树的存储效果如图 29所示：
图29：双亲孩子表示法
使用图 29 结构存储普通树，既能快速找到指定节点的父节点，又能快速找到指定节点的孩子节点。该结构的实现方法很简单。
孩子兄弟表示法
树结构中，位于同一层的节点之间互为兄弟节点。
孩子兄弟表示法，采用的是链式存储结构，其存储树的实现思想是：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。
因此，该链表中的节点应包含以下 3 部分内容（如图所示）：
- 节点的值
- 指向子结点的指针；
- 指向兄弟结点的指针；
图30：结点结构示意图
使用孩子兄弟表示法进行存储的结果如图 31 所示:
图31：孩子兄弟表示法示意图
由图可以看到，结点 R 无兄弟结点，其孩子结点是 A；结点 A 的兄弟结点分别是 B 和 C，其孩子结点为 D，依次类推。
观察图28和图31，图28 为原普通树，图31由图28中的普通树经过孩子兄弟表示方而转化而来的一棵树，确切的说，图31是一棵二叉树。
因此可以得出这样一个结论，即通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，换句话说，任意一棵普通树都有唯一的一棵二叉树与其应对。
因此，孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法，通常又被称为"二叉树表示法"或"二叉链表表示法"
森林转化为二叉树
森林，指的是由 n（n>=2）棵互不相交的树组成的集合，如图32所示：
图32：森林示意图
我们知道，任意一棵普通树都可以转化为二叉树，而森林是由多棵普通树构成的，因此自然也可以转化为二叉树，其转化方法是：
- 首先将森林中所有普通树转化为二叉树
- 将森林中第一棵树的树根作为整个森林的树根，其他树的根节点看作是第一棵树根节点的兄弟节点，采用孩子兄弟表示法将所有树进行连接；
例如，将图 33a) 中的森林转化为二叉树，则以上两个转化过程分别对应图 33 中的 b) 和 c) ：
- 将森林中第一棵树的树根作为整个森林的树根，其他树的根节点看作是第一棵树根节点的兄弟节点，采用孩子兄弟表示法将所有树进行连接；
图33:森林转化为二叉树的过程示意图
森林转化为二叉树，更多的是为了对森林中的结点做遍历操作。遍历二叉树有四种方式，分别是层次遍历、前序遍历、中序遍历、后序遍历。转化前的森林与转化后的二叉树相比，层次遍历和后序遍历访问节点的顺序不同，而前序遍历和中序遍历访问的顺序是相同的
以图32中的森林为例，其转化后的二叉树为图 2c)，两者比较，其先序遍历访问节点的顺序都是 A B C D E F G H I J；同样，
中序遍历访问节点的顺序也相同，都是 B C D A F E H J I G。而后序遍历和层次遍历访问节点的顺序是不同的。
由二叉树转化为森林的过程也就是森林转化二叉树的逆过程，也就是图32 中由 c) 到 b) 再到 a) 的过程。
哈夫曼树（最优树、最优二叉树）
哈夫曼树相关的几个名词
结点的权：哈夫曼树中的权值可以理解为：权值大表明出现概率大，一个节点的权值实际上就是这个结点子树在整个树中所占的比例。
路径长度：从树中一个节点到另一个节点之间的分支构成两个节点之间的路径，路径上分支数目称为路径长度
树的路径长度：从根节点到每一个子节点的路径长度之和。
结点的带权路径长度：从当前节点到根的路径长度乘以节点的权值。
树的带权路径长度: 树中所有叶子节点的带权路径长度之和。 简称（WPL）
哈夫曼树：当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。
图34：带权二叉树
针对上面图34两个二叉树，我们解释上面提到个各个概念，
在左图中根节点到节点D的路径长度为4。
在右图中根节点到节点D的路径长度为2。
左图中树的路径长度为：1+1+2+2+3+3+4+4 = 20。
右图中树的路径长度为：1+2+3+3+2+1+2+2=16。
左图中二叉树的WPL = 5 * 1+ 15 * 2 + 40 * 3 + 30 * 4 + 10 * 4 = 315。
右图中二叉树的WPL = 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 *2 = 220。
计算出的这两个结果可以说明什么问题呢？如果我们现在对1000个成绩进行判定，用左图的树进行判定需要3150次，右图需要2200次，可见性能有了很大提升。
哈夫曼树的算法
根据上面介绍的哈夫曼树的定义，要使一棵哈夫曼树的WPL最小，就必须使权值越大的叶子节点越靠近根节点，同时除了带权值的叶子节点外，必须保证其他所有的节点度为2，这样构造出的二叉树便是哈夫曼树。
假如我们有4个节点A、B、C、D，权值分别为：10、5、2、8，我们该如何构建哈夫曼树呢？
- 先把这些结点按照权值从小到大排序，排序结果为：C(2)、B(5)、D(8)、A(10)
- 取前两个最小权值的结点作为一个新节点N1（N1的权=C的权值+B的权值）的两个子结点，注意相对较小的作为左子结点，此时我们取出C(2)、B(5),C作为N1的左子结点 D作为N1的右子结点。
- 将N1替换为C(2)、B(5),插入到上面结点的排序结果中，继续保持从小到大的顺序。此时排序序列为：N(7)、D(8)、A(10)
- 重复步骤2 取出N1（7）、D（8）构建新的节点N2，N1为N2的左节点、D为N2的右节点，N2的权值为N1的权值+D的权值=15
- 重复步骤3，将N2插入排序序列，序列为A(10)、N2(15)
- 重复步骤2，将A（10）、N2（15）取出，构建新的节点N3，A为左子节点、N2为右子节点，此时N3是根节点。
图35:哈夫曼树构建过程
通过上面的构造哈夫曼树的步骤，我们总结下哈夫曼算法的思想：
- 根据给定的n个权值{W1, W2, …, Wn}构成n棵二叉树的集合F={T1, T2, …,Tn}，其中每棵二叉树Ti中只有一个带权为Wi根节点，其左右子树均为空；
- 在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且把新的二叉树的根节点的权值为其左右子树的根节点的权值之和；
- 在F中删除这两棵树，同时将新得到的二叉树加入F中；
- 重复上面2、3步骤，直到得到一棵树为止。这棵树便是哈夫曼树。
public class HuffmanTree {
//节点数据
static class Node {
String data; //数据
double weight; //权重
Node left; //左节点
Node right; //右节点
public Node(String data, double weight) {
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "Node [data=" + data + ", weight=" + weight + "]";
}
}
/**
* 构造哈夫曼树
* @param nodes 节点集合
* @return
*/
static Node createTree(List<Node> nodes) {
while(nodes != null && nodes.size() > 1) {
quickSort(nodes, 0, nodes.size()-1);
//1、获取权值最小的两个元素
Node left = nodes.get(nodes.size()-1);
Node right = nodes.get(nodes.size()-2);
//2、生成新的节点
Node node = new Node(null, left.weight + right.weight);
//3、新节点作为两个元素的父节点
node.left = left;
node.right = right;
//4、从序列中删除这两个最小的元素
nodes.remove(left);
nodes.remove(right);
//5、将新元素插入到序列中
nodes.add(node);
}
//最后集合中的唯一元素就是根元素
return nodes.get(0);
}
/**
* 快速排序算法（从大到小）
* @param nodes 节点集合
* @param start 开始位置
* @param end 结束位置
*/
private static void quickSort(List<Node> nodes, int start , int end) {
if (start < end) {
//第一个元素作为分界值
Node base = nodes.get(start);
//i从左边搜索，搜索大于分界值的元素的索引
int i = start;
//j从右边开始搜索，搜索小于分界值的元素的索引
int j = end + 1;
while(true) {
//找到大于分界值的元素的索引，或i已经到了end处
while(i < end && nodes.get(++i).weight >= base.weight);
//找到小于分界值的元素的索引，或j已经到了start处
while(j > start && nodes.get(--j).weight <= base.weight);
if (i < j) {
swap(nodes , i , j);
} else {
break;
}
}
swap(nodes , start , j);
//递归排序左子序列
quickSort(nodes , start , j - 1);
//递归排序右边子序列
quickSort(nodes , j + 1, end);
}
}
/**
* 交换数组指定位置的元素
* @param nodes 数组
* @param i 索引值
* @param j 索引值
*/
private static void swap(List<Node> nodes, int i, int j) {
Node tmpNode = nodes.get(i);
nodes.set(i , nodes.get(j));
nodes.set(j , tmpNode);
}
/**
* 层级遍历
* @param root
* @return
*/
public static List<Node> breadthFirst(Node root) {
Queue<Node> queue = new ArrayDeque<Node>();
List<Node> list = new ArrayList<Node>();
if(root != null) {
//将根元素入“队列”
queue.offer(root);
}
while(!queue.isEmpty()) {
//将该队列的“队尾”的元素添加到List中
list.add(queue.peek());
Node p = queue.poll();
//如果左子节点不为null，将它加入“队列”
if(p.left != null) {
queue.offer(p.left);
}
//如果右子节点不为null，将它加入“队列”
if(p.right != null) {
queue.offer(p.right);
}
}
return list;
}
public static void main(String[] args) {
List<Node> nodes = new ArrayList<Node>();
nodes.add(new Node("A" , 10));
nodes.add(new Node("B" , 8));
nodes.add(new Node("C" , 3));
nodes.add(new Node("D" , 12));
nodes.add(new Node("E" , 20));
Node root = HuffmanTree.createTree(nodes);
System.out.println(breadthFirst(root));
}
}
哈夫曼编码
在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，01，1，并可将上述电文用二进制序列：000110100发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面3个0是3个A，1个B、2个A，即译码不唯一，这种编码方法不可使用。
因此，为了设计长短不等的编码，以便减少电文的总长，还必须考虑编码的唯一性，即在建立不等长编码时必须使任何一个字符的编码都不是另一个字符的前缀，这宗编码称为前缀编码（prefix code）。
假设字符集4个字符A，B，C，D的频率分别为45，10, 10， 35，合起来是100%，那么，我们可以按照哈夫曼树来规划它们
图36：哈夫曼编码示意图
上图的构建规则为：
（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树（如上图一）；
（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码（如上图二）。
此时A的编码为0，B的编码为100，C的编码为101，D的编码为11，对于上面的文本内容”ABDDCAA”编码的结果为”0100111110100”。当接收方接收到编码字符串时，根据上图的哈夫曼树可知，第一个0为A，第二个100为B，以此类推，从而破解成功。
把通过哈夫曼树构建的编码称为哈夫曼编码，哈夫曼编码的关键是任意字符的编码都不是其它字符编码的前缀，保证编码的唯一性。
n个结点构造多少种树
方法一
如果两棵树中各结点的位置都一一对应，可以说这两棵树相似，如果两棵树不仅相似，而且对应节点上的数据也相同，就可以说这两棵树等价。
对于任意一棵普通树，通过孩子兄弟表示法都可以构造成一棵二叉树与之对应。每一棵普通树对应的都是一棵没有右子树的二叉树，所以对于n个结点的树来说，树的形态改变是因为除了根结点之外的其他结点改变形态得到的，所以n个结点构建的形态不同的树与之对应的是n-1个结点构建的形态不同的二叉树。
最直接的一种方法就是推理。当 n=0 时，只能构建一棵空树；当 n=2 时，可以构建 2 棵形态不同的二叉树，如图 1（A）；当 n=3 时，可以构建 5 棵形态互不相同的二叉树，如图 1（B）。
图37：不同形态的二叉树
对于具有 n（ n>1 ）个结点的二叉树来说，都可以看成是一个根结点、由 i 个结点组成的左子树和由 n-i-1 个结点组成的右子树。
当n=1时，也适用，只不过只有一个根结点，没有左右孩子。
可以得出一个递推公式：
图38：二叉树形态数量计算公式
通过对公式一步步的数学推算，最后得出，含有 n 个结点的不相似的二叉树的数量为：
图39：最终公式
方法二
从遍历二叉树的角度进行分析，对于任意一棵二叉树来说，它的前序序列和中序序列以及后序序列都是唯一的。其实是这句话还可以倒过来说，只要确定了一棵二叉树的三种遍历序列中的两种，那么这棵二叉树也可以唯一确定。
例如，给定了一个二叉树的前序序列和中序序列分别为：
前序序列：A B C D E F G
中序序列：C B E D A F G
可以唯一得到的二叉树
图40：构造二叉树的过程示意图
分析：通过前序序列得知，结点A为二叉树的根结点，结合中序序列，在结点 A 左侧的肯定为其左孩子中的所有结点，右边为右孩子的所有结点，如图 40（1）所示。
再分析 A 结点的左孩子，在前序序列看到，结点 A 后紧跟的是结点 B，由此断定结点 A 的左孩子是 B，再看中序序列，结点 B 左侧只有一个结点 C ，为 B 的左孩子，结点 B 右侧的结点E 和 D 为右孩子，如图 40（2）。
再分析结点 B 的右孩子，前序序列看到，结点 D 在 E 的前边，所有 D 为 B 的右孩子。在中序序列中，结点 E 在 D 前边，说明 E 是 D 的左孩子，如图 40（3）。
最后分析结点 A 的右孩子，由前序序列看到， F 在 G 前边，说明F为根结点。在中序序列中也是如此，说明，G 是 F 的右孩子。如图 40（4）所示。
如果要唯一确定一棵二叉树，必须知道至少两种遍历序列。如果只确定一种序列，无法准确判定二叉树的具体构造。
不同形态二叉树的数目恰好就是前序序列一定的情况下，所能得到的不同的中序序列的个数。
根据数列中数据的个数 n，所得到的排列顺序的数目为：
图41:二叉树形态数量计算公式
·
