数据结构-二叉树

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 7 分钟

文档引用

二叉树

「二叉树 binary tree」是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

1
2
3
4
5
6
7
/* 二叉树节点类 */
class TreeNode {
    int val;         // 节点值
    TreeNode left;   // 左子节点引用
    TreeNode right;  // 右子节点引用
    TreeNode(int x) { val = x; }
}

每个节点都有两个引用（指针），分别指向「左子节点 left-child node」和「右子节点 right-child node」，该节点被称为这两个子节点的「父节点 parent node」。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的「左子树 left subtree」，同理可得「右子树 right subtree」。

在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。如图 7-1 所示，如果将“节点 2”视为父节点，则其左子节点和右子节点分别是“节点 4”和“节点 5”，左子树是“节点 4 及其以下节点形成的树”，右子树是“节点 5 及其以下节点形成的树”。

父节点、子节点、子树

二叉树常见术语

二叉树的常用术语如图 7-2 所示。

  • 「根节点 root node」：位于二叉树顶层的节点，没有父节点。
  • 「叶节点 leaf node」：没有子节点的节点，其两个指针均指向 None 。
  • 「边 edge」：连接两个节点的线段，即节点引用（指针）。
  • 节点所在的「层 level」：从顶至底递增，根节点所在层为 1 。
  • 节点的「度 degree」：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
  • 二叉树的「高度 height」：从根节点到最远叶节点所经过的边的数量。
  • 节点的「深度 depth」：从根节点到该节点所经过的边的数量。
  • 节点的「高度 height」：从距离该节点最远的叶节点到该节点所经过的边的数量。

二叉树的常用术语

请注意，我们通常将“高度”和“深度”定义为“经过的边的数量”，但有些题目或教材可能会将其定义为“经过的节点的数量”。在这种情况下，高度和深度都需要加 1 。

常见二叉树类型

1. 完美二叉树

如图 7-4 所示，「完美二叉树 perfect binary tree」所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树的高度为 ℎ ，则节点总数为 2ℎ+1−1 ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。

请注意，在中文社区中，完美二叉树常被称为「满二叉树」。

完美二叉树

2. 完全二叉树

如图 7-5 所示，「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。

完全二叉树

3. 完满二叉树

如图 7-6 所示，「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点。

完满二叉树

4. 平衡二叉树

如图 7-7 所示，「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

平衡二叉树

7.1.4 二叉树的退化

图 7-8 展示了二叉树的理想结构与退化结构。当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。

  • 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
  • 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至 O(n) 。

二叉树的最佳结构与最差结构

如表 7-1 所示，在最佳结构和最差结构下，二叉树的叶节点数量、节点总数、高度等达到极大值或极小值。

表 7-1 二叉树的最佳结构与最差结构

完美二叉树 链表
第 i层的节点数量 2^i−1 1
高度为 ℎ 的树的叶节点数量 2^ℎ 1
高度为 ℎ 的树的节点总数 2^(ℎ+1)−1 ℎ+1
节点总数为 i 的树的高度 log2⁡(n+1)−1 n−1

二叉树的遍历

从物理结构的角度来看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而，树是一种非线性数据结构，这使得遍历树比遍历链表更加复杂，需要借助搜索算法来实现。

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

层序遍历

如图 7-9 所示，「层序遍历 level-order traversal」从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

层序遍历本质上属于「广度优先遍历 breadth-first traversal」，也称「广度优先搜索 breadth-first search, BFS」，它体现了一种“一圈一圈向外扩展”的逐层遍历方式。

二叉树的层序遍历

1.代码实现

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static List<Integer> bfs(BinaryTreeNode tree) {
    // 初始化 list 用于存放遍历结果
    List<Integer> result = new ArrayList<>();
    Queue<BinaryTreeNode> queue = new LinkedList<>();
    queue.add(tree);
    while (!queue.isEmpty()) {
        BinaryTreeNode node = queue.poll();
        result.add(node.getValue());
        if (null != node.getLeft()) {
            queue.offer(node.getLeft());
        }
        if (null != node.getRight()) {
            queue.offer(node.getRight());
        }
    }
    return result;
}

2. 复杂度分析

  • 时间复杂度为O(n) ：所有节点被访问一次，使用 O(n) 时间，其中 n 为节点数量。
  • 空间复杂度为O(n) ：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 (n+1)/2 个节点，占用 O(n) 空间。

前序、中序、后序遍历

相应地，前序、中序和后序遍历都属于「深度优先遍历 depth-first traversal」，也称「深度优先搜索 depth-first search, DFS」，它体现了一种“先走到尽头，再回溯继续”的遍历方式。

图 7-10 展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。

二叉搜索树的前序、中序、后序遍历

1.代码实现

深度优先搜索通常基于递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
private List<Integer> list = new ArrayList<>();

/**
 * 前序遍历
 *
 * @param node
 * @author Forest Dong
 * @date 2024/01/10 19:50
 */
public void preOrder(BinaryTreeNode node) {
    if (null == node) {
        return;
    }
    // 访问优先级：根节点 -> 左子树 -> 右子树
    // 逻辑处理
    process(node);
    // 遍历左节点
    preOrder(node.getLeft());
    // 遍历右节点
    preOrder(node.getRight());
}

/**
 * 中序遍历
 *
 * @param node
 * @author Forest Dong
 * @date 2024/01/10 19:50
 */
public void inOrder(BinaryTreeNode node) {
    if (null == node) {
        return;
    }
    // 访问优先级：左子树 -> 根节点 -> 右子树
    // 遍历左节点
    inOrder(node.getLeft());
    // 逻辑处理
    process(node);
    // 遍历右节点
    inOrder(node.getRight());
}

/**
 * 后序遍历
 *
 * @param node
 * @author Forest Dong
 * @date 2024/01/10 19:51
 */
public void postOrder(BinaryTreeNode node) {
    if (null == node) {
        return;
    }
    // 访问优先级：左子树 -> 根节点 -> 右子树
    // 遍历左节点
    postOrder(node.getLeft());
    // 遍历右节点
    postOrder(node.getRight());
    // 逻辑处理
    process(node);
}

/**
 * 逻辑处理
 * 这里将节点值添加进List中，用来展示搜索顺序，在实际应用中可修改为相应的业务处理逻辑
 *
 * @param currentNode
 * @return
 * @author dongyang
 * @date 2021/3/7 下午3:23
 */
private void process(BinaryTreeNode currentNode) {
    // 这里将节点值添加进List中，用来展示搜索顺序，在实际应用中可修改为相应的业务处理逻辑
    list.add(currentNode.getValue());
}

2. 复杂度分析

  • 时间复杂度为O(n) ：所有节点被访问一次，使用 O(n) 时间。
  • 空间复杂度为O(n) ：在最差情况下，即树退化为链表时，递归深度达到n，系统占用O(n)栈帧空间。