常见术语

• 根节点：位于二叉树顶层的节点，没有父节点
• 叶节点：没有子节点的节点（度为0的节点），其两个指针均指向None
• 森林：由m(m>0)棵互不相交的树的集合
• 无序树：树中任意节点的子节点之间没有顺序关系
• 有序树：树中任意节点的子节点之间有顺序关系
• 二叉树：每个节点最多含有2个子树的树
• 边：连接两个节点的线段，即节点引用(指针)
• 节点所在的层:从顶到底递增，根节点所在的层为1
• 节点的度:节点的子节点的数量。在二叉树中，度的取值范围是0、1、2
• 树的度: 一棵树中，最大的节点的度称为树的度
• 二叉树的高度:从根节点到最远叶节点所经过的边的数量
• 节点的深度:从根节点到该节点所经过的边的数量
• 树的深度:从根节点到树中最深叶子节点的最长路径上的节点数(只有根节点的树深度为1)
• 节点的高度:从距离该节点最远的叶节点到该节点所经过的边的数量

WARNING

上面这个高度和深度，具体是以边来计算还是以节点来计算，似乎不太一致。 但都是从1开始计算的

高度的计算是从山脚开始往上量的
深度的计算是从山顶开始往下量的

演示图

Preview

二叉树类型

• 完美二叉树(满二叉树)：除了叶子节点，其他节点度都为2
• 完全二叉树：只有叶子节点没填满，且叶子节点都靠最左
• 完满二叉树：除了叶子节点，其他节点都有2个节点（没有度为1的节点）
• 平衡二叉树：任意节点左子树和右子树高度差绝对值不超过1
• 二叉搜索树：任意节点满足左子树中所有节点的值<父节点的值<右子树中所有节点的值
• AVL树（平衡二叉搜索树）：即是平衡二叉树又是二叉搜索树
• 红黑树
• B树(不是二叉树)
• B+树(不是二叉树)

二叉树的性质

Preview

数组表示下的二叉树

package dataStructure.树;

import java.util.ArrayList;
import java.util.List;

// 数组表示下的二叉树类
public class ArrayBinaryTree {
    private List<Integer> tree;

    public ArrayBinaryTree(List<Integer> arr) {
        tree = new ArrayList<>(arr);
    }

    // 列表容量
    public int size() {
        return tree.size();
    }

    // 获取索引为i节点的值
    public Integer val(int i) {
        if (i<0 || i>= size()) return null;
        return tree.get(i);
    }

    // 获取索引为i节点的左子节点的索引
    public Integer left(int i) {
        return 2 * i + 1;
    }

    // 获取索引为i节点的右子节点的索引
    public Integer right(int i) {
        return 2 * i + 2;
    }

    // 获取索引为i节点的父节点的索引
    public Integer parent(int i) {
        return (i - 1) / 2;
    }

    // 层序遍历(因为是数组表示的，直接遍历数组就行了)
    public List<Integer> levelOrder() {
        List<Integer> res = new ArrayList<>();
        for (int i=0;i<size();i++) {
            if (val(i) != null) res.add(val(i));
        }
        return res;
    }

    // 深度优先遍历
    private void dfs(Integer i, String order, List<Integer> res) {
        // 如果是空位，则返回
        if (val(i) == null) return;
        // 前序遍历
        if ("pre".equals(order)) res.add(val(i));
        dfs(left(i), order, res);
        // 中序遍历
        if ("in".equals(order)) res.add(val(i));
        dfs(right(i), order, res);
        // 后序遍历
        if ("post".equals(order)) res.add(val(i));
    }

    // 前序遍历
    public List<Integer> preOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "pre", res);
        return res;
    }

    // 中序遍历
    public List<Integer> inOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "in", res);
        return res;
    }

    // 后序遍历
    public List<Integer> postOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "post", res);
        return res;
    }
}

树的遍历

广度优先（层序遍历）

借助“队列”实现

package dataStructure.树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class binary_tree_bfs {

    // 广度优先搜索，层序遍历
    List<Integer> levelOrder(TreeNode root) {
        // 初始化队列，加入根节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 初始化一个列表，用于保存遍历序列
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();  // 队列出队
            list.add(node.val);            // 保存节点值
            if (node.left != null) queue.offer(node.left);  // 左子节点入队
            if (node.right != null) queue.offer(node.right); // 右子节点入队
        }
        return list;
    }
}

深度优先

基于“递归”实现

• 前序遍历：中左右
• 中序遍历：左中右
• 后续遍历：左右中

package dataStructure.树;

import java.util.ArrayList;

public class binary_tree_dfs {

    // 保存遍历结果
    ArrayList<Integer> list = new ArrayList<>();

    // 前序遍历
    void preOrder(TreeNode root) {
        if (root == null) return;
        // 访问优先级：根节点 -> 左子树 -> 右子树
        list.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) return;
        // 访问优先级：左子树 -> 根节点 -> 右子树
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) return;
        // 访问优先级：左子树 -> 右子树 -> 根节点
        postOrder(root.left);
        postOrder(root.right);
        list.add(root.val);
    }

}