小菜鸟

java菜鸟号正在起航

0%

二叉树

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 5k 阅读时长 ≈ 5 分钟

二叉树：结构、分类与遍历全解析

二叉树是一种每个节点最多有两个子树（左子树和右子树）的树形结构，是数据结构中的基础且重要的模型。其简洁的层次关系和灵活的操作特性，使其广泛应用于索引、表达式解析、人工智能等领域。本文将从性质、分类、存储到遍历，全面解析二叉树。

二叉树的基本性质

二叉树的核心性质描述了节点数量、层数、深度之间的关系，是理解其结构的基础：

  1. 第 i 层节点数上限：
    二叉树第i层（根节点为第 1 层）上的节点数目至多为 2^(i-1)。
    • 例：第 3 层最多有 2^(3-1)=4 个节点。
  2. 深度为 k 的节点总数上限：
    深度为k的二叉树至多有 2^k - 1 个节点（满二叉树的情况）。
    • 例：深度为 3 的满二叉树有 2^3 - 1 = 7 个节点。
  3. 叶子节点与度为 2 的节点关系：
    对任何二叉树，若叶子节点数为n₀，度为 2 的节点数为n₂，则 n₀ = n₂ + 1。
    • 原理：总边数 = 总节点数 - 1，且总边数 = 度为 1 的节点数 + 2× 度为 2 的节点数，联立推导可得。
  4. 完全二叉树的深度：
    具有n个节点的完全二叉树，深度为 ⌊log₂n⌋ + 1（⌊x⌋ 表示向下取整）。
    • 例：n=7时，深度为 ⌊log₂7⌋ + 1 = 2 + 1 = 3。

二叉树的分类

根据结构和特性，二叉树可分为以下几类：

普通二叉树

每个节点最多有 2 个子树（左子树和右子树），无其他约束。

二叉查找树（BST，Binary Search Tree）

核心特性：

  • 左子树所有节点值 < 根节点值；
  • 右子树所有节点值 > 根节点值；
  • 左右子树也为二叉查找树。

优势：支持高效查找（类似二分查找），平均时间复杂度O(logn)。
缺陷：极端情况下（如有序插入）会退化为单链表，查找效率降至O(n)。

满二叉树

定义：除叶节点外，所有节点均有 2 个子树，且叶节点在同一层。
节点总数：深度为k的满二叉树有 2^k - 1 个节点（符合性质 2 的上限）。

完全二叉树

定义：

  • 除最后一层外，其余层均为满二叉树；
  • 最后一层的节点从左到右连续排列（无空缺）。

特点：适合顺序存储（数组），父节点与子节点的索引关系明确（左子节点2i+1，右子节点2i+2）。

霍夫曼树（最优二叉树）

定义：带权路径长度（所有叶节点的权值 × 路径长度之和）最短的二叉树。
应用：数据压缩（霍夫曼编码），通过权值（频率）高的节点靠近根节点，减少总编码长度。

红黑树

定义：一种自平衡的二叉查找树，通过颜色规则（红 / 黑）维持近似平衡：

  • 根节点、叶节点为黑色；
  • 红色节点的子节点必为黑色（无连续红节点）；
  • 从任一节点到叶节点的所有路径，黑色节点数相同。

优势：插入 / 删除时旋转操作少（相比 AVL 树），适合频繁修改的场景（如TreeMap）。

平衡二叉树（AVL 树）

定义：严格平衡的二叉查找树，左右子树高度差（平衡因子）的绝对值≤1。
优势：查询效率高（树高严格控制在O(logn)）。
缺陷：插入 / 删除时旋转频繁（尤其是删除），适合查询密集场景。

二叉树的存储方式

二叉树的存储需体现节点间的父子关系，常见方式有顺序存储（数组）和链表存储。

1. 顺序存储（数组）

利用满二叉树的节点索引规律，将二叉树映射到数组中：

  • 根节点存于索引0；
  • 索引i的左子节点存于2i+1，右子节点存于2i+2；
  • 索引i的父节点存于(i-1)/2（向下取整）。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ArrayBinTree<T> {
    private T[] datas; // 存储节点的数组
    private int deep;  // 树的深度
    private int size;  // 数组容量（2^deep - 1）

    public ArrayBinTree(int deep) {
        this.deep = deep;
        this.size = (int) Math.pow(2, deep) - 1;
        this.datas = (T[]) new Object[size];
    }

    // 向父节点添加左右子节点
    public void add(int parentIndex, T data, boolean isLeft) {
        if (datas[parentIndex] == null) {
            throw new RuntimeException("父节点不存在");
        }
        int childIndex = isLeft ? 2 * parentIndex + 1 : 2 * parentIndex + 2;
        if (childIndex >= size) {
            throw new RuntimeException("超出数组容量");
        }
        datas[childIndex] = data;
    }
}

优缺点：

  • 优点：随机访问快（通过索引直接定位）。
  • 缺点：非满二叉树会浪费空间（空节点仍占数组位置）。

2. 链表存储

每个节点包含数据域和指向左右子节点的引用（可扩展父节点引用），灵活适应各种二叉树。

节点结构：

1
2
3
4
5
6
7
8
9
10
static class TreeNode<E> {
    E data;          // 节点数据
    TreeNode<E> left;  // 左子节点
    TreeNode<E> right; // 右子节点
    TreeNode<E> parent; // 父节点（可选，便于回溯）

    public TreeNode(E data) {
        this.data = data;
    }
}

树结构及添加节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LinkBinTree<E> {
    private TreeNode<E> root; // 根节点

    public LinkBinTree(E rootData) {
        this.root = new TreeNode<>(rootData);
    }

    // 向父节点添加左右子节点
    public TreeNode<E> add(TreeNode<E> parent, E data, boolean isLeft) {
        if (parent == null) throw new RuntimeException("父节点为空");
        if (isLeft && parent.left != null) throw new RuntimeException("左子节点已存在");
        if (!isLeft && parent.right != null) throw new RuntimeException("右子节点已存在");

        TreeNode<E> newNode = new TreeNode<>(data);
        newNode.parent = parent; // 记录父节点
        if (isLeft) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        return newNode;
    }
}

优缺点：

  • 优点：空间利用率高（仅存储实际节点），适应各种二叉树。
  • 缺点：随机访问差（需从根节点遍历）。

二叉树的遍历方式

遍历是按特定顺序访问二叉树所有节点的过程，分为深度优先遍历（DFS）和广度优先遍历（BFS）。

1. 深度优先遍历（DFS）

优先访问树的最深层节点，包括前序、中序、后序三种方式（以根节点D、左子树L、右子树R的访问顺序区分）。

（1）前序遍历（DLR：根→左→右）

步骤：

  1. 访问根节点；
  2. 递归前序遍历左子树；
  3. 递归前序遍历右子树。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
public List<TreeNode<E>> preOrder() {
    List<TreeNode<E>> result = new ArrayList<>();
    preOrder(root, result);
    return result;
}

private void preOrder(TreeNode<E> node, List<TreeNode<E>> result) {
    if (node == null) return;
    result.add(node);          // 访问根
    preOrder(node.left, result);  // 左子树
    preOrder(node.right, result); // 右子树
}
（2）中序遍历（LDR：左→根→右）

步骤：

  1. 递归中序遍历左子树；
  2. 访问根节点；
  3. 递归中序遍历右子树。

特点：二叉查找树的中序遍历结果为升序序列。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
public List<TreeNode<E>> inOrder() {
    List<TreeNode<E>> result = new ArrayList<>();
    inOrder(root, result);
    return result;
}

private void inOrder(TreeNode<E> node, List<TreeNode<E>> result) {
    if (node == null) return;
    inOrder(node.left, result);   // 左子树
    result.add(node);             // 访问根
    inOrder(node.right, result);  // 右子树
}
（3）后序遍历（LRD：左→右→根）

步骤：

  1. 递归后序遍历左子树；
  2. 递归后序遍历右子树；
  3. 访问根节点。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
public List<TreeNode<E>> postOrder() {
    List<TreeNode<E>> result = new ArrayList<>();
    postOrder(root, result);
    return result;
}

private void postOrder(TreeNode<E> node, List<TreeNode<E>> result) {
    if (node == null) return;
    postOrder(node.left, result);  // 左子树
    postOrder(node.right, result); // 右子树
    result.add(node);              // 访问根
}

2. 广度优先遍历（BFS，层序遍历）

步骤：逐层访问节点，从根节点开始，依次访问第 1 层、第 2 层…… 直至最后一层。
实现方式：用队列存储当前层节点，弹出节点时将其左右子节点入队。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<TreeNode<E>> levelOrder() {
    List<TreeNode<E>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode<E>> queue = new LinkedList<>();
    queue.add(root); // 根节点入队

    while (!queue.isEmpty()) {
        TreeNode<E> node = queue.poll(); // 弹出当前层节点
        result.add(node);

        if (node.left != null) queue.add(node.left);   // 左子节点入队
        if (node.right != null) queue.add(node.right); // 右子节点入队
    }
    return result;
}

应用：层次化数据处理（如打印目录结构、二叉树的按层打印）。

总结

二叉树是层次化数据的核心模型，其性质决定了节点分布规律，分类适应不同场景（如 BST 用于查找、红黑树用于动态平衡）。存储方式中，数组适合完全二叉树，链表适合复杂结构；遍历方式中，深度优先适合递归场景，广度优先适合层次访问

相关文章

欢迎关注我的其它发布渠道