树

树的概念

二叉树的物理存储结构

二叉树可以使用以下两种物理结构表达：

• 链式存储结构
• 数组

使用链式存储结构表述二叉树

使用数组表述二叉树

二叉树的特殊形式

二叉树在实际应用时有许多特殊形式，主要时为了方便进行查找操作和维持相对顺序这两个操作。

查找

二叉查找树
**
又名：二叉搜索树、二叉排序树。具有以下几个条件：

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
• 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
• 左、右子树也都是二叉查找树

  维持相对顺序

  涉及知识点：二叉树的自平衡。
  二叉树的自平衡的方式有许多种，如红黑树、AVL树以及树堆等。

  二叉树的遍历

  以下图二叉树的遍历为例：
  

  深度优先遍历

  前序遍历

  遍历顺序：根节点 -> 左子树 -> 右子树

  输出：1 -> 2 -> 4 -> 5 -> 3 -> 6

中序遍历

遍历顺序：左子树 -> 根节点 -> 右子树

输出：4 -> 2 -> 5 -> 1 -> 3 -> 6

后序遍历

遍历顺序：左子树 -> 右子树 -> 根节点

输出：4 -> 5 -> 2 -> 6 -> 3 -> 1

代码表示(递归实现)

    /**
     * 构建二叉树
     *
     * @param inputList 输入序列，链表的顺序恰好为二叉树前序遍历的顺序
     * @return 构建好的二叉树
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
            node = new TreeNode(data);
            node.left = createBinaryTree(inputList);
            node.right = createBinaryTree(inputList);
        }
        return node;
    }
    /**
     * 前序遍历：根节点 -> 左子树 -> 右子树
     * tip:递归实现
     * @param node
     */
    public static void preOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        System.out.println(node.val);
        preOrderTraveral(node.left);
        preOrderTraveral(node.right);
    }
    /**
     * 中序遍历：左子树 -> 根节点 -> 右子树
     * tip:递归实现
     * @param node
     */
    public static void inOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        inOrderTraveral(node.left);
        System.out.println(node.val);
        inOrderTraveral(node.right);
    }
    /**
     * 后序遍历：左子树 -> 右子树 -> 根节点
     * tip:递归实现
     * @param node
     */
    public static void postOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        postOrderTraveral(node.left);
        postOrderTraveral(node.right);
        System.out.println(node.val);
    }
    /**
     * 二叉树节点类
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

除递归实现二叉树的前序遍历、中序遍历、后序遍历外，还可使用 栈 来完成这一过程。

广度优先遍历

层序遍历

输出：1 -> 2 -> 3 -> 4 -> 5 -> 6