我们知道，链表是一种线性递归的数据结构。前一个结点指向后一个结点，线性地链接起来。树跟链表类似，只不过树的结点与结点之间，不再是单个线性地链接，而是一个结点可以指向多个其他结点。

什么是树

树的相关术语

• 根节点：根节点是一个没有双亲结点的结点，一棵树中最多有一个根节点
• 边：双亲结点到孩子结点的链接
• 叶子结点：没有孩子结点的结点
• 兄弟结点：拥有相同双亲结点的所有孩子结点
• 祖先结点：如果存在一条从根节点到结点q的路径，其结点p出现在这条路径上，那么就可以吧结点p叫作结点q的祖先结点，结点q也叫做p的子孙结点
• 结点的大小：结点的大小是指子孙的个数，包括其自身
• 树的层：位于相同深度的所有结点的集合叫作树的层
• 结点的深度：是指从根节点到该节点的路径长度（上图G点的深度为2，A—C—G）
• 结点的高度：结点到树中最深结点的路径长度，只含有根节点的树的高度为0。（B的高度为2，B—F—J）

---

二叉树

如果一棵树中所有的结点都只有0，1 或者 2个孩子结点，那么这棵树就是二叉树。

二叉树的应用

• 编译器中的表达式树
• 用于数据压缩算法中的赫夫曼编码树
• 支持在集合中查找、插入和删除，其平均时间复杂度为O(lognn)的二叉搜索树（BST）
• 优先队列（PQ），它支持以对数时间（最坏情况下）对集合中的最小（或最大）数据元素进行搜索和删除

遍历二叉树

访问树中所有结点的过程叫作树的遍历。如果用递归的思想去进行遍历就不难理解了。

前序遍历

前序遍历的规则如下：

1. 访问根节点；
2. 按前序遍历方式遍历左子树；
3. 按前序遍历方式遍历右子树.

上图使用前序遍历的结果为： 1 2 4 5 3 6 7

void preOrder(BinaryTreeNode root) {
    if (null != root) {
        System.out.println(root.getData());
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }
}

中序遍历

中序遍历的规则如下：

1. 按中序遍历方式遍历左子树；
2. 访问根节点；
3. 按中序遍历方式遍历右子树.

上图使用中序遍历的结果为：4 2 5 1 6 3 7

void inOrder(BinaryTreeNode root) {
    if (null != root) {
        inOrder(root.getLeft());
        System.out.println(root.getData());
        inOrder(root.getRight());
    }
}

后序遍历

后序遍历的规则如下：

1. 按后序遍历方式遍历左子树；
2. 按后序遍历方式遍历右子树；
3. 访问根节点.

上图使用后序遍历的结果为：4 5 2 6 7 3 1

void postOrder(BinaryTreeNode root) {
    if (null != root) {
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.println(root.getData());
    }
}

---

二叉搜索树(BST)

二叉搜索树，又称二叉查找树（Binary Search Tree, BST），是一种所有左子树结点的元素小于根节点的数据，所有右子树结点的元素大于根节点数据的二叉树。