【数据结构 -- 二叉树】一叶一终点,一岔一分行

作者:是main不是漫日期:2026/10/18

欢迎阅读本篇学习笔记。
本篇作为个人计算机专业的学习记录,这里将系统梳理二叉树的相关知识点,从基础概念到代码实现逐步展开,便于后续的复习巩固。如有不足,欢迎大家在评论区交流指正,感谢大家的阅读与支持!

1.树概念及结构

1.1树的概念

在学习二叉树之前我们先来了解一下树的概念。

树是一种非线性的数据结构,它是由 n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

  • 有一个特殊的结点,称为根结点,根结点没有前驱结点
  • 除根结点外,其余结点被分成 M (M>0) 个互不相交的集合 T1、T2、……、Tm,其中每一个集合 Ti (1<= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有 0 个或多个后继
  • 因此,树是递归定义的。

注意:树形结构中,子树之间不能有交集,否则就不是树形结构

1.2树的相关概念

  • 结点的度:一个结点含有的子树的个数称为该结点的度。度是衡量一个结点“分支能力”的重要指标,它直接反映了该结点向下延伸的规模。如上图:A 的度为 6,说明 A 结点直接连接了 6 棵子树。
  • 叶结点或终端结点:度为 0 的结点称为叶结点,也就是没有任何子结点的结点。叶结点通常位于树的末端,是树结构中最底层的结点。如上图:B、C、H、I… 等结点为叶结点。
  • 非终端结点或分支结点:度不为 0 的结点称为分支结点,这类结点至少含有一个子结点,在树中起到承上启下的作用。如上图:D、E、F、G… 等结点为分支结点。
  • 双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点。父结点是子结点向上追溯的直接来源。如上图:A 是 B 的父结点。
  • 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点。孩子结点是父结点向下延伸的直接结果。如上图:B 是 A 的孩子结点。
  • 兄弟结点:具有相同父结点的结点互称为兄弟结点。兄弟结点之间处于同一层级,共享同一个父结点。如上图:B、C 是兄弟结点。
  • 树的度:一棵树中,最大的结点的度称为树的度。树的度反映了整棵树的最大分支规模,是描述树结构特征的重要参数。如上图:树的度为 6。
  • 结点的层次:从根开始定义起,根为第 1 层,根的子结点为第 2 层,以此类推。层次体现了结点在树中的纵向位置,层次越小越靠近根结点。
  • 树的高度或深度:树中结点的最大层次称为树的高度或深度。高度决定了树的纵向延伸范围,是衡量树规模的重要指标。如上图:树的高度为 4。
  • 堂兄弟结点:双亲在同一层的结点互为堂兄弟。堂兄弟结点并不共享同一个父结点,但它们的父结点处于同一层次。如上图:H、I 互为兄弟结点。
  • 结点的祖先:从根到该结点所经分支上的所有结点都称为该结点的祖先。祖先结点是沿着从根向下的路径依次经过的结点。如上图:A 是所有结点的祖先。
  • 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。子孙结点涵盖了该结点向下延伸的所有后代。如上图:所有结点都是 A 的子孙。
  • 森林:由 m(m>0)棵互不相交的树的集合称为森林。森林可以看作是多棵树的集合,在实际应用中,森林与树的转换是常见的操作。

1.3树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

1typedef int DataType;
2struct Node
3{
4    struct Node* firstChild1;   // 第一个孩子结点
5    struct Node* pNextBrother;  // 指向其下一个兄弟结点
6    DataType data;              // 结点中的数据域
7};
8

好啦,看完上面的文字相信大家已经对树有了一定了解。树作为一种基础的非线性数据结构,其核心在于通过结点之间的层次关系来组织数据,这与我们熟悉的线性表有着本质区别。理解树的概念和相关术语,是后续学习二叉树、堆、并查集等更复杂结构的重要前提。接下来,我们将进入二叉树的学习。

2.二叉树的概念及结构

2.1二叉树的概念

二叉树是由结点构成的有限集合,它有且仅有两种情况:

  1. 集合中没有任何结点,称为空二叉树;
  2. 集合由一个根结点,加上两棵互不相交、分别称作左子树和右子树的二叉树共同组成。

从上图可以看出:

  1. 二叉树不存在度大于 2 的结点
  2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

注意:对于任意的二叉树都是由以下几种情况复合而成的: 空树、只有根节点、只有左子树、只有右子树、左右子树均存在

2.2特殊的二叉树

  • 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为 K,且结点总数是 2的k次方-1,则它就是满二叉树。
  • 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为 K 的,有 n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。通俗一点来讲就是:除了最底下一层,上面所有层的结点都全部填满(前 k-1 层是标准的满二叉树)最底层的结点全部靠左连续排列,中间没有空缺。

2.3二叉树的性质

1/*
2 * 假设二叉树有N个结点
3 * 从总结点数角度考虑: N = n0 + n1 + n2 ①
4 *
5 * 从边的角度考虑,N个结点的任意二叉树,总共有N-1条边
6 * 因为二叉树中每个结点都有双亲,根结点没有双亲,每个节点向上与其双亲之间存在一条边
7 * 因此N个结点的二叉树总共有N-1条边
8 *
9 * 因为度为0的结点没有孩子,故度为0的结点不产生边;度为1的结点只有一个孩子,故每个度为1的结点
10 * * 产生一条边;度为2的结点有2个孩子,故每个度为2的结点产生两条边,所以总边数为:
11 * n1+2*n2
12 * 故从边的角度考虑: N‑1 = n1 + 2*n2 ②
13 * 结合① 和 ②得: n0 + n1 + n2 = n1 + 2*n2 -1
14 * 即: n0 = n2 + 1
15 */
16

✏️ 概念巩固选择题

我们来做几道题来加深我们对二叉树性质的理解。通过实际题目,我们可以更直观地体会上述性质在解题中的应用,也能帮助大家巩固对二叉树结构特征的认知。

参考答案:1.B 2.A 3.A 4.B 5.B

2. 二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。

1. 顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们下一部分会专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

(对应下面配图:左侧为完全二叉树的数组存储,右侧为一般二叉树的数组存储对比)

2. 链式存储

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面随着我们学习的深入会学到红黑树等等会用到三叉链。

3. 堆的概念及结构

在上一部分我们了解了二叉树的两种存储结构,其中**顺序存储(数组)**最适合表示完全二叉树,而现实中最典型的应用就是「堆」。这一部分内容我们将会讲解堆的概念、实现与应用。我们先来了解一下堆和二叉树的区别。

3.1 堆的定义与性质

若存在一个关键码的集合 K = {k0, k1, k2, ..., k (n-1)},将其所有元素按照完全二叉树的顺序存储方式存放于一维数组中,并且满足下述关系,则称该集合为堆:

  • 若满足 Ki ≤ K (2i+1) 且 Ki ≤ K (2i+2),则称为小根堆(小顶堆),此时根结点为全局最小值;
  • 若满足 Ki ≥ K (2i+1) 且 Ki ≥ K (2i+2),则称为大根堆(大顶堆),此时根结点为全局最大值。

堆的核心性质

  1. 堆中任意结点的值,总是不大于(小根堆)或不小于(大根堆)其父结点的值;
  2. 堆在逻辑上一定是一棵完全二叉树,物理上用一维数组存储。

小根堆与大根堆示例

小根堆:父结点 ≤ 左右孩子

  • 逻辑结构:根为 10,子结点 15、56,底层结点 25、30、70
  • 对应存储数组:{10, 15, 56, 25, 30, 70}

大根堆:父结点 ≥ 左右孩子

  • 逻辑结构:根为 70,子结点 56、30,底层结点 25、15、10
  • 对应存储数组:{70, 56, 30, 25, 15, 10}

✏️ 概念巩固选择题

参考答案:1.A 2.C 3.C 4.C


3. 堆的实现

3.1 堆向下调整算法

向下调整是堆所有操作的核心算法,它有一个严格的前提条件:

待调整结点的左、右子树必须已经是堆,才能对该结点执行向下调整。

算法思路(以小根堆为例)

  1. 从目标结点开始,比较当前结点与其左、右孩子的值;
  2. 找到左右孩子中值更小的结点,与当前结点比较;
  3. 如果孩子结点更小,则交换当前结点与孩子结点;
  4. 继续向下重复上述过程,直到当前结点满足堆性质,或到达叶子结点。

示例:数组 {27,15,19,18,28,34,65,49,25,37} 其左右子树本身已经是小根堆,仅根结点 27 不满足堆性质,只需将 27 逐层向下交换到合适位置,即可形成完整的小根堆。


3.2 堆的创建(建堆)

对于一个任意数组,它逻辑上对应一棵完全二叉树,但不一定满足堆的性质。我们可以通过从下往上、对每个非叶子结点依次执行向下调整,将整棵树构建成一个堆。

建堆步骤

  1. 找到倒数第一个非叶子结点(即数组最后一个结点的父结点);
  2. 从该结点开始,倒序向前遍历所有非叶子结点;
  3. 对每一个非叶子结点执行向下调整算法;
  4. 一直调整到根结点,整棵树就成为一个合法的堆。

注意:每次元素交换后,被影响的子树结构可能被破坏,因此需要对交换后的子树重新向下调整,保证子树仍然满足堆性质。

示例:数组 {1,5,3,8,7,6} 构建大根堆,最终得到大根堆序列:8 7 6 1 5 3


3.3 建堆的时间复杂度

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的 就是近似值,多几个结点不影响最终结果)

因此:建堆的时间复杂度为 O(N)


3.4 堆的插入

这里展示的是小堆的插入(大堆也是类似的)

堆的插入操作分为两步:

  1. 将新元素插入到数组的尾部,也就是完全二叉树的最后一个叶子位置;
  2. 对新插入的结点执行向上调整算法:从该结点开始,不断与父结点比较,若不满足堆性质则交换,直到满足堆性质或到达根结点。


3.5 堆的删除

堆的删除默认删除堆顶元素(即当前堆的最值),操作步骤:

  1. 将堆顶元素与数组最后一个元素交换;
  2. 删除数组的最后一个元素(原堆顶元素);
  3. 对新的堆顶元素执行向下调整算法,恢复整个堆的性质。

这种删除方式可以保证删除后结构仍然是合法的堆,单次删除的时间复杂度为 O(logN)。


3.6 堆的代码实现(C 语言)

堆的结构体定义

1typedef int HPDataType;
2typedef struct Heap
3{
4HPDataType* _a;   // 存储堆元素的数组
5int _size;        // 堆中当前元素个数
6int _capacity;    // 数组的总容量
7}Heap;

堆的常用接口声明

1// 堆的构建
2void HeapCreate(Heap* hp, HPDataType* a, int n);
3// 堆的销毁
4void HeapDestory(Heap* hp);
5// 堆的插入
6void HeapPush(Heap* hp, HPDataType x);
7// 堆的删除(删堆顶)
8void HeapPop(Heap* hp);
9// 获取堆顶的数据
10HPDataType HeapTop(Heap* hp);
11// 获取堆的数据个数
12int HeapSize(Heap* hp);
13// 堆的判空
14int HeapEmpty(Heap* hp);
15

4. 堆的应用:堆排序

堆排序(Heap Sort)就是利用堆的思想对数组进行排序,总共分为两大核心步骤:

4.1 步骤一:建堆

  • 排升序:建立大根堆
  • 排降序:建立小根堆

4.2 步骤二:利用堆删除思想排序

建堆完成后,堆顶元素就是整个数组的最值。我们不断执行「堆顶与末尾元素交换 → 缩小堆的范围 → 堆顶向下调整」的循环,每次都能将当前堆的最值放到数组的末尾位置,最终整个数组变为有序序列。

由于建堆和堆删除的核心都是向下调整算法,因此只要掌握了向下调整,就可以完整实现堆排序。

4.3 TOP-K 问题

4.3.1 问题场景

TOP-K 问题的核心需求是:在海量数据中,找出前 K 个最大的元素或者前 K 个最小的元素。常见的应用场景比如专业成绩前 10 名、世界 500 强企业、游戏全服活跃榜前 100 名等。

这类问题的典型特点是数据量极大,如果直接对全部数据做全排序,不仅时间成本很高,甚至可能无法将全部数据一次性加载到内存中。而堆结构正是解决海量数据 TOP-K 问题的最优方案。

4.3.2 解题思路

  1. 用前 K 个元素建初始堆
    • 求前 K 个最大的元素 → 建小根堆(堆顶是当前 K 个元素里的最小值,遇到更大的元素就替换堆顶)
    • 求前 K 个最小的元素 → 建大根堆(堆顶是当前 K 个元素里的最大值,遇到更小的元素就替换堆顶)
  2. 遍历剩余的 N-K 个元素,依次与堆顶元素比较:
    • 如果当前元素比堆顶更符合要求(求最大时比堆顶大,求最小时比堆顶小),则用该元素替换堆顶
    • 替换后对堆顶执行向下调整算法,恢复堆的性质
  3. 全部元素遍历完成后,堆中剩余的 K 个元素就是所求的前 K 个最值元素

4.3.3 代码框架

1void PrintTopK(int* a, int n, int k)
2{
3    // 1. 用数组前k个元素建堆
4    // 2. 剩余n-k个元素依次与堆顶比较,不满足则替换并向下调整
5}
6

4.3.4 测试示例

下面的代码模拟了在 10000 个随机数中,找出数值最大的前 10 个元素:

1#include <stdio.h>
2#include <stdlib.h>
3#include <time.h>
4
5// 小顶堆向下调整
6void sift_down(int* heap, int size, int index) {
7    while (1) {
8        int left = 2 * index + 1;
9        int right = 2 * index + 2;
10        int min_idx = index;
11
12        if (left < size && heap[left] < heap[min_idx]) {
13            min_idx = left;
14        }
15        if (right < size && heap[right] < heap[min_idx]) {
16            min_idx = right;
17        }
18        if (min_idx == index) break;
19
20        int temp = heap[index];
21        heap[index] = heap[min_idx];
22        heap[min_idx] = temp;
23        index = min_idx;
24    }
25}
26
27// 小顶堆实现 Top-K:输出数组中最大的前k个元素
28void PrintTopK(int* a, int n, int k) {
29    int* heap = (int*)malloc(sizeof(int) * k);
30    int heap_size = 0;
31
32    for (int i = 0; i < n; i++) {
33        if (heap_size < k) {
34            // 堆未满,插入尾部并向上调整
35            heap[heap_size++] = a[i];
36            int idx = heap_size - 1;
37            while (idx > 0) {
38                int parent = (idx - 1) / 2;
39                if (heap[idx] < heap[parent]) {
40                    int temp = heap[idx];
41                    heap[idx] = heap[parent];
42                    heap[parent] = temp;
43                    idx = parent;
44                } else break;
45            }
46        } else if (a[i] > heap[0]) {
47            // 堆已满,比堆顶大则替换并向下调整
48            heap[0] = a[i];
49            sift_down(heap, heap_size, 0);
50        }
51    }
52
53    printf("最大的前%d个元素:", k);
54    for (int i = 0; i < heap_size; i++) {
55        printf("%d ", heap[i]);
56    }
57    printf("\n");
58    free(heap);
59}
60
61void TestTopK() {
62    int n = 10000;
63    int* a = (int*)malloc(sizeof(int) * n);
64    srand((unsigned int)time(NULL));
65
66    // 生成10000个0~99999的随机整数
67    for (int i = 0; i < n; ++i) {
68        a[i] = rand() % 100000;
69    }
70
71    // 手动植入10个更大的数,用于验证算法结果
72    a[5] = 100000 + 1;
73    a[1231] = 100000 + 2;
74    a[531] = 100000 + 3;
75    a[5121] = 100000 + 4;
76    a[115] = 100000 + 5;
77    a[2335] = 100000 + 6;
78    a[9999] = 100000 + 7;
79    a[76] = 100000 + 8;
80    a[423] = 100000 + 9;
81    a[3144] = 100000 + 10;
82
83    PrintTopK(a, n, 10);
84    free(a);
85}
86

该算法核心仅维护大小为 K 的小顶堆,空间复杂度为 O (K);实际海量数据场景下可流式逐个读取数据,无需将全部数据加载到内存,非常适合处理大规模数据下的 TOP-K 筛选场景。


5. 二叉树链式结构的实现

前置说明

在学习二叉树的增删改查、遍历等基本操作之前,我们首先需要构造出一棵二叉树作为测试基础。 考虑到初学者对二叉树结构还不够熟悉,为了降低学习门槛,我们先通过手动快速创建的方式得到一棵结构简单的二叉树,先把重心放在遍历等核心操作的学习上。等对二叉树的操作逻辑完全熟悉之后,再深入讲解二叉树通用的、正式的创建方式。

链式二叉树结点定义

链式存储的二叉树采用二叉链表结构,每个结点由三部分组成:数据域、左孩子指针、右孩子指针:

1typedef int BTDataType;
2typedef struct BinaryTreeNode
3{
4BTDataType _data;              // 数据域,存储结点的值
5struct BinaryTreeNode* _left;  // 左指针,指向左孩子结点
6struct BinaryTreeNode* _right; // 右指针,指向右孩子结点
7}BTNode;

手动构建测试二叉树

下面的代码通过逐个申请结点、手动连接指针的方式,构建一棵固定结构的二叉树,用于后续操作的测试:

1BTNode* CreatBinaryTree()
2{
3    // 申请6个结点
4    BTNode* node1 = BuyNode(1);
5    BTNode* node2 = BuyNode(2);
6    BTNode* node3 = BuyNode(3);
7    BTNode* node4 = BuyNode(4);
8    BTNode* node5 = BuyNode(5);
9    BTNode* node6 = BuyNode(6);
10// 按照树形结构连接各结点的左右指针
11node1-&gt;_left = node2;
12node1-&gt;_right = node4;
13node2-&gt;_left = node3;
14node4-&gt;_left = node5;
15node4-&gt;_right = node6;
16return node1; // 返回整棵树的根结点指针
17}

注意:上述代码只是快速构造测试树的权宜写法,并不是二叉树通用的创建方式。

二叉树的递归定义

二叉树的定义本身具有递归性,这也是二叉树绝大多数操作都采用递归实现的根本原因:

  1. 空树:不包含任何结点的二叉树
  2. 非空树:由根结点、根结点的左子树、根结点的右子树三部分组成

换句话说,二叉树的任意一棵子树,本身也都是一棵完整的二叉树。这个概念是理解二叉树递归遍历、递归操作的核心基础。


5.2 二叉树的遍历

5.2.1前序、中序以及后序遍历

遍历是二叉树最基础也最重要的操作。所谓二叉树遍历 (Traversal),是指按照某种特定的规则,依次访问二叉树中的每一个结点,且每个结点仅被访问一次。遍历是二叉树上所有其它运算的基础。

根据访问根结点的时机不同,二叉树有三种经典的深度优先遍历方式:

  1. 前序遍历(先根遍历,Preorder Traversal) 访问根结点的操作,发生在遍历其左右子树之前。 访问顺序:根结点 → 左子树 → 右子树,简称 NLR
  2. 中序遍历(中根遍历,Inorder Traversal) 访问根结点的操作,发生在遍历其左右子树中间。 访问顺序:左子树 → 根结点 → 右子树,简称 LNR
  3. 后序遍历(后根遍历,Postorder Traversal) 访问根结点的操作,发生在遍历其左右子树之后。 访问顺序:左子树 → 右子树 → 根结点,简称 LRN

其中 N 代表根结点 (Node),L 代表左子树 (Left subtree),R 代表右子树 (Right subtree)。由于被访问的结点一定是某棵子树的根,因此 NLR、LNR、LRN 也分别称为先根遍历、中根遍历和后根遍历。

5.2.2 递归遍历的函数接口

三种深度优先遍历都可以基于二叉树的递归定义,用递归函数简洁实现。三个遍历函数的接口声明如下:

1// 二叉树前序遍历
2void PreOrder(BTNode* root);
3// 二叉树中序遍历
4void InOrder(BTNode* root);
5// 二叉树后序遍历
6void PostOrder(BTNode* root);
7

5.2.3 前序遍历递归执行过程详解

二叉树的递归定义天然适配递归遍历逻辑,下面我们以前序遍历为例,完整拆解递归调用与返回的完整执行过程。中序与后序遍历仅调整访问根结点的时机,递归调用的整体路径完全一致,大家可以对照逻辑自行推导。

核心递归逻辑

前序遍历遵循「根 → 左 → 右」的规则,递归函数的执行逻辑为:

  1. 如果当前结点为空(NULL),直接返回,这是递归的终止条件;
  2. 先访问当前根结点;
  3. 递归遍历当前结点的左子树;
  4. 递归遍历当前结点的右子树。

逐步骤递归调用过程

我们以下图中的二叉树为例(根结点 1,左孩子 2、右孩子 4;结点 2 的左孩子为 3;结点 4 的左孩子为 5、右孩子为 6;所有叶子结点的左右子树均为空),逐步拆解前序遍历的执行流程:

  1. 调用 PreOrder(结点1):访问结点 1,随后递归进入左子树,调用 PreOrder(结点2)
  2. 调用 PreOrder(结点2):访问结点 2,随后递归进入左子树,调用 PreOrder(结点3)
  3. 调用 PreOrder(结点3):访问结点 3,随后递归进入左子树,调用 PreOrder(NULL)
  4. 调用 PreOrder(NULL):触发递归终止条件,直接返回到结点 3
  5. 结点 3 继续递归进入右子树,调用 PreOrder(NULL),再次触发终止条件返回;结点 3 遍历完成,返回到结点 2
  6. 结点 2 递归进入右子树,调用 PreOrder(NULL),触发终止条件返回;结点 2 遍历完成,返回到结点 1
  7. 结点 1 递归进入右子树,调用 PreOrder(结点4)
  8. 调用 PreOrder(结点4):访问结点 4,随后递归进入左子树,调用 PreOrder(结点5)
  9. 调用 PreOrder(结点5):访问结点 5,左、右子树依次递归调用均为 NULL,逐层返回;结点 5 遍历完成,返回到结点 4
  10. 结点 4 递归进入右子树,调用 PreOrder(结点6)
  11. 调用 PreOrder(结点6):访问结点 6,左、右子树依次递归调用均为 NULL,逐层返回;结点 6 遍历完成,返回到结点 4
  12. 结点 4 遍历完成,返回到结点 1,整棵二叉树的前序遍历结束

最终得到前序遍历序列:1 2 3 4 5 6

图解说明

图中红色箭头代表递归深入调用的方向,绿色箭头代表递归结束后的返回方向,每一个虚线框都对应一次函数调用的完整生命周期。可以看到,递归遍历本质上是沿着二叉树的结构深度优先深入,遇到空结点就回溯,最终覆盖所有结点。

补充:中序遍历和后序遍历的递归调用路径与前序完全一致,区别仅在于访问根结点的时机:

  • 中序:左子树递归返回后、右子树递归前,访问根结点
  • 后序:左、右子树都递归返回后,再访问根结点

✏️ 概念巩固选择题

参考答案:1.A 2.A 3.D 4.A

好啦,那这篇内容就先整理到这里,这次把二叉树的相关知识整理了一下,为了方便自己日后复习回顾,也希望能给正在学习的小伙伴一些参考。如果文中有理解不到位或是书写有误的地方,欢迎大家在评论区指出,一起交流共同进步。谢谢大家!


《【数据结构 -- 二叉树】一叶一终点,一岔一分行》 是转载文章,点击查看原文。


相关推荐


推荐一款支持AI的数据可视化一站式报表平台
mldong2026/10/16

一、五分钟走一遍:一句话到一面能发布的大屏 登录后首页左侧五栏:首页、报表管理、大屏管理、设计总览、模板市场。右下角有个悬浮球,点开就是 AI 助手。 第 1 步:说人话,别说提示词 我在输入框里打了一句:"搭一张华东区销售日报大屏(深色)"。 它没有直接开始画图,而是回了一段我挺意外的话: 收到,做「华东区销」分析屏——先对齐两点再搭,免得返工: ❓1. 先定指标:盯哪几个?(如销量、销售额、订单量、转化率,说 3~6 个) ❓2. 范围是?(如大盘 / 板块 / 自选,说一个) 你回一


手机远控电脑怎么更顺手?ToDesk移动端手势、虚拟键鼠与指针模式科普
JoyCong19982026/10/7

地铁上临时改文档、躺床上想要玩把3A端游、出差路上帮同事处理问题……越来越多人已因为各样所需事项,开始用手机或平板远程控制电脑来高效解决。但小屏幕中没有实体键鼠,怎么操作才更高效?ToDesk移动端设有触控手势、虚拟键鼠和指针模式等,本篇内容,小编就为屏幕前的各位一次讲清! 一、单指手势:最基础,也最容易混淆         单指单击,等于鼠标单击;单指双击,等于双击操作;单指长按可进入拖动状态,松开后解除拖动。         要注意的是,这里有个关键区别:单指短按是拖动,没有先


同一套充血模型,八种语言八种长相
mldong2026/9/29

写这个系列的时候,收到过一条很典型的评论:"DDD 是 Java 生态的东西吧?Go 要是写成这样会被笑,Python 根本没有真正的封装——你们这些'充血模型'换个语言是不是就得散架?" 这话问到了点子上。理论争论没意思,我们直接把同一个领域模型用八种语言各写了一遍:Java、Go、Python、Node、PHP、Rust、MoonBit、C#。这篇把八个栈的聚合根并排放给你看——哪些地方变了,变了多少;哪些地方一个字都不能变。看懂这张对照表,"充血模型是不是特定语言的特产"这个问题就有答案了


iOS定向加固实践
黑科技iOS上架(解决审核难题)2026/9/23

iOS定向加固实践:小蟹iOS加固能力详解与工程落地指南 文章来源参考文档:https://crab‑https://ios.com/docs/site/%E6%96%B0%E6%89%8B%E6%95%99%E7%A8%8B/harden/ 前言 在iOS开发的安全领域,逆向分析、二进制dump、方法Hook、核心业务逻辑被扒取是开发者长期面对的风险。普通源码混淆大多只能处理业务源码,对于Framework、dylib动态库这类自研二进制组件防护能力薄弱。很多团队在做安全防护时,很容易混淆


iPhone Duo 带来的机遇与挑战 -- 肘子的 Swift 周报 #153
东坡肘子2026/9/15

iPhone Duo 带来的机遇与挑战 尽管 iPhone Duo 的设计资料早在几个月前就已部分泄漏,而且苹果也是折叠机领域的后来者,但凭借软硬件整合能力,它所带来的交互变化还是给不少消费者带来了惊喜。 不同机构对 iPhone Duo 的初期销量给出了不同口径的预测:Counterpoint 预计其 2026 年内出货量最高约 600 万部;IDC 则预计上市后前 12 个月可能达到约 1000 万部。在整个 iPhone 销量中,这仍然只占一小部分,但与 Vision Pro 上市两年半的


从案例分析 Vue3 Tokenizer+Parser 源码四
单线程_012026/9/7

情形四:标签属性(source="<div id=a class="c" inert style=\'\'></div>") 本小节将深度拆解 Vue3 编译器中 普通 HTML 标签多属性完整解析流程,覆盖无引号属性、双引号属性、布尔属性、空值属性四种常见属性场景。本文以 Vue3 源码单元测试用例 __tests__/parse.spec.ts 1068‑1172 的 multiple attributes 案例为核心,逐行梳理标签从词法分析(tokenizer)到语法分析(parser)的


React Router v8 升了之后,我花了两天才把项目跑起来
Flynt2026/8/30

昨天看到 React Router 发了 v8.3.1,想着项目还停在 v7 的某个中间版本,趁周末没排需求,不如先升了试试。 changelog 写得很乐观:"all of them are changes you can make in v7",意思是所有破坏性变更都能提前通过 future flags 适配。我当时觉得挺合理的——我们项目 v7 上了快半年,该有的 flag 应该都开了。 结果 pnpm i react-router@latest 装完一跑,直接炸了三个地方。 升级本身不难


两个 Agent 怎么协作:Host-Worker 模式(第91篇-E77)
leeyi2026/8/22

Part 16 开篇。前面 15 个 Part 讲的是一个 Agent 怎么做安全、怎么加记忆、怎么接知识库——但单个 Agent 的注意力是有限的。一个 Agent 面对"帮我查北京天气、订机票、比价酒店"这种多维度任务,会在上下文里来回跳,工具一多就乱。 这篇回答一个问题:两个 Agent 怎么协作——Host-Worker 模式,主 Agent 分派、子 Agent 执行,注意力该拆给谁。 两个问题串全篇: Eino 的 Host MultiAgent 怎么让 host LLM 把 s


漫话火山 Milvus|为 Agent、RAG 、语义搜索而生,AI 时代的极致性价比之选
火山引擎Agent社区2026/8/8

托管锁定、自建难扩容、性能和成本难以兼顾? 火山 Milvus,开源兼容、可自由迁移;自研算法优化算力开销,支持 Serverless;联动火山大模型生态,适配多模态 RAG 与 Agent,可控、性能、性价比一站式解决。 火山 Milvus,基于开源 Milvus 构建的全托管数据库服务,提供高效的非结构化数据检索能力,适用于多样化 AI 场景,客户无需再关心底层硬件资源,降低使用成本,提高整体效率。


CSS 现代布局终极方案:Grid 完整实战,替代浮动/弹性布局复杂场景
前端人类学2026/7/30

Hi,我是前端人类学! 从“圣杯”到“卡片墙”,Grid 正在重新定义我们对 Web 布局的想象。 如果你还在用 float 清浮动、用 margin 推间距、用 flex 小心翼翼地嵌套多行网格,那今天这篇文章,值得你多看两眼。 CSS Grid 不是来“卷”谁的,它是来解决问题的——那些你以前觉得“凑合能看但维护起来想删库”的布局问题。 文章目录 一、Grid 凭什么说自己是“终极方案”?二、干掉浮动和复杂 Flex:两个核心实战模式2.1 响应式卡片网格:一行代码,无需媒

首页编辑器站点地图

本站内容在 CC BY-SA 4.0 协议下发布

Copyright © 2026 聚合阅读