前面介绍的数据结构————线性表、栈和队列都是线性的数据结构，这种数据结构之内的元素只存在一个对一个的关系，存储、处理起来相对简单。本章将要介绍的树则是一种更复杂的数据结构，这种数据结构内的元素存在一个对多个关系，例如，一个父节点可以包含多个子节点。
树也是一种非常常用的数据结构，尤其是二叉树的应用更是广泛，哈夫曼树及哈夫曼编码就是二叉树的重要用途，排序二叉树、平衡二叉树、红黑树再实际编程中都有极为广泛的用途。例如，Java 集合框架的 TreeMap 本质上就是红黑树的实现。
树的概述
作为一种非常常用的数据结构，树与前面介绍的线性表、栈、队列等线性结构不同，它是一种非线性结构。
树的定义和基本术语
计算机世界里的树，是从自然界实际的树抽象而来的，它指的是 N 个有父子关系的节点有限集合。对于这个有限的节点集合而言，它满足如下要求：
- 当 N=0 时，该节点集合为空，这棵树也被称为空树；
- 再任意的非空树中，有且仅有一个根（root）节点；
- 当 N>1 时，除根节点以外的其余节点可分为 M 个互为相交的有限集合 T1、T2……Tm，其中每个集合本身又是一棵树，并称其为根的子树（subtree）。
从上面定义可以发现树的递归特性：一棵树由根和若干颗子树组成，而每个子树又由若干颗更小的子树组成。
树中任一节点可以有 0 或多个子节点，但只能有一个父节点。根节点是一个特例，根节点没有父节点，叶子节点没有子节点。树中每个节点既可以是上一级节点的子节点，也可以是下一级节点的父节点，因此同一个节点可以既是父节点，也是子节点（类似于一个人————他既是他儿子的父亲，又是他父亲的儿子）。
很显然，父子关系是一种非线性的关系，所以树结构是非线性结构。
如果按节点是否包含子节点来分，节点分成以下两种：
- 普通节点：包含子节点的节点；
- 叶子节点：没有子节点的节点，因此叶子节点不可作为父节点。
如果按节点是否具有唯一的父节点来分，节点又可以分为如下两种：
- 根节点：没有父节点的节点，根节点不可作为子节点；
- 普通节点：具有唯一父节点的节点。
一棵树只能有一个根节点，如果一棵树有了多个根节点，那它已经不再是一棵树，而是多棵树的集合，有时也被称为森林。
与树有关的术语有如下一些：
- 节点：树的最基本组成单元，常包括一个数据元素及若干指针用于指向其它节点；
- 节点的度：节点拥有的子数的个数被称为节点的度（degree）；
- 树的度：树中所有节点的度的最大值就是该树的度；
- 叶子节点：度为 0 的节点被称叶子节点或终端节点；
- 分支节点：度不为 0 的节点被称分支节点或非终端节点；
- 子节点、父节点、兄弟节点：节点的子树的根被称为该节点的子节点，而该节点称做子节点的父节点（parent）。具有相同父节点的子节点之间互称为兄弟节点（sibling）；
- 节点的层次（level）：节点的层次从根开始算起，根的层次值为 1，其余节点的层次值为父节点的层次值加 1；
- 树的深度（depth）：树中节点的最大层次值称为树的深度或高度；
- 有序树与无序树：如果将树中节点的各个子树看成从左到右是有序的（即不能互换），则称该树为有序树，否则称为无序树；
- 祖先节点（ancestor）：从根到该节点所经分值上的所有节点；
- 后代节点（descendant）：以某节点为根的子树中任一节点都称为该节点的后代节点；
- 森林（forest）：森林是 2 颗或 2 颗以上互不相交的树的集合，删去一棵树的根，就得到一个森林。
树的基本操作
如果需要实现一棵树，程序不仅要以合适的方式保存该树的所有节点，还要记录节点与节点之间的父子关系。接下来，还应该为该树实现如下基本操作：
- 初始化：通常是一个构造器，用于创建一个空的树，或者以指定节点为根来创建树；
- 为指定节点添加子节点；
- 判断树是否为空；
- 返回根节点；
- 返回指定节点（非根节点）的父节点；
- 返回指定节点（非叶子节点）的所有子节点；
- 返回指定节点（非叶子节点）的第 i 个子节点；
- 返回该树的深度；
- 返回指定节点的位置。
为了实现树这种数据结构，程序必须能记录节点与节点之间的父子关系，为此有以下两种选择：
- 父节点表示法：每个子节点都记录它的父节点；
- 孩子链表示法：每个非叶子节点通过一个链表来记录它所有的子节点。
父节点表示法
通过前面的介绍可以发现：树中除根节点之外的每个节点都有一个父节点。为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个 parent 域，用以记录该节点的父节点。
public class TreeParent<E> {
public static class Node<T> {
T data;
//记录其父节点的位置
int parent;
public Node(){
}
public Node(T data) {
this.data = data;
}
public Node(T data, int parent) {
this.data = data;
this.parent = parent;
}
@Override
public String toString() {
return "TreeParent$Node[data=" + data + ", parent=" + parent + "]";
}
}
private final int DEFAULT_TREE_SIZE = 100;
private int treeSize = 0;
//使用一个Node数组来记录该树里的所有记录
private Node<E>[] nodes;
//记录节点数
private int nodeNums;
//以指定根节点创建树
public TreeParent(E data) {
treeSize = DEFAULT_TREE_SIZE;
nodes = new Node[treeSize];
nodes[0] = new Node<>(data, -1);
nodeNums++;
}
//以指定根节点、指定treeSize创建树
public TreeParent(E data, int treeSize) {
this.treeSize = treeSize;
nodes = new Node[treeSize];
nodes[0] = new Node<>(data, -1);
nodeNums++;
}
//为指定节点添加子节点
public void addNode(E data, Node parent) {
for (int i = 0;i < treeSize;i++) {
//找到数组中第一个为null的元素，该元素保存新节点
if (nodes[i] == null) {
//创建新街点，并用指定的数组元素保存它
nodes[i] = new Node(data, pos(parent));
nodeNums++;
return;
}
}
throw new RuntimeException("该树已满，无法添加新节点");
}
//判断树是否为空
public boolean empty() {
//根节点是否为null
return nodes[0] == null;
}
//返回根节点
public Node<E> root() {
return nodes[0];
}
//返回指定节点（非根节点）的父节点
public Node<E> parent(Node node) {
//每个节点的parent记录了其父节点的位置
return nodes[node.parent];
}
//返回指定节点（非叶子节点）的所有子节点
public List<Node<E>> children(Node parent) {
List<Node<E>> list = new ArrayList<>();
for (int i = 0;i < treeSize;i++) {
//如果当前节点的父节点的位置等于parent节点的位置
if (nodes[i] != null && nodes[i].parent == pos(parent)) {
list.add(nodes[i]);
}
}
return list;
}
//返回该树的深度
public int deep() {
//用于记录节点的最大深度
int max = 0;
for (int i = 0;i < treeSize && nodes[i] != null;i++) {
//初始化本节点的深度
int def = 1;
//m记录当前节点的父节点的位置
int m = nodes[i].parent;
//如果其父节点存在
while (m != -1 && nodes[m] != null) {
//向上继续搜索父节点
m = nodes[m].parent;
def++;
}
if (max < def) {
max = def;
}
}
//返回最大深度
return max;
}
//返回包含指定值的节点
public int pos(Node node) {
for (int i = 0;i < treeSize;i++) {
//如果找到指定节点
if (nodes[i] == node) {
return i;
}
}
return -1;
}
}从上面程序的代码中可以看出，定义树节点时增加了一个 parent 域。该 parent 域用于保存该节点的父节点再数组中的位置索引，通过这种方式即可记录树中节点之间的父子关系。
使用这种父节点表示法来存储树时，添加节点时将新节点的 parent 域的值设为其父节点再数组中的索引即可。下面程序简单测试了上面的 TreeParent 类：
public class TreeParentTest {
public static void main(String[] args) {
TreeParent<String> tp = new TreeParent<>("root");
TreeParent.Node root = tp.root();
System.out.println(root);
tp.addNode("节点1", root);
System.out.println("此树的深度：" + tp.deep());
tp.addNode("节点2", root);
//获取根节点的所有子节点
List<TreeParent.Node<String>> nodes = tp.children(root);
System.out.println("根节点的第一个子节点：" + nodes.get(0));
//为根节点的第一个子节点新增一个子节点
tp.addNode("节点3", nodes.get(0));
System.out.println("此树的深度：" + tp.deep());
}
}通过上面介绍可以发现，父节点表示法的特点是：每个节点都可以快速找到它的父节点。但如果要找某个节点的所有子节点就比较麻烦，程序要遍历整个节点数组。
子节点链表示法
父节点表示法的思想是让每个节点“记住”它的父节点的索引，这种方式是从父子节点着手；反过来，还有另外一种方式：让父节点“记住”它的所有子节点。在这种方式下，由于每个父节点需要记住多个子节点，因此必须采用“子节点链”表示法。
采用子节点链表示法来记录树时，需要为每个节点维护一个子节点链，通过该子节点链来记录该节点的所有子节点。下面程序示范了这种“子节点表示法”的树：
public class TreeChild<E> {
private static class SonNode {
//记录当前节点的位置
private int pos;
private SonNode next;
public SonNode(int pos, SonNode next) {
this.pos = pos;
this.next = next;
}
}
public static class Node<T> {
T data;
//记录第一个子节点
SonNode first;
public Node(T data) {
this.data = data;
this.first = null;
}
@Override
public String toString() {
if (first != null) {
return "TreeChild$Node[data=" + data + ", first=" + first.pos + "]";
} else {
return "TreeChild$Node[data=" + data + ", first=-1]";
}
}
}
private final int DEFAULT_TREE_SIZE = 100;
private int treeSize = 0;
//使用一个Node[]数组来记录该树里的所有节点
private Node<E>[] nodes;
//记录节点数
private int nodeNums;
//以指定根节点创建树
public TreeChild(E data) {
treeSize = DEFAULT_TREE_SIZE;
nodes = new Node[treeSize];
nodes[0] = new Node<>(data);
nodeNums++;
}
//以指定根节点，指定treeSize创建树
public TreeChild(E data, int treeSize) {
this.treeSize = treeSize;
nodes = new Node[treeSize];
nodes[0] = new Node<>(data);
nodeNums++;
}
//为指定节点添加子节点
public void addNode(E data, Node parent) {
for (int i = 0;i < treeSize;i++) {
//找到数组中第一个为null的元素，该元素保存新节点
if (nodes[i] == null) {
//创建新节点，并用指定数组元素来保存它
nodes[i] = new Node(data);
if (parent.first == null) {
parent.first = new SonNode(i, null);
} else {
SonNode next = parent.first;
while (next.next != null) {
next = next.next;
}
next.next = new SonNode(i, null);
}
nodeNums++;
return;
}
}
throw new RuntimeException("该树已满，无法添加新节点");
}
//判断树是否为空
public boolean empty() {
//根节点是否为null
return nodes[0] == null;
}
//返回根节点
public Node<E> root() {
return nodes[0];
}
//返回指定节点（非叶子节点）的所有子节点
public List<Node<E>> children(Node parent) {
List<Node<E>> list = new ArrayList<>();
//获取parent节点的第一个子节点
SonNode next = parent.first;
//沿着孩子链不断搜索下一个孩子节点
while (next != null) {
list.add(nodes[next.pos]);
next = next.next;
}
return list;
}
//返回指定节点（非叶子节点）的第index个子节点
public Node<E> child(Node parent, int index) {
//获取parent节点的第一个子节点
SonNode next = parent.first;
//沿着孩子链不断搜索下一个孩子节点
for (int i = 0;next != null;i++) {
if (index == i) {
return nodes[next.pos];
}
next = next.next;
}
return null;
}
//返回该树的深度
public int deep() {
//获取该树的深度
return deep(root());
}
//这是一个递归方法，每颗子树的深度为其所有子树的最大深度+1
private int deep(Node node) {
if (node.first == null) {
return 1;
} else {
//记录其所有子树的最大深度
int max = 0;
SonNode next = node.first;
//沿着孩子链不断搜索下一个孩子节点
while (next != null) {
//获取以其子节点为根的子树的深度
int tmp = deep(nodes[next.pos]);
if (tmp > max) {
max = tmp;
}
next = next.next;
}
//最后，返回其所有子树的最大深度+1
return max + 1;
}
}
//包含指定值的节点
public int pos(Node node) {
for (int i = 0;i < treeSize;i++) {
//找到指定节点
if (nodes[i] == node) {
return i;
}
}
return -1;
}
}从上面程序可以看出，定义树节点时增加了一个 first 域。该 first 域用于保存对该节点的子节点链的引用，通过这种方式即可记录树中节点之间的父子关系。
使用这种子节点链表示法来存储树时，添加节点时只需找到指定父节点的子节点链的最后节点，并让它指向新增的节点。下面程序简单测试了上面的 TreeChild 类：
public class TreeChildTest {
public static void main(String[] args) {
TreeChild<String> tp = new TreeChild<>("root");
TreeChild.Node root = tp.root();
System.out.println("根节点：" + root);
tp.addNode("节点1", root);
tp.addNode("节点2", root);
tp.addNode("节点3", root);
System.out.println("添加子节点后的根节点：" + root);
System.out.println("此树的深度：" + tp.deep());
//获取根节点的所有子节点
List<TreeChild.Node<String>> nodes = tp.children(root);
System.out.println("根节点的第一个子节点：" + nodes.get(0));
//为根节点的第一个子节点新增一个子节点
tp.addNode("节点4", nodes.get(0));
System.out.println("根节点的第一个子节点：" + nodes.get(0));
System.out.println("此树的深度：" + tp.deep());
}
}通过上面介绍可知，子节点链表示法的特点是：每个节点都可以快速找到它的所有子节点。但如果要找某个节点的父节点则比较麻烦，程序要遍历整个节点数组。
二叉树
对于普通树来说，由于它需要遵循的规律太少，程序控制起来反而更加复杂，因此限制了它在实际应用中的使用。如果对普通树增加一些限制，让一棵树中最多只能包含 2 个子节点，而且严格区分左子节点、右子节点（左、右子节点的位置不能交换），这棵树就变成了二叉树。
二叉树的定义和基本概念
二叉树指的是每个节点最多只能有两个子数的有序树。通常左边的子树被称作“左子树”（left subtree），右边的子树被称为“右子树”（right subtree）。由此可见，二叉树依然是树，它是一种特殊的树。
二叉树的每个节点最多只有 2 颗子树（不存在度大于 2 的节点）。二叉树的子树有左、右之分，次序不能颠倒。
树和二叉树两个重要区别：
- 树中节点的最大度数没有限制，而二叉树节点的最大度数为 2，也就是说二叉树是节点的最大度数为 2 的树；
- 无序树的节点无左、右之分，而二叉树的节点有左、右之分，也就是说二叉树是有序树。
一颗深度为 k 的二叉树，如果它包含了 2^k-1 个节点，就把这颗二叉树称为满二叉树。满二叉树的特点是每一层上的节点数都是最大节点数，即各层节点数分别为 1、2、4、8、16……2^(k-1)。
一颗有 n 个节点的二叉树，按满二叉树的编号方式对它进行编号，若树中所有节点和满二叉树 1~n 编号完全一致，则称该树为完全二叉树。也就是说，如果一颗二叉树除最后一层外，就其余层的所有节点都是满的，并且最后一层要么是满的，要么仅再右边缺少若干连续的节点，则此二叉树就是完全二叉树。
满二叉树是一种特殊的完全二叉树，当完全二叉树最后一层的所有节点都是满的时，这颗完全二叉树就变成了满二叉树。
综上所述，二叉树大致有如下几个性质：
- 二叉树第 i 层上的节点数目至多为 2^(i-1)（i >= 1）；
- 深度为 k 的二叉树至多有 2^k-1 个节点。满二叉树的每层节点的数量依次是1、2、4、8……因此深度为 k 满二叉树包含的节点数为公比为 2 的等比数列的前 k 项总和，即 2^k-1；
- 再任何一颗二叉树中，如果其叶子节点的数量为 n0，度为 2 的子节点数量为 n2，则 n0=n2+1；
- 具有 n 个节点的完全二叉树的深度为 log(2)(n+1)；
对一颗有 n 个节点的完全二叉树的节点按层自左向右编号，则对任一编号为 i（n >= i >= 1）的节点有下列性质：
- 当 i==1 时，节点 i 是二叉树的根；若 i>1，则节点的节点是 i/2；
- 若 2i<=n，则节点 i 有左孩子，左孩子的编号是 2i，否则，节点无左孩子，并且叶子节点；
- 若 2i+1<=n，则节点 i 有右孩子，右孩子的编号是 2i+1；否则，节点无右孩子。
- 对一颗有 n 个节点的完全二叉树的节点按层自左向右编号，1~n/2 范围的节点都是有孩子节点的非叶子节点，其余的节点全部都是叶子节点。编号为 n/2 的节点可能只有左子节点，也可能既有左子节点，又有右子节点。
二叉树的基本操作
二叉树记录其节点之间的父子关系更加简单，因为二叉树中的每个节点最多只能保存 2 个子节点。接下来，程序也需要为二叉树实现如下基本操作：
- 初始化：通常是一个构造器，用于创建一个空的树，或者以指定节点为根来创建二叉树；
- 为指定节点添加子节点；
- 判断二叉树是否为空；
- 返回根节点；
- 返回指定节点（非根节点）的父节点；
- 返回指定节点（非叶子节点）的左子节点；
- 返回指定节点（非叶子节点）的右子节点；
- 返回该二叉树的深度；
- 返回指定节点的位置。
要实现二叉树这种数据结构，有以下 3 种选择：
- 顺序存储：采用数组来记录二叉树的所有节点；
- 二叉链表存储：每个节点保留一个 left、right 域，分别指向其左、右子节点；
- 三叉链表存储：每个节点保留一个 left、right、parent 域，分别指向其左、右子节点和父节点。
二叉树的顺序存储
顺序存储指的是充分利用满二叉树的特性————每层的节点树分别为 1、2、4、8……2^(i-1)，一颗深度为 i 的二叉树最多只能包含 2^i-1 个节点，因此只要定义一个长度为 2^i-1 的数组即可存储这颗二叉树。
对于普通二叉树（不是满的二叉树），那些空出来的节点对应的数组元素留空就可以了。由此可见，二叉树采用顺序存储会造成一定的空间浪费。
当使用数组来村粗二叉树的所有节点时可能为产生一定的空间浪费，如果该二叉树是完全二叉树，就不会有任何空间浪费；但如果该二叉树的所有节点都只有右子节点，那么就会产生相当大的空间浪费了。
掌握上面的理论之后，可以使用如下代码来实现一个顺序存储的二叉树：
public class ArrayBinTree<T> {
//使用数组来记录该树的所有节点
private Object[] datas;
private final int DEFAULT_DEEP = 8;
//保存该树的深度
private int deep;
private int arraySize;
//以默认的深度创建二叉树
public ArrayBinTree() {
this.deep = DEFAULT_DEEP;
this.arraySize = (int)Math.pow(2, deep) - 1;
datas = new Object[arraySize];
}
//以指定深度创建二叉树
public ArrayBinTree(int deep) {
this.deep = deep;
this.arraySize = (int)Math.pow(2, deep) - 1;
datas = new Object[arraySize];
}
//以指定深度创建、指定根节点创建二叉树
public ArrayBinTree(int deep, T data) {
this.deep = deep;
this.arraySize = (int)Math.pow(2, deep) - 1;
datas = new Object[arraySize];
datas[0] = data;
}
/**
* 为指定节点添加子节点
* @param index 需要添加子节点的父节点索引
* @param data 新子节点的数据
* @param left 是否为左节点
*/
public void add(int index, T data, boolean left) {
if (datas[index] == null) {
throw new RuntimeException(index + "处节点为空，无法添加子节点");
}
if (2 * index + 1 >= arraySize) {
throw new RuntimeException("树底层数组已满，树越界异常");
}
//添加左子节点
if (left) {
datas[2 * index + 1] = data;
} else {
datas[2 * index + 2] = data;
}
}
//判断二叉树是否为空
public boolean empty() {
//根据根源是判断二叉树是否为空
return datas[0] == null;
}
//返回根节点
public T root() {
return (T)datas[0];
}
//返回指定节点（非根节点）的父节点
public T parent(int index) {
return (T)datas[(index - 1) / 2];
}
//返回指定节点（非叶子节点）的左子节点，当左子节点不存在时返回null
public T left(int index) {
if (2 * index + 1 >= arraySize) {
throw new RuntimeException("该节点为叶子节点，无子节点");
}
return (T)datas[index * 2 + 1];
}
//返回指定节点（非叶子节点）的右子节点，当右子节点不存在时返回null
public T right(int index) {
if (2 * index + 1 >= arraySize) {
throw new RuntimeException("该节点为叶子节点，无子节点");
}
return (T)datas[index * 2 + 2];
}
//返回该二叉树的深度
public int deep(int index) {
return deep;
}
//返回指定节点的位置
public int pos(T data) {
//该循环实际上就是按广度遍历来搜索每个节点
for (int i = 0;i < arraySize;i++) {
if (datas[i].equals(data)) {
return i;
}
}
return -1;
}
@Override
public String toString() {
return java.util.Arrays.toString(datas);
}
}从上面介绍可以看出，顺序存储二叉树的思想就是将树中不同的节点存入数组的不同位置。比如，根节点，永远使用数组的第一个元素来保存；第 2 层的第 2 个节点，永远使用数组的第 3 个元素来保存；第 3 层最右边的节点，永远使用数组的第 7 个元素来保存……依次类推。
对于这种顺序存储的二叉树，不管是遍历树中节点，还是查找树中节点，都可以非常高效地完成，唯一的缺点是空间浪费很大。例如下面的测试成语，虽然只为该二叉树保存了 4 个节点，一样需要使用长度为 15 的数组。
public class ArrayBinTreeTest {
public static void main(String[] args) {
ArrayBinTree<String> binTree = new ArrayBinTree<>(4, "根");
binTree.add(0, "第二层右子节点", false);
binTree.add(2, "第三层右子节点", false);
binTree.add(6, "第四层右子节点", false);
System.out.println(binTree);
}
}上面程序中的二叉树只有 4 个节点，它们都是每层最右边的节点，因此程序依然需要长度为 15 的数组来保存该二叉树，而且底层数组最后一个数组元素也有值。运行上面程序，可以看到如下输出：
[根, null, 第二层右子节点, null, null, null, 第三层右子节点, null, null, null, null, null, null, null, 第四层右子节点]二叉树的二叉链表存储
二叉链表存储的思想是让每个节点都能“记住”它的左、右两个子节点。为每个节点增加 left、right 两个指针，分别引用该节点的左、右两个子节点。
二叉链表存储的二叉树的节点大致有如下定义：
class Node {
T data;
Node left;
Node right;
}对于这种二叉链表存储的二叉树，如果程序需要为指定节点添加子节点也非常容易，让父节点的 left、right 引用指向新节点即可。下面程序以二叉链表实现了二叉树：
public class TwoLinkBinTree<E> {
public static class TreeNode {
Object data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(Object data) {
this.data = data;
}
public TreeNode(Object data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
private TreeNode root;
//以默认的构造器创建二叉树
public TwoLinkBinTree() {
this.root = new TreeNode();
}
//以指定根元素创建二叉树
public TwoLinkBinTree(E data) {
this.root = new TreeNode(data);
}
/**
* 为指定节点添加子节点
* @param parent 需要添加子节点的父节点的索引
* @param data 新子节点的数据
* @param isLeft 是否为左节点
* @return 新增的节点
*/
public TreeNode addNode(TreeNode parent, E data, boolean isLeft) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null，无法添加子节点");
}
if (isLeft && parent.left != null) {
throw new RuntimeException("节点已经有左子节点，无法添加左子节点");
}
if (!isLeft && parent.right != null) {
throw new RuntimeException("节点已经有右子节点，无法添加右子节点");
}
TreeNode newNode = new TreeNode(data);
if (isLeft) {
//让父节点的left引用指向新节点
parent.left = newNode;
} else {
//让父节点的left引用指向新节点
parent.right = newNode;
}
return newNode;
}
//判断二叉树是否为空
public boolean empty() {
//根据根源是判断二叉树是否为空
return root.data == null;
}
//返回根节点
public TreeNode root() {
if (empty()) {
throw new RuntimeException("树为空，无法访问根节点");
}
return root;
}
//返回指定节点（非根节点）的父节点
public E parent(TreeNode node) {
//对于二叉树链表存储发，如果要访问指定节点的父节点必须遍历二叉树
return null;
}
//返回指定节点（非叶子节点）的左子节点，当左子节点不存在时返回null
public E leftChild(TreeNode parent) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null，无法添加子节点");
}
return parent.left == null ? null : (E)parent.left.data;
}
//返回指定节点（非叶子节点）的右子节点，当右子节点不存在时返回null
public E rightChild(TreeNode parent) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null，无法添加子节点");
}
return parent.right == null ? null : (E)parent.right.data;
}
//返回该二叉树的深度
public int deep() {
//获取该树的深度
return deep(root);
}
//这是一个递归方法，每颗子树的深度为其所有子树的最大深度 + 1
private int deep(TreeNode node) {
if (node == null) {
return 0;
}
//没有子树
if (node.left == null && node.right == null) {
return 1;
} else {
int leftDeep = deep(node.left);
int rightDeep = deep(node.right);
//记录其所有左、右子树中交大的深度
int max = leftDeep > rightDeep ? leftDeep : rightDeep;
//返回其左右子树中较大的深度 + 1
return max + 1;
}
}
}在上面程序中，二叉树中每个节点保留了 left、right 两个引用，分别指向该节点的左、右两个子节点。通过这种方式即可建立二叉树各节点之间的父子关系，下面程序测试了上面的二叉树：
public class TwoLinkBinTreeTest {
public static void main(String[] args) {
TwoLinkBinTree<String> binTree = new TwoLinkBinTree<>("根节点");
//依次添加节点
TwoLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root(), "第二层左节点", true);
TwoLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root(), "第二层右节点", false);
TwoLinkBinTree.TreeNode tn3 = binTree.addNode(tn2, "第三层左节点", true);
TwoLinkBinTree.TreeNode tn4 = binTree.addNode(tn2, "第三层右节点", false);
TwoLinkBinTree.TreeNode tn5 = binTree.addNode(tn3, "第四层左节点", true);
System.out.println("tn2的左子节点：" + binTree.leftChild(tn2));
System.out.println("tn2的右子节点：" + binTree.rightChild(tn2));
System.out.println(binTree.deep());
}
}对于这种二叉链表的二叉树，因为程序采用链表来记录树中所有节点，所以添加节点没有限制，而且不会像顺序存储那样产生大量的空间浪费。当然，这种二叉链表的存储方式再遍历树节点时效率不高，指定节点访问父节点时也比较困难，程序必须采用遍历二叉树的方式来搜索其父节点。
为了克服二叉链表存储方式中访问父节点不方便的问题，可以将二叉链表拓展成三叉链表。
二叉树的三叉链表存储
三叉链表存储的思想是让每个节点不仅“记住”它的左、右两个子节点，还“记住”它的父节点，因此需要为每个节点增加 left、right 和 parent 3 个指针，分别引用该节点的左、右两个节点和父节点。
二叉链表存储和三叉链表存储都是根据该二叉树的节点特征来划分的。对于二叉链表存储而言，二叉树的每个节点需要 2 个“分叉”，分别记录该节点的左、右 2 个子节点；对于三叉链表存储而言，二叉树的每个节点需要 3 个“分叉”，分别记录该节点的左、右 2 个子节点和父节点。
因此，三叉链表存储的二叉树的节点大致右如下定义：
class Node {
T data;
Node left;
Node right;
Node parent;
}对于这种三叉链表存储的二叉树，如果程序需要为指定节点添加子节点也非常容易，除了要维护父节点的 left、right 引用之外，还要维护新增节点的 parent 引用。下面程序以三叉链表实现了二叉树：
public class ThreeLinkBinTree<E> {
public static class TreeNode {
Object data;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode() {
}
public TreeNode(Object data) {
this.data = data;
}
public TreeNode(Object data, TreeNode left, TreeNode right, TreeNode parent) {
this.data = data;
this.left = left;
this.right = right;
this.parent = parent;
}
}
private TreeNode root;
//以默认的构造器创建二叉树
public ThreeLinkBinTree() {
this.root = new TreeNode();
}
//以指定根元素创建二叉树
public ThreeLinkBinTree(E data) {
this.root = new TreeNode(data);
}
/**
* 为指定节点添加子节点
* @param parent 需要添加子节点的父节点的索引
* @param data 新子节点的数据
* @param isLeft 是否为左节点
* @return 新增的节点
*/
public TreeNode addNode(TreeNode parent, E data, boolean isLeft) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null，无法添加子节点");
}
if (isLeft && parent.left != null) {
throw new RuntimeException("节点已经有左子节点，无法添加左子节点");
}
if (!isLeft && parent.right != null) {
throw new RuntimeException("节点已经有右子节点，无法添加右子节点");
}
TreeNode newNode = new TreeNode(data);
if (isLeft) {
//让父节点的left引用指向新节点
parent.left = newNode;
} else {
//让父节点的left引用指向新节点
parent.right = newNode;
}
//让新节点的parent引用到parent节点
newNode.parent = parent;
return newNode;
}
//判断二叉树是否为空
public boolean empty() {
//根据根源是判断二叉树是否为空
return root.data == null;
}
//返回根节点
public TreeNode root() {
if (empty()) {
throw new RuntimeException("树为空，无法访问根节点");
}
return root;
}
//返回指定节点（非根节点）的父节点
public E parent(TreeNode node) {
if (node == null) {
throw new RuntimeException(node + "节点为null，无法访问其父节点");
}
return (E)node.parent.data;
}
//返回指定节点（非叶子节点）的左子节点，当左子节点不存在时返回null
public E leftChild(TreeNode parent) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null，无法添加子节点");
}
return parent.left == null ? null : (E)parent.left.data;
}
//返回指定节点（非叶子节点）的右子节点，当右子节点不存在时返回null
public E rightChild(TreeNode parent) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null，无法添加子节点");
}
return parent.right == null ? null : (E)parent.right.data;
}
//返回该二叉树的深度
public int deep() {
//获取该树的深度
return deep(root);
}
//这是一个递归方法，每颗子树的深度为其所有子树的最大深度 + 1
private int deep(TreeNode node) {
if (node == null) {
return 0;
}
//没有子树
if (node.left == null && node.right == null) {
return 1;
} else {
int leftDeep = deep(node.left);
int rightDeep = deep(node.right);
//记录其所有左、右子树中交大的深度
int max = leftDeep > rightDeep ? leftDeep : rightDeep;
//返回其左右子树中较大的深度 + 1
return max + 1;
}
}
}从上面的程序可以看出，三叉链表存储方式是对二叉链表的一种改进，通过为树节点增加一个 parent 引用，可以让每个节点都能非常方便地访问其父节点。三叉链表存储的二叉树既可方便地向下访问节点，也可以方便地向上访问节点。
遍历二叉树
遍历二叉树指的是按某种规律依次访问二叉树的每个节点，对二叉树的遍历过程就是将非线性结构的热茶岁的节点排列在一个线性序列上的过程。
如果采用顺序结构来保存二叉树，程序遍历二叉树将非常容易，无需进行任何思考，直接遍历底层数组接口即可。如果采用链表来保存二叉树的节点，则有以下两类遍历方式。
- 深度优先遍历：这种遍历算法将先访问到树中最深的层次的节点；
- 广度优先遍历：这种遍历算法将逐层访问每层的节点，先访问根（第一层）节点，然后访问第二层的节点……依次类推。因此，广度优先遍历方法又被称为按层遍历。
对于深度优先的遍历算法而言，它又可分为以下 3 种。
- 先（前）序遍历二叉树；
- 中序遍历二叉树；
- 后序遍历二叉树。
如果 L、D、R 表示左子树、根、右子树，习惯上总是必须先遍历左子树，后遍历右子树，根据遍历根节点的顺序不同，上面 3 种算法可如下表示：
- DLR：先序遍历；
- LDR：中序遍历；
- LRD：后序遍历。
深度遍历的先序遍历、中序遍历、后序遍历这 3 种遍历方式的名称都是针对根节点（D）而言，而处理根节点（D）时就称为先序遍历，其次处理根节点（D）时就称为中序遍历，最后处理根节点（D）时就称为后序遍历。
因为二叉树的定义本身就有“递归性”，所以深度优先遍历时能非常方便地利用递归来遍历每个节点：一颗非空二叉树由树根、左子树和右子树组成，依次遍历这 3 部分，就可以变量整个二叉树。
先序遍历
先序遍历指先处理根节点，其处理顺序如下：
- 访问根节点；
- 递归遍历左子树；
- 递归遍历右子树。
实现先序遍历的方法如下：
public List<TreeNode> preIterator() {
return preIterator(root);
}
private List<TreeNode> preIterator(TreeNode node) {
List<TreeNode> list = new ArrayList<>();
//处理根节点
list.add(node);
if (node.left != null) {
list.addAll(preIterator(node.left));
}
if (node.right != null) {
list.addAll(preIterator(node.right));
}
return list;
}中序遍历
中序遍历指其次处理根节点，其处理顺序如下：
- 递归遍历左子树；
- 访问根节点；
- 递归遍历右子树。
实现中序遍历的方法如下：
public List<TreeNode> inIterator() {
return inIterator(root);
}
private List<TreeNode> inIterator(TreeNode node) {
List<TreeNode> list = new ArrayList<>();
//递归处理左子树
if (node.left != null) {
list.addAll(inIterator(node.left));
}
//处理根节点
list.add(node);
//递归处理右子树
if (node.right != null) {
list.addAll(inIterator(node.right));
}
return list;
}后序遍历
后序遍历指最后处理根节点。其处理顺序如下：
- 递归遍历左子树；
- 递归遍历右子树；
- 访问根节点。
实现后序遍历的方法如下：
public List<TreeNode> postIterator() {
return postIterator(root);
}
private List<TreeNode> postIterator(TreeNode node) {
List<TreeNode> list = new ArrayList<>();
//递归处理左子树
if (node.left != null) {
list.addAll(postIterator(node.left));
}
//递归处理右子树
if (node.right != null) {
list.addAll(postIterator(node.right));
}
//处理根节点
list.add(node);
return list;
}广度优先（按层）遍历
广度优先遍历又称为按层遍历，整个遍历算法先遍历二叉树的第一层（根节点），再遍历根节点的两个子节点（第二层）……以此类推，逐层遍历二叉树的所有节点。
为了实现广度遍历，可以借助于具有“FIFO”特征的队列来实现，如下所示。
- 建立一个队列（先进先出），把树的根节点压入队列；
- 从队列中弹出一个节点（第一次弹出的就是根节点），然后把该节点的左、右节点压入队列，如果没有子节点，则说明已经到达叶子节点了；
- 用循环重复执行第 2 步，直到队列为空。当队列为空时，说明所有的叶子节点（深度最深的层）都已经经过了队列，也就完成了遍历。
基于上面给定的思想，可以用如下程序来实现广度优先遍历。
//广度优先遍历
public List<TreeNode> breadthFirst() {
Queue<TreeNode> queue = new ArrayDeque<>();
List<TreeNode> list = new ArrayList<>();
if (root != null) {
//将根元素加入队列
queue.offer(root);
}
while (!queue.isEmpty()) {
//将该队列的“队尾”的元素加入到List中
list.add(queue.peek());
TreeNode p = queue.poll();
//如果左子节点不为null，将它加入队列
if (p.left != null) {
queue.offer(p.left);
}
//如果右子节点不为null，将它加入队列
if (p.right != null) {
queue.offer(p.right);
}
}
return list;
}从上面的代码可以看出，为了实现二叉树的广度遍历，程序借助一个 Queue 对象，这是从 JDK1.5 提供的一个队列接口。通过这个队列接口，可以非常方便地对二叉树实现广度优先遍历。
森林、树和二叉树的转换
由于二叉树是一种更“确定”（它的每个节点最多只有 2 个子节点）的数据结构，因此不管是存储、增加、删除节点，还是遍历节点，程序都可以更简单、方便地实现。反之，由于树的每个节点具有个数不确定的子节点，因此程序实现起来更复杂。
为了充分利用二叉树的简单易用性，可以将普通树转换为二叉树，以二叉树的形式来保存普通树，当程序需要树时，再将二叉树转换为普通树。
森林其实更简单，如果将一颗普通树的根节点去掉，这棵树就变成了森林。或者可以转换一下思维，森林其实就是有多个根节点的树。
森林、树和二叉树之间的转换
有序树、森林和二叉树之间有一一映射关系，可以进行相互转换。
多叉树向二叉树转换的方法如下：
- 加虚线：同一个父节点的相邻兄弟节点之间加虚线；
- 抹实线：每节点只保留它与最左子节点的连线，与其它子节点的连线都被抹掉；
- 旋改实：虚线改为实线。
多叉树转二叉树的方法关键思想就是：所有子节点只保留子节点，其它节点转为左子节点的右子节点链。
按照这种转换思路，森林也可以转换为二叉树————只要把森林当成一颗根节点被删除的多叉树。
反过来，二叉树也可恢复出对应的多叉树、森林，恢复方法如下：
- 加虚线：若某节点 I 是父节点的左子节点，则将该节点 I 的右孩子链的所有节点分别与节点 I 的父节点添加连线；
- 抹线：把所有虚线的节点与原父节点的连线抹去；
- 整理：虚改实并按层排列。
如果二叉树的根节点有右子节点————右子节点就代表是根节点的兄弟节点，这种情况会转换得到森林。
树的链式存储
根据上面介绍的理论，二叉树可以在多叉树之间进行自由转换，因此可以得到普通树的另外一种保存方式：以二叉树的形式来保存多叉树，实际需要的时候再将二叉树转换为普通树。
至于到底以哪种方式来保存二叉树，完全是自由的。通常会选择使用三叉链表存储来保存二叉树，这样得到的二叉树操作起来更方便，进行二叉树和多叉树之间转换时也更方便。
哈夫曼树
哈夫曼树又被称为最优二叉树，是一类带权路径最短的二叉树。哈夫曼树是二叉树的一种应用，再信息检索中很常用。
哈夫曼树的定义和基本概念
介绍哈夫曼树之前闲来介绍一些相关的概念
- 节点之间的路径长度：从一个节点到另一个节点之间的分支数量称为两个节点之间的路径长度；
- 树的路径长度：从根节点到树中每一个节点的路径长度之和。
- 节点的带权路径长度：从该节点到根节点之间的路径长度与节点上权的乘积；
- 树的带权路径长度：树中所有叶子节点的带权路径长度之和。
带权路径最小的二叉树被称为哈夫曼树或最优二叉树。
对于哈夫曼树，有一个很重要的定理：对于具有 n 个叶子节点的哈夫曼树，一共需要 2*n-1 个节点。因为对于二叉树来说，有 3 种类型节点，即度数为 2 的节点、度数为 1 的节点和度数为 0 的叶节点，而哈夫曼树的非叶子节点都是由两个节点合并产生，所以不会出现度数为 1 的节点。而生成的非叶子节点的个数为叶子节点个数 -1，因此 n 个叶子节点的哈夫曼树，一共需要 2*n-1 个节点。
创建哈夫曼树
创建哈夫曼树，可以按如下步骤进行：
- 根据给定的 n 个权值｛w1,w2,……,wn｝构造 n 颗二叉树的集合 F = ｛T1,T2,……,Tn｝，F 集合中每颗二叉树都只有一个根节点；
- 选取 F 集合中每颗根节点的权值最小的树作为左、右子树以构造一颗新的二叉树，且将新的二叉树的根节点的权值设为左、右子树上根节点的权值之和；
- 将新的二叉树加入到 F 集合中，并删除 2 步中被选中的两棵树；
- 重复 2 和 3 步直到 F 集合只剩下一棵树，这棵树就是哈夫曼树。
基于上面思想，对指定节点集合创建哈夫曼树，示例如下：
public class HuffmanTree {
public static class Node<E> {
E data;
double weight;
Node leftChild;
Node rightChild;
public Node(E data, double weight) {
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "Node[data=" + data + ", weight=" + weight + "]";
}
}
public static void main(String[] args) {
List<Node> nodes = new ArrayList<>();
nodes.add(new Node("A", 40.0));
nodes.add(new Node("B", 8.0));
nodes.add(new Node("C", 10.0));
nodes.add(new Node("D", 30.0));
nodes.add(new Node("E", 10.0));
nodes.add(new Node("F", 2.0));
Node root = HuffmanTree.createTree(nodes);
System.out.println(breadthFirst(root));
}
/**
* 构造哈夫曼树
* @param nodes 节点集合
* @return 构造出来的韩服满树的更节点
*/
private static Node createTree(List<Node> nodes) {
//只要还有nodes数组中还有两个以上的节点
while (nodes.size() > 1) {
quickSort(nodes);
//获取权值最小的两个节点
Node left = nodes.get(nodes.size() - 1);
Node right = nodes.get(nodes.size() - 2);
//生成新节点，新节点的权值为两个子节点的权值之和
Node parent = new Node(null, left.weight + right.weight);
//让新节点作为权值最小的两个节点的父节点
parent.leftChild = left;
parent.rightChild = right;
//删除权值最小的两个节点
nodes.remove(nodes.size() - 1);
nodes.remove(nodes.size() - 2);
//将新生成的父节点添加到集合中
nodes.add(parent);
}
//返回nodes集合中唯一的节点，也就是根节点
return nodes.get(0);
}
//将指定数组的 i 和 j 索引处的元素交换
private static void swap(List<Node> nodes, int i, int j) {
Node tmp = nodes.get(i);
nodes.set(i, nodes.get(j));
nodes.set(j, tmp);
}
//实现快速排序算法，用于对节点进行排序
private static void subSort(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) {
i++;
}
//找到小于分界值的元素的索引，或者j已经到了start处
while (j > start && nodes.get(j).weight <= base.weight) {
j--;
}
if (i < j) {
swap(nodes, i, j);
} else {
break;
}
}
swap(nodes, start, j);
//递归左边子序列
subSort(nodes, start, j - 1);
//递归右边子序列
subSort(nodes, j + 1, end);
}
}
public static void quickSort(List<Node> nodes) {
subSort(nodes, 0, nodes.size() - 1);
}
//广度优先遍历
public static List<Node> breadthFirst(Node root) {
Queue<Node> queue = new ArrayDeque<>();
List<Node> list = new ArrayList<>();
if (root != null) {
//将根元素入队列
queue.offer(root);
}
while (!queue.isEmpty()) {
//将该队列的队尾的元素添加到List中
list.add(queue.peek());
Node p = queue.poll();
//如果左子节点不为null，将它加入队列
if (p.leftChild != null) {
queue.offer(p.leftChild);
}
//如果右子节点不为null，将它加入队列
if (p.rightChild != null) {
queue.offer(p.rightChild);
}
}
return list;
}
}上面的程序完成了如下事情：
- 对 List 集合中所有节点进行排序；
- 找出 List 集合中权值最小的两个节点；
- 以权值最小的两个节点作为子节点创建新节点；
- 从 List 集合中删除权值最小的两个节点，将新节点添加到 List 集合中。
程序采用循环不断地执行上面 1、2、3、4 步，直到 List 集合中只剩下一个节点，最后剩下的这个节点就是哈夫曼树的根节点。
哈夫曼编码
根据哈夫曼树可以解决报文编码问题。假设需要把一个字符串如“abcdabcaba”进行编码，将它转换成唯一的二进制码，但要求转换出来的二进制码最小。
假设每个字符再字符串中出现的频率为 W，其编码长度为 L，编码字符 n 个，则编码后二进制码的长度整为 W1L1 + W2L2 + W3L3 + …… + WnLn，这正好复合哈夫曼树的处理原则。因此可采用哈夫曼树的原理构造二进制编码，并使电文长度最短。
对于“abcdabcaba”字符串，总共只有 a、b、c、d 4 个字符，它们出现的次数分别是 4、3、2、1 次————这相当于它们的权值。于是，将 a、b、c、d 4 个字符以出现次数的权值构造哈夫曼树如下所示：
()
/\
a ()
/\
b ()
/\
c d从哈夫曼树根节点开始，对左子树分配代码“0”，对右子树分配代码“1”，一直到达叶子节点。然后，将从树沿每条路径到达叶子节点的代码排列起来，便得到了每个叶子节点的哈夫曼编码。示例如下：
()
0/\1
/ \
a ()
0 0/\1
/ \
b ()
10 0/\1
/ \
c d
110 111从上面可以看出，a 的哈夫曼编码为 0、b 的哈夫曼编码为 10，c 的哈夫曼编码为 110，d 的哈夫曼编码为 111。然后将“abcdabcaba”这个字符串转换为对应的二进制编码为 0101101110101100100，长度仅为 19。这就是该字符串的最短二进制编码，也被称为哈夫曼编码。
根据上面介绍的规律不难发现，哈夫曼编码有一个规律：假设有 N 个叶子节点需要编码，最终得到的哈夫曼树一定有 N 层，哈夫曼编码的到的二进制码的最大长度为 N-1。
程序将 N 个叶子节点按权值由小到大排列，这些叶子节点对应的哈夫曼编码依次为 0、10、110、1110、……、11…10、11…11（一共有 N-1 位）。
排序二叉树
排序二叉树是一种特殊结构的二叉树，通过它可以非常方便地对树中所有节点依次排序和检索。
排序二叉树要么是一颗空二叉树，要么是具有以下性质的二叉树。
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 它的左、右子树也分别为排序二叉树。
10
/ \
/ \
3 18
/\ /\
/ \ / \
2 4 13 21
\
\
9
/\
/ \
8 9对于上面的排序二叉树，对排序二叉树，若按中序遍历就可以得到由小到大的有序序列：｛2, 3, 4, 8, 9, 9, 10, 13, 15, 18｝
创建排序二叉树的步骤，就是不断地向排序二叉树添加节点的过程，具体如下：
- 以根节点为当前节点开始搜索；
- 拿新节点的值和当前节点的值比较；
- 如果新节点的值更大，则以当前节点的右子节点作为新的当前节点；如果新节点的值更小，则以当前节点的左子节点作为新的当前节点；
- 重复 2、3 两个步骤，直到搜索到合适的叶子节点；
- 将新节点添加为第 4 步找到的叶子节点的子节点，如果新节点更大，则添加为右子节点；否则，加为左子节点。
当程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序二叉树，必须对该排序二叉树进行维护。维护颗分为如下几种情况：
- 被删除的节点是叶子节点，只需要将它从父节点中删除；
- 被删除节点 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 节点。）
被删除节点只有左子树的情况示例：
18 18
/ \ / \
/ \ / \
12 30(删除该节点) 12 23
\ / \ \
\ / \ \
14 23 14 26
/ \ /
/ \ /
13 26 13被删除节点只有右子树的情况示例：
18 18
/ \ / \
/ \ / \
12(删除) 30 14 30
\ / / /
\ / / /
14 23 13 23
/ \ \
/ \ \
13 26 26被删除节点既有左子节点，又有右子节点的情形。此时采用第 1 种方式进行维护。示例：
5 5
/ \ / \
/ \ / \
3 20(删除) 3 10
/ \ / \
/ \ / \
10 30 8 15
/\ \
/ \ \
8 15 30被删除节点既有左子树，又有右子树的情形。此时采用第 2 种方式进行维护。示例：
5 5
/ \ / \
/ \ / \
3 15(删除) 3 30
/ \ /
/ \ /
10 30 10
/ / \
/ / \
8 8 15掌握上面理论之后，使用如下 Java 程序来实现排序二叉树。实现排序二叉树的删除节点采用上面第 2 种方式进行维护，也就是用被删除节点的左子树中最大节点与被删除节点交换的方式进行维护。
public class SortBinTree<T extends Comparable> {
static class Node {
Object data;
Node parent;
Node left;
Node right;
public Node(Object data, Node parent, Node left, Node right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "[data=" + data + "]";
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj.getClass() == Node.class) {
Node target = (Node)obj;
return data.equals(target.data)
&& left == target.left
&& right == target.right
&& parent == target.parent;
}
return false;
}
}
private Node root;
//两个构造器用于创建排序二叉树
public SortBinTree() {
root = null;
}
public SortBinTree(T o) {
root = new Node(o, null, null, null);
}
//添加节点
public void add(T ele) {
//如果根节点为null
if (root == null) {
root = new Node(ele, null, null, null);
} else {
Node current = root;
Node parent = null;
int cmp = 0;
//搜索合适的叶子节点，以该叶子节点为父节点添加新节点
do {
parent = current;
cmp = ele.compareTo(current.data);
//如果新节点的值大于当前节点的值
if (cmp > 0) {
//以右子节点作为当前节点
current = current.right;
} else {
//以左子节点作为当前节点
current = current.left;
}
} while (current != null);
//创建新节点
Node newNode = new Node(ele, parent, null, null);
//如果新节点的值大于父节点的值
if (cmp > 0) {
//新节点作为父节点的右子节点
parent.right = newNode;
//如果新节点的值小于父节点的值
} else {
//新节点作为父节点的左子节点
parent.left = newNode;
}
}
}
//删除节点
public void remove(T ele) {
//获取要删除的节点
Node target = getNode(ele);
if (target == null) {
return;
}
//左、右子树为空
if (target.left == null && target.right == null) {
//被删除节点是根节点
if (target == root) {
root = null;
} else {
//被删除节点是父节点的左子节点
if (target == target.parent.left) {
//将target的父节点的left改为null
target.parent.left = null;
} else {
//将target的父节点的right设为null
target.parent.right = null;
}
target.parent = null;
}
//左子树为空，右子树不为空
} else if (target.left == null && target.right != null) {
//被删除的是根节点
if (target == root) {
root = target.right;
} else {
//被删除节点是父节点的左子节点
if (target == target.parent.left) {
//让target的父节点的left指向target的右子树
target.parent.left = target.right;
} else {
//让target的父节点的right指向target的右子树
target.parent.right = target.right;
}
//让target的右子树的parents指向target的parent
target.right.parent = target.parent;
}
//左子树不为空，右子树为空
} else if (target.left != null && target.right == null) {
//被删除节点是根节点
if (target == root) {
root = target.left;
} else {
//被删除节点是父节点的左子节点
if (target == target.parent.left) {
//让target的父节点的left指向target的左子树
target.parent.left = target.left;
} else {
//让target的父节点的right指向target的左子树
target.parent.right = target.left;
}
//让target的左子树的parent指向target的parent
target.left.parent = target.parent;
}
//左、右子树都不为空
} else {
//leftMaxNode用于保存target节点的左子树中值最大的节点
Node leftMaxNode = target.left;
//搜索target节点的左子树中值最大的节点
while (leftMaxNode.right != null) {
leftMaxNode = leftMaxNode.right;
}
//从原来的子树中删除leftMaxNode节点
leftMaxNode.parent.right = null;
//让leftMaxNode的parent指向target的parent
leftMaxNode.parent = target.parent;
//被删除节点是父节点的左子节点
if (target == target.parent.left) {
//让target的父节点的left指向leftMaxNode
target.parent.left = leftMaxNode;
} else {
//让target的父节点的right指向leftMaxNode
target.parent.right = leftMaxNode;
}
leftMaxNode.left = target.left;
leftMaxNode.right = target.right;
target.parent = target.left = target.right = null;
}
}
//根据给定的值搜索节点
public Node getNode(T ele) {
//从根节点开始搜索
Node p = root;
while (p != null) {
int cmp = ele.compareTo(p.data);
//如果搜索的值小于当前p节点的值
if (cmp < 0) {
//向左子树搜索
p = p.left;
//如果搜索的值大于当前p节点的值
} else if (cmp > 0) {
//向右子树搜索
p = p.right;
} else {
return p;
}
}
return null;
}
//广度遍历优先
public List<Node> breadthFirst() {
Queue<Node> queue = new ArrayDeque<>();
List<Node> list = new ArrayList<>();
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 class SortBinTreeTest {
public static void main(String[] args) {
SortBinTree<Integer> tree = new SortBinTree<>();
//添加节点
tree.add(5);
tree.add(20);
tree.add(10);
tree.add(3);
tree.add(8);
tree.add(15);
tree.add(30);
System.out.println(tree.breadthFirst());
//删除节点
tree.remove(20);
System.out.println(tree.breadthFirst());
}
}运行上面的程序，可以看到如下的结果：
data=5], [data=3], [data=20], [data=10], [data=30], [data=8], [data=15
data=5], [data=3], [data=15], [data=10], [data=30], [data=8采用广度优先法则来遍历排序二叉树得到的不是有序序列，采用中序遍历来遍历排序二叉树时才可以得到有序序列。
红黑树
排序二叉树虽然可以快速检索，但在最坏的情况下，如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插入节点集本身是由大到小排列），或者所有节点只有右节点（如果插入节点集合本身由小到大排列）。在这种情况下，排序二叉树就变成了普通链表，其检索效率就会很差。
为了改变排序二叉树存在的不足，Rudolf Bayer 于 1972 年发明了另一种改进后的排序二叉树————红黑树，他将这种排序二叉树称为“对称二叉 B 树”，而红黑树这个名字则由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。
红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型地，JDK 提供的集合类 TreeMap 本身就是一个红黑树的实现。
红黑树在原有的排序二叉树上增加了如下几个要求。
- 性质 1：每个节点要么是红色，要么是黑色；
- 性质 2：根节点永远是黑色的；
- 性质 3：所有的叶子节点都是空节点（即 null），并且是黑色的；
- 性质 4：每个红色节点的两个子节点都是黑色（从每个叶子到根的路径上不会有两个连续的红色节点）；
- 性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
上面的性质 3 中指定红黑树的每个叶子节点都是空节点，并且叶子节点都是黑色，但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而每个叶子节点都是红色的。
Java 中实现的红黑树可能是如下的结构：
13(黑)
/ \
/ \
9(红) 18(红)
/ \ / \
/ \ / \
5(黑) 10(黑) 16(黑) 25(黑)
/ \ / \ / \ / \
/ \ null(黑) null(黑) / \ / \
null(黑) 8(红) null(黑) null(黑) 23(红) 30(红)
/ \ / \ / \
/ \ / \ / \
null(黑) null(黑) null(黑) null(黑) null(黑) null(黑)根据性质 5，红黑树从根节点到每个根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）”。
性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其它路径的两倍。加入有一颗黑色高度为 3 的红黑树，从根节点到叶子节点的最短路径长度是 2，该路径上全是黑色节点（黑节点-黑节点-黑节点）。最长路径路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点-红节点-黑节点-红节点-黑节点），性质 4 保证绝不可能插入更多的红色节点。由此可见，红黑树中最长的路径就是一条红黑交替的路径。
由此可以得出结论：对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1，最长路径长度为 2*(N-1)。
排序二叉树的深度直接影响了检索的性能，正如前面指出的，当插入节点本身就是由小到大排列时，排序二叉树将变成一个链表，这种排序二叉树的检索性能最低：N 个节点的二叉树深度就是 N-1。
红黑树通过上面这种限制来保证它大致是平衡的————因为红黑树的高度不会无限增高，这样能保证红黑树在最坏情况下都是高效的，不会出现普通排序二叉树的情况。
红黑树并不是真正的平衡二叉树，但在实际应用中，红黑树的统计性能要高于平衡二叉树，但极端性能略差。
由于红黑树只是一个特殊的排序二叉树，因此对红黑树的只读操作与普通二叉树上的只读操作完全相同，只是红黑树保持了大致平衡，因此检索性能更好。
但在红黑树进行插入操作和删除操作会导致树不再复合红黑树的特征。因此插入操作和删除操作都需要进行一定的维护，以保证插入节点、删除节点后的树依然是红黑树。
插入操作
插入操作按如下步骤进行。
排序二叉树的方法插入新节点，并将它设为红色。
如果设为黑色，就会导致根节点到叶子节点的路径上多一个额外的黑节点，这样将会导致很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点，再通过颜色调换和树旋转来调整即可。
进行颜色调换
这种颜色调用和树旋转就比较复杂了，下面将分情况进行介绍。在介绍中，把新插入的节点定义为 N 节点，把 N 节点的父节点定义为 P 节点，把 P 节点的兄弟节点定义为 U 节点，把 P 节点父节点定义为 G 节点。在插入操作中，红黑树的性质 1 和性质 3 永远不会发生改变，因此无需考虑红黑树的这两个特征。
- 情形 1：新节点 N 是树的根节点，没有父节点。
在这种情形下，直接将它设置为黑色以满足性质 2。 - 情形 2：新节点的父节点 P 是黑色。
在这种情况下，新插入的节点是红色的，因此依然满足性质 4。而且因为新节点 N 有两个黑色叶子节点，但是由于新节点 N 是红色，通过它的每个子节点的路径依然保持相同的黑色节点数，因此依然满足性质 5。 - 情形 3：如果父节点 P 和父节点的兄弟节点 U 都是红色。
在这种情况下，程序应该将 P 节点、U 节点都设置为黑色，并将 P 节点的父节点设为红色（用来保持性质 5）。现在，新节点 N 有了一个黑色的父节点 P。由于从 P 节点、U 节点到根节点的任何路径都必须通过 G 节点，这些路径上的黑节点数目没有改变（原来有叶子和 G 节点两个黑色节点，现在有叶子和 P 两个黑色节点）。
经过上面处理后，红色的 G 节点的父节点也有可能是红色的，这就违反了性质 4，因此还需要对 G 节点递归进行整个过程（把 G 当成新插入的节点进行处理）。 - 父节点 P 是红色，而其兄弟节点 U 是黑色或缺少；且新节点 N 是父节点 P 的右子节点，而父节点 P 又是其父节点 G 的左子节点。
在这种情形下，对新节点和其父节点进行一次左旋转。接着，按情形 5 处理以前的父节点 P（也就是把 P 当成新插入的节点）。这将导致某些路径通过它们以前不通过的新节点 N 或父节点 P 其中之一，但是这两个节点都是红色的，因此不会影响性质 5。 - 情形 5：父节点 P 是红色，而其兄弟节点 U 是黑色或缺少；且新节点 N 是其父节点的左子节点，而父节点 P 又是其父节点 G 的左子节点。
在这种情形下，需要对节点 G 进行依次右旋转。在旋转产生的树中，以前的父节点 P 现在是新节点 N 和节点 G 的父节点。由于以前的节点 G 是黑色（否则父节点 P 就不可能是红色），切换以前的父节点 P 和节点 G 的颜色，使之满足性质 4。性质 5 也仍然保持满足，因为通过这 3 个节点中任何一个的所有路径以前都通过节点 G，现在它们都通过以前的父节点 P。在各自的情形下，这都是 3 个节点中唯一的黑色节点。
- 情形 1：新节点 N 是树的根节点，没有父节点。
删除操作
红黑树的删除操作比插入操作要更复杂一些，实际上也可按如下步骤进行。
- 以排序二叉树的方法删除指定节点
- 进行颜色调换和树旋转，使之满足红黑树特征。
关于删除节点后要进行的颜色调换和树旋转中各种情况的处理，可以参考插入操作的介绍，此处不再一一列举。
本文转载自：《疯狂Java 突破程序员基本功的16课》第十一章 树和二叉树