遍历二叉树
遍历二叉树指的是按某种规律依次访问二叉树的每个节点，对二叉树的遍历过程就是将非线性结构的二叉树中的节点排列在一个线性序列上的过程。
如果采用顺序结构来保存二叉树，程序遍历二叉树将非常容易，直接遍历底层数组即可。
如果采用链表来保存二叉树的节点，则有以下两类遍历方式：
- 深度优先遍历：这种遍历算法将先访问到树中最深层次的节点。又可以分 3 种：
- 前序遍历
- 中序遍历
- 后序遍历
- 广度优先遍历：这种遍历算法将逐层访问每层的节点，先访问根节点(第一层)，然后访问第二层的节点，依次类推。又称为按层遍历。为了实现广度优先遍历，可以借助队列来实现：
- 第一步：建一个队列，把树的根节点压入队列。
- 第二步：从队列中弹出一个节点(第一次弹出的就是根节点)，然后把该节点的左、右节点压入队列，如果没有子节点，说明已经到达叶子节点。
- 第三步：用循环重复执行第二步，知道队列为空。当队列为空时，说明所有的叶子节点(深度最深的层)都已经经过了队列，也就完成了遍历。
哈夫曼树
哈夫曼树又称为最优二叉树，是一类带权路径最短的二叉树，在信息检索中很常用。
基本概念：
- 节点之间的路径长度：从一个节点到另一个节点之间的分支数量称为两个节点之间的路径。
- 树的路径长度：从根节点到树中每一个节点的路径长度之和。
排序二叉树
排序二叉树具有如下性质：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
- 若它的右子树不空，则右子树上所有节点的值均小于它的根节点的值。
- 它的左、右子树也分别为排序二叉树。
对于排序二叉树，按照中序遍历就可以得到由小到大的有序序列。
当程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序二叉树，必须对该排序二叉树进行维护，维护可分为几种情况：
- 被删除的节点是叶子节点，只需将它从其父节点中删除。
- 被删除节点 p 只有左子树，将 p 的左子树 pL 添加成 p 的父节点的左子树即可；被删除节点 p 只有右子树，将 p 的右子树 pR 添加成 p 的父节点的右子树即可。
若被删除节点 p 的左、右子树均非空，有以下两种做法：
将 pL 设为 p 的父节点 q 的左或右子节点(取决于 p 是其父节点 q 的左、右子节点)，将 pR 设为 p 节点的中序前趋节点 s 的右子节点(s 是 pL 最右下的节点，也就是 pL 子树中最大的节点)。
以 p 节点的中序前趋或后继替代 p 所指节点，然后再从原排序二叉树中删去中序前趋或后继节点(也就是，用大于 p 的最小节点或小于 p 的最大节点代替 p 节点)。
红黑树
排序二叉树虽然可以快速检索，但是如果插入的节点本身就是有序的，要么已经是从小到大排序，要么已经是从大到小排序，那么得到的二叉树将变成一个链表。
红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组，例如，集合类 TreeMap 就是一个红黑树的实现。
红黑树性质
红黑树在排序二叉树基础上增加了几个要求：
- 性质1：每个节点要么是红色，要么是黑色。
- 性质2：根节点永远是黑色的。
- 性质3：所有的叶子节点都是空节点(即 null)，并且是黑色的。
- 性质4：每个红色节点的两个子节点都是黑色的(从每个叶子到根的路径不会有两个连续的红色节点)。
- 性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。
根据性质5，红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数目被称为树的 “黑色高度(black-height)”。
根据性质4，保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的 2 倍。假如有一颗黑色高度为 3 的红黑树，从根节点到叶子节点的最短路径长度是 2 ，该路径上全都是黑色节点(黑节点-黑节点-黑节点)，最长路径也只能为 4 ，在每个黑色节点之间插入一个红节点(黑节点-红节点-黑节点-红节点-黑节点)。
结论：对于给定的黑色高度为 N 的红黑树，从根节点到叶子节点的最短路径长度为 N-1，最长路径长度为 2*(N-1)
注意：性质3中指定红黑树的每个叶子节点都是空节点，而且叶子节点都是黑色，但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。
红黑树通过以上限制来保证它大致上是平衡的，高度不会无线增高，因此检索性能更好。但红黑树在进行插入和删除操作会导致树不再符合红黑树的特征，因此插入和删除操作都需要进行一定的维护。
红黑树插入操作
插入操作按照如下步骤进行：
- 以排序二叉树的方法插入新节点，并将它设为 红色。
进行颜色调换和树旋转。(新插入的节点定义为 N 节点，把 N 节点的父节点定位为 P 节点，把 P 节点的兄弟节点定义为 U 节点，把 P 节点父节点定义为 G 节点)
情形一：新节点 N 是树的根节点，没有父节点。
在这种情形下，直接将它设置为黑色以满足性质2。
情形二：新节点的父节点 P 是黑色。
该情况下，新插入的节点是红色的，因此依然满足性质4，而且因为新节点 N 有两个黑色叶子节点，但是由于新节点 N 是红色，通过它的每个子节点的路径依然保持相同的黑色节点数目，因此依然满足性质5。
情形三：如果父节点 P 和父节点的兄弟节点 U 都是红色。
在这种情况下，程序应该将 P 节点、U 节点都设置为黑色，并将 P 节点的父节点设为红色(用来保持性质5)。限制，新节点 N 有了一个黑色的父节点。由于从 P 节点、U 节点到根节点的任何路径都必须通过 G 节点，这些路径上的黑色节点数目没有改变(原来有叶子和 G 节点两个黑色节点，现在有叶子和 P 两个黑色节点)。经过以上处理后，红色的 G 节点和父节点也有可能是红色的，这就违反了性质4，因此还需要对 G 节点递归进行整个过程(把 G 当成新插入的节点进行处理)。
情形四：父节点 P 是红色，而其兄弟节点 U 是黑色或缺少；且新节点 N 是父节点 P 的右子节点，而父节点 P 又是其父节点 G 的左子节点。
在这种情况下，对新节点和其父节点进行一次左旋转，然后按情形5处理以前的父节点 P，也就是把 P 当成新插入的节点
情形五：父节点 P 是红色，而其兄弟节点 U 是黑色或缺少；且新节点 N 是其父节点的左子节点，而父节点 P 又是其父节点 G 的左子节点。
需要对节点 G 进行一次右旋转。在旋转产生的树中，以前的父节点 P 现在是新节点 N 和节点 G 的父节点。
树的旋转(Tree rotation)
树旋转是二叉树的一种子树调整操作，每一次旋转并不影响对该二叉树进行中序遍历的结果。旋转通常应用于需要调整树的局部平衡性的场合。
树的旋转分为两种基本的操作，即 左旋(逆时针旋转) 和 右旋(顺时针旋转)。
