二叉树

发表于 2026-03-01 更新于 2026-04-12 分类于数据结构

二叉树

背景

数据结构——二叉树
博主以代码随想录进行学习

介绍

二叉树是每个节点最多有 2 个子节点的树结构，两个子节点分别称为「左子节点」和「右子节点」，具有以下核心特性：
- 每个节点的度（子节点数）≤ 2
- 子树有左右之分，顺序不可颠倒（区分于普通树）
- 空树也是合法的二叉树

二叉树的种类

满二叉树
- 定义：除了叶子节点，每个节点都有左右两个子节点，且所有叶子节点都在同一层。
- 特点：节点总数 = 2h−1（h 为树的高度）。
- 示例：高度为 3 的满二叉树，节点总数 = 2^3^−1=7。
完全二叉树
- 定义：按「层序遍历」的顺序给节点编号，所有编号都能和相同高度的满二叉树一一对应（叶子节点只能出现在最下层和次下层，且最下层叶子靠左）。
- 特点：堆（大顶堆 / 小顶堆）就是完全二叉树的典型应用。
- 区别于满二叉树：满二叉树一定是完全二叉树，但完全二叉树不一定是满的。
二叉搜索树（BST）
- 定义：左子树所有节点值 <根节点值，右子树所有节点值> 根节点值；左右子树也必须是二叉搜索树。
- 特点：中序遍历结果是严格升序的，常用于有序数据的查找 / 插入 / 删除。
平衡二叉搜索树（AVL 树）
- 定义：在二叉搜索树的基础上，要求每个节点的左右子树高度差（平衡因子）≤ 1。
- 特点：保证查询效率（时间复杂度 O(logn)），避免二叉搜索树退化成链表。
- 常见变种：红黑树（近似平衡，工业界更常用，如 HashMap、TreeMap）。

二叉树的存储方式

链式存储（最常用）

方式：通过「节点类」+ 指针（引用）连接，每个节点包含「值、左子节点引用、右子节点引用」。
优点：增删节点灵活，符合二叉树的逻辑结构；
缺点：需要额外存储指针，空间利用率略低。

代码示例（Java）：

// 二叉树节点定义（链式存储）
class TreeNode {
    int val;
    TreeNode left;  // 左子节点引用
    TreeNode right; // 右子节点引用
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

顺序存储（数组存储）
- 方式：用数组存放节点，按「层序遍历」顺序排列，通过下标映射父子关系：
  - 若父节点下标为 i，则左子节点下标 = 2*i + 1，右子节点下标 = 2*i + 2；
  - 若子节点下标为 j，则父节点下标 = (j-1)/2（整数除法）。
- 优点：无需存储指针，空间利用率高；
- 缺点：适合完全二叉树，非完全二叉树会浪费数组空间。
- 示例：数组 [1,2,3,4,5,null,6] 对应层序遍历的二叉树（null 表示空节点）。

二叉树的遍历方式

遍历核心目标：按一定顺序访问二叉树的所有节点，且每个节点仅访问一次。分为「深度优先遍历（DFS）」和「广度优先遍历（BFS）」两大类。

深度优先遍历（DFS）：优先遍历到树的最深层，再回溯，核心用「递归」或「栈」实现。

前序遍历（根 → 左 → 右）

顺序：先访问根节点，再遍历左子树，最后遍历右子树。

代码

public void preOrder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);       // 根
    preOrder(root.left, res); // 左
    preOrder(root.right, res);// 右
}

中序遍历（左 → 根 → 右）

顺序：先遍历左子树，再访问根节点，最后遍历右子树（二叉搜索树的中序遍历是升序）。

代码

public void inOrder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    inOrder(root.left, res);  // 左
    res.add(root.val);        // 根
    inOrder(root.right, res); // 右
}

后序遍历（左 → 右 → 根）

顺序：先遍历左子树，再遍历右子树，最后访问根节点。

代码

public void postOrder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    postOrder(root.left, res);  // 左
    postOrder(root.right, res); // 右
    res.add(root.val);          // 根
}

广度优先遍历（BFS）：即「层序遍历」，按层级从左到右访问节点，核心用「队列」实现。

代码

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size(); // 当前层的节点数
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

二叉树的定义

逻辑定义：二叉树是由「空集」或「一个根节点 + 两棵互不相交的左子树、右子树」组成的有限集合，左 / 右子树也满足二叉树的定义（递归定义）。

代码定义

// 基础节点定义
class TreeNode {
    // 节点值（可根据题目改为 String/自定义类型）
    int val;
    // 左子节点引用
    TreeNode left;
    // 右子节点引用
    TreeNode right;
    
    // 构造方法（重载，满足不同初始化需求）
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

总结

核心关键点
二叉树的核心分类：满二叉树、完全二叉树（堆）、二叉搜索树（BST）、平衡二叉树（AVL / 红黑树）；
存储方式：链式存储（灵活，通用）、顺序存储（适合完全二叉树）；
遍历方式：DFS（前 / 中 / 后序，递归 / 栈）、BFS（层序，队列），中序遍历是 BST 的核心考点；
代码基础：TreeNode 节点定义是所有二叉树题目的前提，递归是遍历的核心思想。