Java 基础之数据结构：树

现在面试问 MySQL、红黑树好像都是必备问题了。动不动就让手写红黑树或者简单介绍下红黑树。然而，我们如果直接去看红黑树，可能会一下子蒙了。在看红黑树之前，需要先了解下树的基础知识，从简单到复杂，看看红黑树是在什么场景下出现的，是哪种东西。

本文主要是介绍二叉树、二叉搜索树，然后到高度平衡二叉树，根据树的基本操作和特点，帮助理解那些特殊结构的树，是怎样演化而来的。

二叉树（Binary tree）基本概念

二叉树（Binary tree）是树形结构的一个重要类型。看它这名字，就是最多有俩叉的一种特殊的树形结构。通常，它的俩叉分别叫做“左子树”和“右子树”。

对二叉树的结构定义如下：

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }
}

二叉树的遍历

binary_tree

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。 例如，对于如上图二叉树，访问的先后顺序依次是：FBADCEGIH。 下面使用简单递归来写个：

//前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        generate(root, result);
        return result;
    }

    private void generate(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        if (root.left == null && root.right == null) {
            return;
        }
        if (root.left != null) {
            generate(root.left, result);
        }
        if (root.right != null) {
            generate(root.right, result);
        }
    }

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。 例如，对于如上图二叉树，访问的先后顺序依次是：ABCDEFGHI。