二叉树

任何多叉树都可以转换为等价的二叉树，二叉树作为树结构的特例且不失一般性，因此主要研究二叉树。

遍历

由于树的元素并不存在天然的前驱和后继关系，但施加一定的约束就可以确定一种顺序，因此称二叉树是一种半线性数据结构。常见的遍历顺序有：先序，中序，后序，层序。这里实现了所有遍历顺序的递归与非递归版本。

二叉线索树

\(n\) 个节点的二叉树有 \(n-1\) 条边，即有 \(n-1\) 个指针指向其它节点。每个节点都有两个指针，那么就有 \(2n-(n-1)=n+1\) 个空闲指针。将这些指针利用起来，指向前驱或后继，形成类似链表的结构。主要是节省非递归情况下的空间开销，以及省去了递归、栈操作的开销。为了区分节点指针与线索指针，加入两个标签字段标识。

在遍历时构建临时线索的方式叫做 Morris 遍历，适合一次性遍历操作。

下文以中序二叉线索树为例。

构建

左指针指向中序前驱，右指针指向中序后继。注意，可以在中序遍历的同时完成线索化，思路与链表的构建类似：保存前驱，插入节点。

在中序遍历中，我们可以发现：一个节点只要有左儿子，那么左儿子一定是当前节点的前驱；一个节点只要有右儿子，那么当前节点一定是右儿子的前驱。把握住这点代码就好写了。

一个小优化，加入一个头节点，让遍历序列的第一个和最后一个元素空闲的指针都指向它，从而形成一个类似循环链表的结构。笔者认为可以直接让首尾两个节点互指达到相同目的，就省去头节点了。

遍历

定义两个函数，First 和 Next，分别用于求以某点 \(p\) 为根的树的中序序列第一个节点和下一个节点，那么遍历就像链表一样了。

First 的实现是：只要 \(p\) 有左儿子，就递归，否则返回 \(p\)。 Next 的实现是：只要 \(p\) 有右儿子，就返回右子树的第一个节点（利用 First），否则返回 \(p\) 的后继线索。（没有右子树一定有线索）

总结

树的变种与实现细节过多，这里只是抛砖引玉。真正要学懂二叉树的遍历，关键是把握住顺序约束，其余都可以推导出来。

存储

顺序结构

双亲表示法：顺序存储节点，每个节点保存其父节点在数组中的位置。

链式结构

孩子表示法（邻接表）：每个节点带一个链表，把所有兄弟存里面。（即链表存该节点所有孩子）
孩子兄弟表示法（树、森林转二叉树）：左儿子存第一个孩子，右儿子存下一个兄弟，存完自动变二叉树。（对于森林，把每棵树转为二叉树。由于根没有兄弟，右儿子一定是空的，就可以把另一棵树加进去）

应用

哈夫曼树（最优编码二叉树）

每次选两个权值最小的树构成新的树，直到森林变为一棵树。贪心。编码的长度 = 节点在编码树中的高度。最优编码 = 平均编码长度最小 = 平均深度最小。

注意，上述选取过程不一定确定，在选取、合并子树时都可能出现歧义，好在不难解决。容易证得歧义不影响所得编码的最优性。一个简化的解决方式是让左子树权值小于右子树，如果权值相同，矮的放左边。

哈夫曼编码

哈夫曼树左分枝标 0，右分枝标 1，每个节点的哈夫曼编码就是从根到节点路径数字组成的一串二进制数。