建议先阅读: 容器概览, 栈(递归与栈的关系),队列(层序遍历依赖队列)


原理

树(Tree)是计算机科学中最丰富的非线性结构。它是递归定义的自然体现——一棵树的子树仍然是树。这种自相似性使得递归成为树操作的首选范式。

树在哪里

文件系统是一棵倒挂的树——根目录 / 在顶部,子目录层层展开。编译器把源代码解析成抽象语法树(AST),每个表达式是一棵子树。HTML 的 DOM 是一棵树——<html> 是根,每个标签是子节点,CSS 选择器沿着树路径匹配。数据库的 B+ 树索引让百万行查询从全表扫描的 降到 。这些场景的共同主题——层次关系的自然表达与高效检索——正是树的核心用武之地。

术语体系


graph TD
    ROOT["Root 深度=0"] --> A["A 深度=1"]
    ROOT --> B["B 深度=1"]
    A --> C["C d=2"]
    A --> D["D d=2"]
    B --> E["E d=2"]
    C --> F["F d=3"]
    C --> G["G d=3"]
    style ROOT fill:#4a90d9,color:#fff
    style A fill:#5ba3e6,color:#fff
    style B fill:#5ba3e6,color:#fff
    style C fill:#7ec8e3,color:#333
    style D fill:#7ec8e3,color:#333
    style E fill:#7ec8e3,color:#333
    style F fill:#afa,color:#333
    style G fill:#afa,color:#333

节点 F 的高度 = 0 (叶子), 节点 A 的高度 = 2, 树的高度 = 3
节点 F 的深度 = 3 (从根起的边数)

术语定义例(以 F 为参考)
深度(Depth)从根到该节点的边数3
高度(Height)该节点到最深叶子的边数0(叶子)
层(Level)深度 + 1第 4 层
平衡因子(BF)左子树高度 - 右子树高度—

二叉树的性质与计算公式

这一节是选择题的”公式库”。先约定:层从 1 开始(根在第 1 层);若题目把高度定义为”边的条数”,则高度 对应层数 ,套公式前先看题目约定。

(1)基本性质

性质公式说明
第 层最多结点数
层数为 的二叉树最多结点数即满二叉树
叶子数与度为 2 的结点数最高频,直接秒杀
结点总数二叉树只有 0/1/2 度
边数每条边对应一个孩子

的推导:设结点总数 ;除根外每个结点都有一条来自双亲的边,故边数 ;另一方面边数 。联立得 ,即 。

(2)完全二叉树

性质公式 / 结论
结点数 与层数
度为 1 的结点数只能是 或
叶子结点数由 与 联立求
双亲/孩子编号(根为 1)双亲 ;左孩子 ;右孩子
顺序存储所需最大下标层数 的斜树可达

完全二叉树叶子数的快速算法:先求层数 ,最后一层结点数 ;最后一层的父结点数为 (即第 层中有孩子的结点数)。第 层共有 个结点,其中叶子数为 。总叶子数 。例:,,,,叶子 。

(3)二叉链表空指针数

个结点的二叉链表有 个指针域,其中 个指向孩子(除根外每个结点恰有一条入边),故空指针域

线索二叉树正是把这 个空指针改成前驱/后继线索,所以线索数 。

(4)一般树(非二叉树)的结点数与度数

设度为 的结点有 个(),则

联立可求叶子数 。例:度为 4 的树中 ,则边数 ,,。

(5)满 叉树与正则二叉树

概念结论
满 叉树第 层最多 个结点
层数为 的满 叉树总数
正则二叉树(每个分支结点度都为 2);层数 时最少 个结点
满二叉树是正则二叉树的特例,且所有叶子同层

易混:” 叉树”指每个结点最多有 个孩子(允许某些结点度小于 );“度为 的树”指至少有一个结点度为 。两者不是一回事。

树、森林与二叉树的相互转换

(1)树 → 二叉树:左孩子右兄弟

规则只有一句:每个结点的第一个孩子变成它的左孩子,其余孩子依次变成前一个孩子的右孩子(即”左孩子右兄弟”)。

graph TD
  subgraph "树"
    A1["A"] --> B1["B"]
    A1 --> C1["C"]
    A1 --> D1["D"]
  end
  subgraph "转换后的二叉树"
    A2["A"] --> B2["B"]
    B2 --> C2["C"]
    C2 --> D2["D"]
  end
  • 转换是唯一的;
  • 转换后根结点没有右子树(因为根没有兄弟);
  • 树的前序/后序与二叉树遍历的对应见下。

(2)森林 → 二叉树

  1. 先把每棵树各自转成二叉树;
  2. 从第一棵树的根开始,把后一棵树的根作为前一棵树根的右孩子依次串起来。

转换后:

  • 若森林只有一棵树 → 二叉树根无右子树;
  • 若森林有多棵树 → 二叉树根有右子树(右链就是各棵树的根);
  • 森林中树的棵数 = 转换后二叉树根结点沿右链的结点数。

(3)二叉树 → 树 / 森林

逆规则:若结点是双亲的左孩子,则把它作为双亲的第一个孩子;若结点是双亲的右孩子,则把它作为其双亲(左孩子)的下一个兄弟。反复应用即可还原。若二叉树根有右子树,则还原为森林;否则还原为一棵树。

(4)遍历的对应关系

树 / 森林对应二叉树
树的先根遍历二叉树的先序遍历
树的后根遍历二叉树的中序遍历
森林的先根遍历二叉树的先序遍历
森林的后根遍历二叉树的中序遍历

记忆:先根对先序,后根对中序;森林只是把多棵树的根用右链串起来,遍历对应关系不变。

(5)右指针为空的结点数

森林有 个非终端结点,转换成二叉树后,右指针域为空的结点有 个。

直观理解:转换后,一个结点的右指针为空 ⇔ 它没有”下一个兄弟”。森林中每棵树的根、每一条兄弟链的末尾都会贡献一个空右指针,归纳后恰好比非终端结点数多 1。做题直接套 。

二叉树的四种遍历

二叉树遍历是递归应用的经典场景。每种遍历将”处理当前节点”的动作放在递归调用的不同位置:

graph TD
 subgraph "某棵子树"
 ROOT["根"] --> L["左子树"]
 ROOT --> R["右子树"]
 end
 subgraph "前序: 根→左→右"
 P1["1. 访问根"] --> P2["2. 递归遍历左子树"] --> P3["3. 递归遍历右子树"]
 end
 subgraph "中序: 左→根→右"
 I1["1. 递归遍历左子树"] --> I2["2. 访问根"] --> I3["3. 递归遍历右子树"]
 end
 subgraph "后序: 左→右→根"
 O1["1. 递归遍历左子树"] --> O2["2. 递归遍历右子树"] --> O3["3. 访问根"]
 end
遍历方式顺序典型应用
前序(Pre-order)根 → 左 → 右序列化/反序列化([根, 左子树序列, 右子树序列] 唯一确定一棵树)、前缀表达式
中序(In-order)左 → 根 → 右BST 的中序遍历输出升序序列
后序(Post-order)左 → 右 → 根释放树的内存(必须先释放子树再释放根)、后缀表达式、计算目录总大小
层序(Level-order)逐层、从左到右BFS 搜索、判断完全二叉树、二叉树的最大宽度

遍历手算轨迹

以这棵完全二叉树为例:

graph TD
    N1["1"] --> N2["2"]
    N1 --> N3["3"]
    N2 --> N4["4"]
    N2 --> N5["5"]
    N3 --> N6["6"]
    N3 --> N7["7"]
遍历序列过程
前序1, 2, 4, 5, 3, 6, 7根→左→右:先访问 1,递归左子树(2→4→5),递归右子树(3→6→7)
中序4, 2, 5, 1, 6, 3, 7左→根→右:最左 4,回退 2,右 5,回退 1,右子树同理
后序4, 5, 2, 6, 7, 3, 1左→右→根:叶子先输出,根最后
层序1, 2, 3, 4, 5, 6, 7逐层从左到右:BFS 遍历

自测:遍历序列

给定二叉树:

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    B --> E["E"]
    C --> F["F"]

写出前序、中序、后序、层序遍历序列。

答案:

前序:A, B, D, E, C, F
中序:D, B, E, A, C, F
后序:D, E, B, F, C, A
层序:A, B, C, D, E, F

前序+中序唯一确定二叉树:给定前序和中序遍历序列,可以重建一棵二叉树。前序的第一个元素是根,在中序中找出根的位置后,左边是左子树的中序序列,右边是右子树的中序序列。递归即可构建。这是分治思想的典型应用——每个子问题是一个子树的构建。

前序+中序重建手算

给定前序 [A,B,D,E,C,F] 和中序 [D,B,E,A,F,C],重建二叉树:

第 1 步:前序首元素 A 是根。在中序中 A 的位置 → 左子树中序 [D,B,E],右子树中序 [F,C]。

第 2 步:左子树的前序为 [B,D,E],首元素 B 是左子树的根。中序 [D,B,E] 中 B 的位置 → B 的左子树中序 [D],右子树中序 [E]。

第 3 步:D 和 E 都是叶子。

第 4 步:右子树的前序为 [C,F],首元素 C 是右子树的根。中序 [F,C] 中 C 的位置 → C 的左子树中序 [F]。

第 5 步:F 是叶子。

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    B --> E["E"]
    C --> F["F"]

自测:前序 [1,2,4,5,3,6,7] + 中序 [4,2,5,1,6,3,7],画出二叉树。

答案:即正文遍历手算轨迹中的完全二叉树——根 1,左子树(2,4,5),右子树(3,6,7)。

遍历序列的推导与性质

(1)已知两种序列求第三种

  • 前序 + 中序 → 后序:前序首元素是根;在中序中定位根,分出左右子树;递归处理左右子树,最后输出根。
  • 后序 + 中序 → 前序:后序末元素是根;在中序中定位根,分出左右子树;先输出根,再递归左右。
  • 前序 + 后序不能唯一确定二叉树:前序定根,但无法区分”左子树为空”还是”右子树为空”;只有满二叉树(每个结点 0 或 2 个孩子)时,前序+后序才能唯一确定。

手算模板(前序 + 中序):

  1. 前序第一个是根 ;
  2. 在中序中找到 ,左边是左子树中序,右边是右子树中序;
  3. 用左子树结点个数在前序中切出左子树前序,剩下的是右子树前序;
  4. 对左右子树递归。

例:前序 ABCDEF、中序 CBAEDF → 根 A;中序左 CB、右 EDF;左子树前序 BC,根 B,中序 CB → B 的左 C;右子树前序 DEF,根 D,中序 EDF → D 的左 E、右 F。后序为 C B E F D A,即 CBEFDA。

(2)遍历序列的重合 / 相反性质

条件结论原因
前序 = 中序所有结点没有左孩子(只有右子树)前序”根左右”、中序”左根右”;要相同,左必须为空
前序 = 后序只有根结点(非空时)前序根在前、后序根在后,相同只能是单结点
前序与后序相反树是单分支的(每个结点至多一个孩子),等价于只有一个叶子单分支时前序与后序互为逆序
中序 = 后序所有结点没有右孩子(只有左子树)中序”左根右”、后序”左右根”;要相同,右必须为空
叶子结点相对次序在前序、中序、后序中都不变叶子之间没有祖先关系,遍历只改变”根”的位置

注意:“前序与后序相反 ⇒ 只有一个叶子”是必要条件,不是”所有结点都无左孩子/无右孩子”——单分支树可以左右交替(zigzag),所以不能选”所有结点都无左孩子”。

(3)用遍历实现编号 / 交换

  • 要求”双亲编号大于孩子编号”:先访问孩子、后访问双亲 → 后序遍历。
  • 交换所有结点的左右子树:先递归交换左右子树,再交换当前结点的左右孩子 → 后序遍历(前序/中序也能做,但教材标准答案多写后序)。
  • 要求”左孩子编号小于右孩子编号”:在同一层内先左后右,配合后序即可。

其他重要概念

(1)树的存储结构

存储方式做法特点
双亲表示法数组存每个结点 + 双亲下标找双亲 ,找孩子
孩子链表表示法每个结点挂一条孩子链表找孩子方便,找双亲需遍历
孩子兄弟表示法左指针指第一个孩子,右指针指下一个兄弟把树转成二叉树,最常用
顺序存储用数组按下标存只适合完全二叉树;一般树不适用

注意:顺序存储不是”树的标准存储形式”;它只对完全二叉树/满二叉树自然,因为下标能直接算父子关系。

(2)树的度与 叉树

  • 树的度 = 树中所有结点度的最大值;
  • 叉树 = 每个结点最多有 个孩子(允许某些结点度小于 );
  • 度为 的树 = 至少有一个结点恰有 个孩子;
  • 因此” 叉树” “度为 的树”:前者是”上限”,后者是”取到上限”。

(3)表达式树

  • 中缀表达式 → 表达式树:操作数在叶子,运算符在内部结点;
  • 前序遍历 → 前缀(波兰)式;中序遍历 → 中缀式(需补括号);后序遍历 → 后缀(逆波兰)式;
  • 后缀式求值:用栈,遇操作数压栈,遇运算符弹两个操作数计算后压回;
  • 中缀转后缀:调度场算法(见 栈)。

(4)完全二叉树与堆

  • 堆一定是完全二叉树(大根堆/小根堆都用数组顺序存储);
  • 完全二叉树不一定是堆——还必须满足”父结点 ≥/≤ 孩子”的堆序性质;
  • 因此”完全二叉树”是形状条件,“堆”是形状 + 有序性条件,二者不能划等号。

(5)顺序存储的极端情况

层数为 的二叉树用数组顺序存储时,最坏情况是斜树(每层只有一个结点,且一直往右),最后一个结点的下标可达

所以数组至少要开 个单元(下标 )。例:层数 的斜树最大下标为 ,共需要 个存储单元。这也是”完全二叉树适合顺序存储、一般二叉树不适合”的原因。


二叉搜索树(BST)

BST 通过有序性约束将查找从 加速到 (平衡情况下):

性质:对于任意节点 X,
 左子树中的所有节点值 < X 的值 < 右子树中的所有节点值
graph TD
 ROOT["8"] --> L["3"]
 ROOT --> R["10"]
 L --> LL["1"]
 L --> LR["6"]
 LR --> LRL["4"]
 LR --> LRR["7"]
 R --> RR["14"]
 RR --> RRL["13"]

中序遍历这棵 BST:1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14。即升序输出。

BST 的三个操作:

操作平均最坏核心步骤
查找(search)与根比较:小则走左,大则走右
插入(insert)查找到失败位置,在 leaf 的空位上插入
删除(delete)三种情况:叶子(直删)、单子(用子代替)、双子(用后继代替)

BST 删除的三个情况:

graph TD
 subgraph "情况1: 删除叶子节点"
 LEAF["5 → 删除 5"] --> HEALTHY["直接删除, 父节点的 left/right 置 NULL"]
 end
 subgraph "情况2: 单子节点"
 ONE["删除 3, 它有子节点 4"] --> REPLACE["用节点 4 代替节点 3 在父节点中的位置"]
 end
 subgraph "情况3: 双子节点"
 TWO["删除 8, 它有左/右子树"] --> FIND["找到中序后继(右子树的最小值)= 10"]
 FIND --> COPY["将 10 的值复制到 8 的位置"]
 COPY --> DEL10["删除值 10 的原节点(情况1或2)"]
 end

中序后继是 BST 中 key 排序下”正好比当前节点大的下一个节点”。选择它替代被删节点,可以保证 BST 性质完全保持不变——所有左子树的值 < 后继的值 < 所有右子树的值。

BST 删除手算轨迹

以 BST [8, 3, 10, 1, 6, 14, 4, 7, 13] 为例,逐步删除:

初始树:

graph TD
    N8["8"] --> N3["3"]
    N8 --> N10["10"]
    N3 --> N1["1"]
    N3 --> N6["6"]
    N10 --> N14["14"]
    N6 --> N4["4"]
    N6 --> N7["7"]
    N14 --> N13["13"]

删除 7(情况 1:叶子):直接删除,父节点 6 的 right 置 NULL。

graph TD
    N8["8"] --> N3["3"]
    N8 --> N10["10"]
    N3 --> N1["1"]
    N3 --> N6["6"]
    N10 --> N14["14"]
    N6 --> N4["4"]
    N14 --> N13["13"]

删除 6(情况 2:单子):6 只有左子 4,用 4 代替 6 的位置。

graph TD
    N8["8"] --> N3["3"]
    N8 --> N10["10"]
    N3 --> N1["1"]
    N3 --> N4["4"]
    N10 --> N14["14"]
    N14 --> N13["13"]

删除 3(情况 3:双子):3 有左子 1 和右子 4。找中序后继——右子树最小值 = 4。将 4 复制到 3 的位置,删除原 4 节点(叶子)。

graph TD
    N8["8"] --> N4["4"]
    N8 --> N10["10"]
    N4 --> N1["1"]
    N10 --> N14["14"]
    N14 --> N13["13"]

自测:BST 删除

给定 BST [15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9],删除 6 后画出新树(写出所用情况)。

答案:

6 有左子(3)和右子(7) → 情况 3。中序后继 = 右子树最小值 = 7。
用 7 替换 6,删除原 7(叶子)。

graph TD
    N15["15"] --> N7["7"]
    N15 --> N18["18"]
    N7 --> N3["3"]
    N18 --> N17["17"]
    N18 --> N20["20"]
    N3 --> N2["2"]
    N3 --> N4["4"]

右子树:13 和 9 仍在 15 的左子树中——等一下,需要重新检查原始树的结构。

更正:原始 BST 中 13 在 18 的左子树路径上(15→18→17→13 不对)。按 BST 性质,13 < 15 应在 15 的左子树。实际原始树为:15(根), 左子树(6→3→(2,4), 7→(…)), 右子树(18→17, 20)。13 应在 15 的左子树中——它大于 6 小于 15,所以在 6 的右子树中。6 的右子树有 7 和 13。13 > 7 所以在 7 的右子树。删除 6 后 7 替上来,13 仍在 7 的右子树:

graph TD
    N15["15"] --> N7["7"]
    N15 --> N18["18"]
    N7 --> N3["3"]
    N7 --> N13["13"]
    N18 --> N17["17"]
    N18 --> N20["20"]
    N3 --> N2["2"]
    N3 --> N4["4"]

情况 3(双子):用中序后继 7 替换 6。

BST 退化的致命性:

按递增顺序插入 个元素到空 BST:

  • 第一个元素成为根
  • 每个后续元素都比之前的所有元素大
  • 因此每个新元素都是在”最右叶子”上追加

结果是一棵深度为 的单链——退化为链表。此时查找从 变为 。这正是自平衡二叉搜索树存在的根本原因。

AVL 树——通过旋转维持平衡

AVL 树是最早的自平衡 BST(Adelson-Velsky & Landis, 1962)。核心约束:任意节点的左右子树高度差 。

平衡因子(BF):

当插入或删除导致某个节点的 时,需要通过旋转恢复平衡。

四种旋转场景:

graph TD
 subgraph "LL — 右旋"
 LL_BEFORE["节点 X (BF=2)<br/> /<br/> Y (BF=1)<br/> /<br/>Z<br/>失衡: 左子树的左子树太重"]
 LL_BEFORE -->|"右旋(X)"| LL_AFTER["Y<br/>/<br/>Z X<br/>平衡恢复"]
 end
 subgraph "RR — 左旋"
 RR_BEFORE["节点 X (BF=-2)<br/> \\<br/> Y (BF=-1)<br/> \\<br/> Z<br/>失衡: 右子树的右子树太重"]
 RR_BEFORE -->|"左旋(X)"| RR_AFTER["Y<br/>/<br/>X Z<br/>平衡恢复"]
 end
 subgraph "LR — 先左旋后右旋"
 LR_BEFORE["节点 X (BF=2)<br/> /<br/> Y (BF=-1)<br/> \\<br/> Z<br/>失衡: 左子树的右子树太重"]
 LR_BEFORE -->|"左旋(Y) → LL"| LR_MID["X (BF=2)<br/> /<br/> Z<br/> /<br/>Y<br/>变成 LL 情形"]
 LR_MID -->|"右旋(X)"| LR_AFTER["Z<br/>/<br/>Y X<br/>平衡恢复"]
 end
 subgraph "RL — 先右旋后左旋"
 RL_BEFORE["节点 X (BF=-2)<br/> \\<br/> Y (BF=1)<br/> /<br/> Z<br/>失衡: 右子树的左子树太重"]
 RL_BEFORE -->|"右旋(Y) → RR"| RL_MID["X (BF=-2)<br/> \\<br/> Z<br/> \\<br/> Y<br/>变成 RR 情形"]
 RL_MID -->|"左旋(X)"| RL_AFTER["Z<br/>/<br/>X Y<br/>平衡恢复"]
 end

旋转的原理——以 LL 右旋为例:将失衡节点的左子节点”提上来”成为新的子树根,原根成为新根的右子节点。旋转保持了 BST 性质(中序遍历不变),同时将左子树的高度降低了 1,右子树的高度增加了 1——左右高度从不平衡的 2 恢复到 0 或 1。

AVL 建树手算轨迹

给定插入序列 [3, 2, 1, 4, 5, 6, 7],逐步构建 AVL 树并标注旋转类型:

步插入树状态(简化)失衡节点旋转结果
13(3)——BF(3)=0
22(3,(2))——BF(3)=-1
31(3,(2,(1)))3LL右旋 → (2,(1),(3))
44(2,(1),(3,(4)))——BF(3)=-1, BF(2)=-1
55(2,(1),(3,(4,(5))))3RR左旋 → (2,(1),(4,(3),(5)))
66(2,(1),(4,(3),(5,(6))))4,2RR x2先左旋4 → (2,(1),(5,(3),(4),(6)));BF(2)=-2 再左旋2 → (5,(2,(1),(4)),(6))
77(5,(2,(1),(4)),(6,(7)))6RR左旋 → (5,(2,(1),(4)),(7,(6))),检查 5 的 BF:左高=2,右高=1 → BF=1 OK

关键判断:每插入一个节点后,沿路径回溯更新高度,遇到 时根据 BF 值和新插入值的方向判定旋转类型:

  • BF=2 且新值 < 左子值 → LL(右旋)
  • BF=-2 且新值 > 右子值 → RR(左旋)
  • BF=2 且新值 > 左子值 → LR(先左旋后右旋)
  • BF=-2 且新值 < 右子值 → RL(先右旋后左旋)

自测:AVL 建树

插入序列 [10, 20, 30, 25, 28, 27],画出每次插入后的 AVL 树并标注旋转类型。

答案:

① 插入 10:(10) — BF=0

② 插入 20:(10,(20)) — BF(10)=-1

③ 插入 30:(10,(20,(30))) — BF(10)=-2,RR → 左旋 → (20,(10),(30))

④ 插入 25:(20,(10),(30,(25))) — BF(30)=-1, BF(20)=-1

⑤ 插入 28:(20,(10),(30,(25,(28)))) — BF(30)=-2,RR → 左旋 → (20,(10),(28,(25),(30))),BF(20)=-1 OK

⑥ 插入 27:(20,(10),(28,(25,(27)),(30))) — BF(28)=1, BF(20)=-1 → OK 无需旋转

旋转汇总:第 3 步 LL 一次,第 5 步 RR 一次,第 6 步 RR 两次,第 7 步 RR 一次,共 4 次旋转。

AVL 高度上界的推导:

设 为高度为 的 AVL 树中的最小节点数。最”瘦”的 AVL 树是斐波那契树——左右子树高度差恰好为 1:

这与斐波那契数列 有相同的递推关系,因此 ,其中 (黄金比)。由此反推:

即 AVL 树的高度不超过 ,保证查找、插入、删除均为 。AVL 是最严格的平衡二叉搜索树——代价是插入/删除时可能需要 次旋转(向根方向传播)。


实现

BST

#include <stdlib.h>
 
typedef struct BSTNode {
 int data;
 struct BSTNode* left;
 struct BSTNode* right;
} BSTNode;
 
BSTNode* bst_insert(BSTNode* root, int value) {
 if (!root) {
 BSTNode* node = malloc(sizeof(BSTNode));
 node->data = value;
 node->left = node->right = NULL;
 return node;
 }
 if (value < root->data)
 root->left = bst_insert(root->left, value);
 else if (value > root->data)
 root->right = bst_insert(root->right, value);
 return root;
}
 
BSTNode* bst_search(BSTNode* root, int value) {
 if (!root || root->data == value) return root;
 if (value < root->data) return bst_search(root->left, value);
 return bst_search(root->right, value);
}
 
// 删除节点: 返回新的子树根
BSTNode* bst_delete(BSTNode* root, int value) {
 if (!root) return NULL;
 if (value < root->data)
 root->left = bst_delete(root->left, value);
 else if (value > root->data)
 root->right = bst_delete(root->right, value);
 else {
 // 情况1/2: 叶子或单子节点
 if (!root->left) { BSTNode* tmp = root->right; free(root); return tmp; }
 if (!root->right) { BSTNode* tmp = root->left; free(root); return tmp; }
 // 情况3: 双子节点 — 找中序后继
 BSTNode* succ = root->right;
 while (succ->left) succ = succ->left;
 root->data = succ->data; // 替换值
 root->right = bst_delete(root->right, succ->data); // 删除后继
 }
 return root;
}
 
void bst_destroy(BSTNode* root) {
 if (!root) return;
 bst_destroy(root->left);
 bst_destroy(root->right);
 free(root);
}
 
// 树的三种递归遍历
void preorder(BSTNode* root) {
 if (!root) return;
 printf("%d ", root->data);
 preorder(root->left);
 preorder(root->right);
}
 
void inorder(BSTNode* root) {
 if (!root) return;
 inorder(root->left);
 printf("%d ", root->data);
 inorder(root->right);
}
 
void postorder(BSTNode* root) {
 if (!root) return;
 postorder(root->left);
 postorder(root->right);
 printf("%d ", root->data);
}
 
// 层序遍历 (BFS): 依赖队列
void level_order(BSTNode* root) {
 if (!root) return;
 BSTNode** q = malloc(sizeof(BSTNode*) * 1024);
 int front = 0, back = 0;
 q[back++] = root;
 while (front < back) {
  BSTNode* n = q[front++];
  printf("%d ", n->data);
  if (n->left) q[back++] = n->left;
  if (n->right) q[back++] = n->right;
 }
 free(q);
}

AVL 树

typedef struct AVLNode {
 int data;
 int height; // 该节点子树的高度 (叶子=0)
 struct AVLNode* left;
 struct AVLNode* right;
} AVLNode;
 
static int height(AVLNode* n) { return n ? n->height : -1; }
static int max(int a, int b) { return a > b ? a : b; }
static int bf(AVLNode* n) { return height(n->left) - height(n->right); }
 
// 右旋
static AVLNode* rotate_right(AVLNode* y) {
 AVLNode* x = y->left;
 AVLNode* T2 = x->right;
 x->right = y;
 y->left = T2;
 y->height = max(height(y->left), height(y->right)) + 1;
 x->height = max(height(x->left), height(x->right)) + 1;
 return x; // 新根
}
 
// 左旋
static AVLNode* rotate_left(AVLNode* x) {
 AVLNode* y = x->right;
 AVLNode* T2 = y->left;
 y->left = x;
 x->right = T2;
 x->height = max(height(x->left), height(x->right)) + 1;
 y->height = max(height(y->left), height(y->right)) + 1;
 return y;
}
 
AVLNode* avl_insert(AVLNode* root, int value) {
 if (!root) {
 AVLNode* node = malloc(sizeof(AVLNode));
 node->data = value; node->height = 0;
 node->left = node->right = NULL;
 return node;
 }
 if (value < root->data)
 root->left = avl_insert(root->left, value);
 else if (value > root->data)
 root->right = avl_insert(root->right, value);
 else
 return root; // 重复值不插入
 
 root->height = max(height(root->left), height(root->right)) + 1;
 int balance = bf(root);
 
 // LL: 左子树的左子树过重
 if (balance > 1 && value < root->left->data)
 return rotate_right(root);
 // RR: 右子树的右子树过重
 if (balance < -1 && value > root->right->data)
 return rotate_left(root);
 // LR: 左子树的右子树过重
 if (balance > 1 && value > root->left->data) {
 root->left = rotate_left(root->left);
 return rotate_right(root);
 }
 // RL: 右子树的左子树过重
 if (balance < -1 && value < root->right->data) {
 root->right = rotate_right(root->right);
 return rotate_left(root);
 }
 return root;
}

AVL 删除

删除比插入复杂——删除后沿路径回溯更新高度时,失衡可能出现在任意祖先节点,且旋转类型需根据左右子树的高度判断(而非插入时的值比较)。

AVLNode* avl_delete(AVLNode* root, int value) {
 if (!root) return NULL;
 if (value < root->data)
  root->left = avl_delete(root->left, value);
 else if (value > root->data)
  root->right = avl_delete(root->right, value);
 else {
  // 找到目标节点
  if (!root->left || !root->right) {
   AVLNode* tmp = root->left ? root->left : root->right;
   free(root);
   return tmp;
  }
  // 双子节点: 用中序后继替换
  AVLNode* succ = root->right;
  while (succ->left) succ = succ->left;
  root->data = succ->data;
  root->right = avl_delete(root->right, succ->data);
 }
 
 root->height = max(height(root->left), height(root->right)) + 1;
 int balance = bf(root);
 
 // LL: 左子树过高
 if (balance > 1 && bf(root->left) >= 0)
  return rotate_right(root);
 // LR: 左子树的右子树过高
 if (balance > 1 && bf(root->left) < 0) {
  root->left = rotate_left(root->left);
  return rotate_right(root);
 }
 // RR: 右子树过高
 if (balance < -1 && bf(root->right) <= 0)
  return rotate_left(root);
 // RL: 右子树的左子树过高
 if (balance < -1 && bf(root->right) > 0) {
  root->right = rotate_right(root->right);
  return rotate_left(root);
 }
 return root;
}

与插入的关键区别:插入时只需检查一次旋转(因为插入只影响一条路径上的一个节点)。删除后回溯过程中,每个祖先都可能失衡,且旋转后子树高度可能继续变化,因此旋转判断条件不同——插入用 value 与子节点值比较,删除用 bf() 直接判断子树平衡因子。

哈夫曼树构建

从频率数组构建哈夫曼树——每次取两个最小频率节点合并为新节点,直到剩余一个根节点。使用最小堆加速选取过程。

typedef struct HuffNode {
 int freq;
 struct HuffNode *left, *right;
} HuffNode;
 
// 用最小堆构建哈夫曼树
// freq: 字符频率数组, n: 字符数
HuffNode* huffman_build(int* freq, int n) {
 if (n <= 0) return NULL;
 
 // 构建叶子节点最小堆
 HuffNode** heap = malloc(sizeof(HuffNode*) * n);
 int heap_size = 0;
 for (int i = 0; i < n; i++) {
  if (freq[i] <= 0) continue;
  HuffNode* node = malloc(sizeof(HuffNode));
  node->freq = freq[i];
  node->left = node->right = NULL;
  heap[heap_size++] = node;
 }
 
 // Floyd 建堆 O(n)
 for (int i = heap_size / 2 - 1; i >= 0; i--) {
  int idx = i;
  while (1) {
   int smallest = idx;
   int l = 2 * idx + 1, r = 2 * idx + 2;
   if (l < heap_size && heap[l]->freq < heap[smallest]->freq) smallest = l;
   if (r < heap_size && heap[r]->freq < heap[smallest]->freq) smallest = r;
   if (smallest == idx) break;
   HuffNode* t = heap[idx]; heap[idx] = heap[smallest]; heap[smallest] = t;
   idx = smallest;
  }
 }
 
 // 反复合并最小的两个
 while (heap_size > 1) {
  // extract min
  HuffNode* min1 = heap[0];
  heap[0] = heap[--heap_size];
  int idx = 0;
  while (1) {
   int smallest = idx;
   int l = 2 * idx + 1, r = 2 * idx + 2;
   if (l < heap_size && heap[l]->freq < heap[smallest]->freq) smallest = l;
   if (r < heap_size && heap[r]->freq < heap[smallest]->freq) smallest = r;
   if (smallest == idx) break;
   HuffNode* t = heap[idx]; heap[idx] = heap[smallest]; heap[smallest] = t;
   idx = smallest;
  }
 
  // extract min
  HuffNode* min2 = heap[0];
  heap[0] = heap[--heap_size];
  idx = 0;
  while (1) {
   int smallest = idx;
   int l = 2 * idx + 1, r = 2 * idx + 2;
   if (l < heap_size && heap[l]->freq < heap[smallest]->freq) smallest = l;
   if (r < heap_size && heap[r]->freq < heap[smallest]->freq) smallest = r;
   if (smallest == idx) break;
   HuffNode* t = heap[idx]; heap[idx] = heap[smallest]; heap[smallest] = t;
   idx = smallest;
  }
 
  // 合并
  HuffNode* parent = malloc(sizeof(HuffNode));
  parent->freq = min1->freq + min2->freq;
  parent->left = min1;
  parent->right = min2;
 
  // 插入堆并上浮
  heap[heap_size++] = parent;
  int pos = heap_size - 1;
  while (pos > 0) {
   int p = (pos - 1) / 2;
   if (heap[p]->freq <= heap[pos]->freq) break;
   HuffNode* t = heap[p]; heap[p] = heap[pos]; heap[pos] = t;
   pos = p;
  }
 }
 
 HuffNode* root = heap[0];
 free(heap);
 return root;
}

时间复杂度 ( 次 extract + insert,每次 )。空间 。

树的其他重要变体

表达式树(Expression Tree):编译器将数学表达式解析为二叉树——操作数在叶子,运算符在内部节点。后序遍历即得到后缀表达式(RPN),可以直接求值。

graph TD
    MUL["*"] --> ADD["+"]
    MUL --> SUB["-"]
    ADD --> T3["3"]
    ADD --> T4["4"]
    SUB --> T5["5"]
    SUB --> T2["2"]
    style MUL fill:#4a90d9,color:#fff
    style ADD fill:#5ba3e6,color:#fff
    style SUB fill:#5ba3e6,color:#fff

后序遍历: 3 4 + 5 2 - * → 后缀表达式 → 求值结果 21

线索二叉树(Threaded Binary Tree):将空的 left/right 指针改为指向中序的前驱/后继的线索(thread)。遍历时无需递归或栈——从第一个节点出发,沿线索可以连续访问中序后继。内存开销为每个节点 2 bit(标记 left/right 是真指针还是线索)。线索二叉树将 空间的遍历栈需求压缩到常数空间。

线索二叉树详解

定义:对于二叉树中的空指针:

  • 若节点的 left 为空,令 left 指向其中序前驱(in-order predecessor)
  • 若节点的 right 为空,令 right 指向其中序后继(in-order successor)
  • 增加标志位 ltag/rtag:0 表示真子节点,1 表示线索

线索化过程:中序遍历一遍,在遍历过程中记录前一个访问的节点 prev。若当前节点 left 为空,则 left = prev(指向前驱);若 prev 的 right 为空,则 prev->right = curr(指向后继)。

typedef struct ThreadNode {
 int data;
 struct ThreadNode *left, *right;
 int ltag, rtag; // 0=子节点, 1=线索
} ThreadNode;
 
static ThreadNode* prev = NULL;
 
void inorder_thread(ThreadNode* node) {
 if (!node) return;
 inorder_thread(node->left); // 左
 
 // 处理当前节点的线索
 if (!node->left) {
 node->ltag = 1;
 node->left = prev; // 指向前驱
 }
 if (prev && !prev->right) {
 prev->rtag = 1;
 prev->right = node; // 前驱的右指针指向当前(后继)
 }
 prev = node;
 
 inorder_thread(node->right); // 右
}

线索化手算轨迹

给定二叉树(中序序列为 D, B, A, E, C):

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> E["E"]
步当前节点leftright动作线索状态
1DNULLNULLD 的 left 指向 NULL(无前驱),D 的 right 指向 B(后继)D→B
2BDNULLB 的 right 指向 A(后继)D→B→A
3ABCA 的 left/right 都非空,无线索—
4ENULLNULLE 的 left 指向 A(前驱),E 的 right 指向 C(后继)A→E→C
5CENULLC 的 left = E(已处理),C 的 right 指向 NULL(无后继)—

最终线索化后,沿线索遍历:D → B → A → E → C(中序序列),无需栈。

自测:线索二叉树

二叉树中序序列为 G, D, H, B, E, A, C, F。① 画出线索二叉树(标注 ltag/rtag)。② 写出从节点 G 出发沿线索遍历的序列。

答案:

① 线索(ltag=1 表示线索,rtag=1 表示线索):

  • G: left=NULL(ltag=1,无前驱), right=D(rtag=1,后继)
  • D: left=G(ltag=1,前驱), right=H(rtag=1,后继)
  • H: left=D(ltag=1,前驱), right=B(rtag=1,后继)
  • B: left=D(ltag=1,前驱), right=E(rtag=1,后继)
  • E: left=B(ltag=1,前驱), right=A(rtag=1,后继)
  • A: left=B(ltag=1,前驱), right=C(rtag=1,后继)
  • C: left=A(ltag=1,前驱), right=F(rtag=1,后继)
  • F: left=C(ltag=1,前驱), right=NULL(rtag=1,无后继)

② 从 G 出发沿线索遍历:G → D → H → B → E → A → C → F

线索树中找前驱 / 后继的规则(中序线索)

目标规则
结点 X 的前驱若 ltag==1(无左孩子),left 直接指向前驱;否则前驱 = 左子树中最右下的结点(一直沿右指针走到底)
结点 X 的后继若 rtag==1(无右孩子),right 直接指向后继;否则后继 = 右子树中最左下的结点(一直沿左指针走到底)
第一个访问的结点从根出发一路向左,走到 ltag==1 的结点
最后一个访问的结点从根出发一路向右,走到 rtag==1 的结点

口诀:前驱在左子树的最右,后继在右子树的最左;只有孩子为空时才用线索。

线索数 = 空指针数 = n+1: 个结点有 个指针域,其中 个指向孩子,剩下 个空指针全部改成线索。线索二叉树的目的就是加快找前驱/后继,并能不用栈、不用递归地中序遍历。

哈夫曼树(Huffman Tree):贪心构造的最优前缀编码二叉树。权值最小的两个节点不断合并为新节点,最终形成一棵最优的二叉树——高频字符靠近根,低频字符在深层。这是数据压缩的基础算法。

哈夫曼编码手算

给定字符频率表:a=5, b=9, c=12, d=13, e=16, f=45。

构建过程(每次合并两个最小频率):

步合并结果频率剩余节点
1a(5) + b(9)(14)(14), c(12), d(13), e(16), f(45)
2c(12) + d(13)(25)(14), e(16), (25), f(45)
3(14) + e(16)(30)(25), (30), f(45)
4(25) + (30)(55)f(45), (55)
5f(45) + (55)(100)(100) ← 根

编码(左分支=0,右分支=1):

graph TD
    ROOT["(100)"] --> F["f=45"]
    ROOT --> N55["(55)"]
    N55 --> N25["(25)"]
    N55 --> N30["(30)"]
    N25 --> C["c=12"]
    N25 --> D["d=13"]
    N30 --> N14["(14)"]
    N30 --> E["e=16"]
    N14 --> A["a=5"]
    N14 --> B["b=9"]
字符编码频率x位数
f045x1 = 45
c10012x3 = 36
d10113x3 = 39
a11005x4 = 20
b11019x4 = 36
e11116x3 = 48

总加权路径长度 。若用等长编码(3 位/字符),总位数 。哈夫曼编码节省 。

自测:哈夫曼

频率表:A=27, B=8, C=15, D=15, E=30, F=5。构建哈夫曼树并写出 F 和 B 的编码。

答案:

步骤:F(5)+B(8)→13;13+C(15)→28;D(15)+A(27)→42;28+E(30)→58;42+58→100

graph TD
    ROOT["(100)"] --> N42["(42)"]
    ROOT --> N58["(58)"]
    N42 --> D["D=15"]
    N42 --> A["A=27"]
    N58 --> N28["(28)"]
    N58 --> E["E=30"]
    N28 --> N13["(13)"]
    N28 --> C["C=15"]
    N13 --> F["F=5"]
    N13 --> B["B=8"]

F 的编码:1000(根→右→左→左→左)
B 的编码:1001(根→右→左→左→右)

哈夫曼树的拓展与性质

(1)结点数公式

个叶子结点的哈夫曼树,总结点数为

因为哈夫曼树是正则二叉树(每个分支结点都有两个孩子),由 得 ,总数 。反过来,若已知哈夫曼树有 个结点,则叶子数 。

(2)结构性质

  • 哈夫曼树没有度为 1 的结点;
  • 哈夫曼树不一定是完全二叉树(选择题高频错误项);
  • 权值越大的叶子离根越近(不是越远);
  • 两个权值最小的结点在构造的第一步被合并,一定是兄弟;
  • 任一非叶结点的权值不小于其孩子结点的权值。

(3) 叉哈夫曼树(拓展)

叉哈夫曼树要求每个分支结点恰有 个孩子(严格 叉)。若叶子数 不满足

则需要补充若干个权值为 0 的虚叶子,使条件成立。需补的个数为

例:三叉哈夫曼树(),若叶子数 ,,需补 个虚叶子,变成 7 个叶子再构造。

(4)前缀码的判断与译码

  • 前缀码:任何一组编码中,没有一个编码是另一个编码的前缀。哈夫曼编码一定是前缀码。
  • 判断方法:把编码按长度排序,逐对检查短码是否为长码的前缀;或把编码建成 Trie,若某个编码结点还有孩子,则它不是前缀码。
  • 译码:从哈夫曼树根出发,读 0 走左、读 1 走右,到达叶子就输出该字符并回到根,继续读下一位。

例:编码集 {0, 1, 00, 11} 不是前缀码(0 是 00 的前缀,1 是 11 的前缀);{0, 10, 110, 111} 是前缀码。

高频考点(含真题与典型例题)

这一节把树与二叉树的选择题考点集中起来:先给结论,再给真题与典型例题。题目按考点分组,只讲思路,不引用题号。

概念考点速记

1. 树、森林 ↔ 二叉树

项目规则 / 结论
树 → 二叉树左孩子右兄弟;转换唯一;根无右子树
森林 → 二叉树各树先转二叉树,再把后一棵树的根作为前一棵根的右孩子
二叉树 → 树/森林逆规则;根有右子树 → 森林,无右子树 → 树
树先根 / 森林先根= 二叉树先序
树后根 / 森林后根= 二叉树中序
右指针空森林有 个非终端结点 → 二叉树右空指针 个

2. 核心公式

公式说明
任何二叉树(最高频)
第 层 ≤ 从 1 开始
层数 的二叉树 ≤ 满二叉树
完全二叉树层数 个结点
完全二叉树度为 1 的结点只能是 0 或 1
二叉链表空指针
一般树 边数 = 各度贡献
满 叉树第 层 ≤ 从 1 开始
层数 满 叉树总数
正则二叉树层数 最少
哈夫曼树 叶总 ,无度 1
线索数

3. 遍历性质

条件结论
前序 = 中序所有结点无左孩子(只有右子树)
中序 = 后序所有结点无右孩子(只有左子树)
前序 = 后序只有根结点
前序与后序相反单分支树 ⇔ 只有一个叶子
叶子相对次序三种遍历都不变
双亲编号 > 孩子后序遍历
交换左右子树后序遍历(教材标准答案)
前序 + 中序 / 后序 + 中序唯一确定树
前序 + 后序一般不唯一(满二叉树才唯一)

4. 线索二叉树

目标规则
前驱(有左孩子)左子树最右结点
后继(有右孩子)右子树最左结点
无左孩子left 线索直接指前驱
无右孩子right 线索直接指后继
目的加快找前驱/后继,遍历不用栈
线索数

5. 哈夫曼树

  • 个叶子 → 总 ;无度为 1 的结点;不一定是完全二叉树;权大离根近;最小两权值必为兄弟;
  • 叉哈夫曼: 时补权 0 虚叶子,补 个;
  • 前缀码:没有任何编码是另一个的前缀;哈夫曼编码必为前缀码;译码从根按 0/1 走到叶子。

6. 其他

  • 正则二叉树:每个分支结点度 2,,层数 最少 ;
  • 满 叉树:第 层 ,总数 ;
  • 树的存储:双亲表示、孩子链表、孩子兄弟;顺序存储只适合完全二叉树;
  • 叉树 ≠ 度为 的树(前者是上限,后者是取到上限);
  • 完全二叉树 ≠ 堆(堆还要满足堆序);
  • 顺序存储斜树:层数 需要 个单元(最大下标 )。

真题与典型例题

一、树、森林与二叉树的转换

QUIZ
question: 把一棵树转换为二叉树后,这棵二叉树的形态是( )。
A: 唯一的
B: 有多种
C: 有多种,但根结点都没有左孩子
D: 有多种,但根结点都没有右孩子
answer: A
explanation: 左孩子右兄弟规则是确定的,所以转换唯一;转换后根结点没有右子树(D 的"有多种"表述错误)。
QUIZ
question: 利用二叉链表存储树,则根结点的右指针是( )。
A: 指向最左孩子
B: 指向最右孩子
C: 空
D: 非空
answer: C
explanation: 树转成二叉树后,根没有兄弟,因此没有右孩子,右指针为空。
QUIZ
question: 设森林 F 中有 n 个非终端结点,B 是由 F 转换得到的二叉树,则 B 中右指针域为空的结点有( )个。
A: n-1
B: n
C: n+1
D: n+2
answer: C
explanation: 这是转换的固定结论:右空指针数 = n+1。可用"每个非终端结点贡献一条孩子兄弟链,末尾多一个空右指针"来理解。
QUIZ
question: 树的后根遍历序列等同于该树对应二叉树的( )。
A: 先序序列
B: 中序序列
C: 后序序列
answer: B
explanation: 记忆:**先根对先序,后根对中序**;森林的后根遍历同样对应二叉树的中序。

二、二叉树的性质与公式

QUIZ
question: 由 3 个结点可以构造出多少种不同的二叉树?
A: 2
B: 3
C: 4
D: 5
answer: D
explanation: n 个结点不同形态二叉树数为卡特兰数 Cₙ,C₃ = 1/4C(6,3) = 5。
QUIZ
question: 一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是( )。
A: 250
B: 500
C: 254
D: 501
answer: D
explanation: 层数 h = ⌊ log₂ 1001⌋+1 = 10;最后一层 1001-(2⁹-1) = 490 个;其父结点 ⌈490/2⌉ = 245 个;第 9 层共 2⁸ = 256 个,其中叶子 256-245 = 11 个;叶子总数 490+11 = 501。
QUIZ
question: 一个具有 1025 个结点的二叉树的高 h 为( )。
A: 11
B: 10
C: 11 至 1025 之间
D: 10 至 1024 之间
answer: C
explanation: 最矮是接近完全二叉树:⌊ log₂ 1025⌋+1 = 11;最高是单链:h = 1025。所以范围是 11 至 1025。
QUIZ
question: 在一棵具有 5 层的满二叉树中,结点总数为( )。
A: 31
B: 32
C: 33
D: 16
answer: A
explanation: 层数 h = 5 的满二叉树总数 2ʰ-1 = 31。
QUIZ
question: 若一棵二叉树具有 10 个度为 2 的结点、5 个度为 1 的结点,则度为 0 的结点个数是( )。
A: 9
B: 11
C: 15
D: 不确定
answer: B
explanation: 由 n₀ = n₂+1 = 10+1 = 11,与度为 1 的结点数无关。
QUIZ
question: 具有 100 个结点的二叉树中,若用二叉链表存储,其中空指针域的个数是( )。
A: 50
B: 99
C: 100
D: 101
answer: D
explanation: n 个结点的二叉链表空指针数 = n+1 = 101。
QUIZ
question: 设树 T 的度为 4,其中度为 1、2、3、4 的结点个数分别为 4、2、1、1,则 T 中的叶子数为( )。
A: 5
B: 6
C: 7
D: 8
answer: D
explanation: 边数 = 1×4+2×2+3×1+4×1 = 15,总结点 n = 16;叶子 n₀ = 16-(4+2+1+1) = 8。
QUIZ
question: 在一棵三元树中,度为 3 的结点数为 2,度为 2 的结点数为 1,度为 1 的结点数为 2,则度为 0 的结点数为( )。
A: 4
B: 5
C: 6
D: 7
answer: C
explanation: 边数 = 3×2+2×1+1×2 = 10,n = 11;叶子 n₀ = 11-(2+1+2) = 6。
QUIZ
question: 对于有 n 个结点的二叉树,其高度为( )。
A: n log₂ n
B: log₂ n
C: ⌊ log₂ n⌋+1
D: 不确定
answer: D
explanation: 只有在"完全二叉树"或"最矮"的前提下才是 ⌊ log₂ n⌋+1;一般二叉树可能退化成链,高度可达 n。

三、遍历序列

QUIZ
question: 已知某二叉树的后序遍历序列是 `dabec`,中序遍历序列是 `debac`,它的前序遍历序列是( )。
A: `acbed`
B: `decab`
C: `deabc`
D: `cedba`
answer: D
explanation: 后序末元素 `c` 是根;中序中 `c` 在最后 → 无右子树;左子树后序 `dabe`、中序 `deba`,根 `e`;继续分治得前序 `c e d b a`,即 `cedba`。
QUIZ
question: 已知一棵二叉树的前序遍历结果为 `ABCDEF`,中序遍历结果为 `CBAEDF`,则后序遍历的结果为( )。
A: `CBEFDA`
B: `FEDCBA`
C: `CBEDFA`
D: 不定
answer: A
explanation: 根 `A`;左子树中序 `CB`、前序 `BC`,根 `B`、左孩子 `C`;右子树中序 `EDF`、前序 `DEF`,根 `D`、左 `E`、右 `F`。后序 `C B E F D A`。
QUIZ
question: 二叉树的先序遍历为 `EFHIGJK`,中序遍历为 `HFIEJKG`,该二叉树根的右子树的根是( )。
A: `E`
B: `F`
C: `G`
D: `H`
answer: C
explanation: 根 `E`;中序中 `E` 左边 `HFI`、右边 `JKG`,右子树有 3 个结点;前序中右子树为 `GJK`,首元素 `G` 即右子树的根。
QUIZ
question: 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( )。
A: 所有结点均无左孩子
B: 所有结点均无右孩子
C: 只有一个叶子结点
D: 任意二叉树
answer: C
explanation: 先序与后序相反 ⇔ 单分支树(每个结点至多一个孩子),单分支树恰好只有一个叶子。注意单分支树可以左右交替,所以 A、B 不一定成立。
QUIZ
question: 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序( )。
A: 不发生变化
B: 发生变化
C: 不能确定
answer: A
explanation: 叶子之间没有祖先关系,遍历只改变"根"的访问位置,不改变叶子之间的左右相对次序。
QUIZ
question: 对二叉树的结点从 1 开始连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中左孩子的编号小于右孩子,可采用( )遍历实现。
A: 先序
B: 中序
C: 后序
D: 层次
answer: C
explanation: 要求"孩子先编号、双亲后编号",正是后序"左右根"的顺序。
QUIZ
question: 若二叉树采用二叉链表存储,要交换其所有分支结点左、右子树的位置,利用( )遍历方法最合适。
A: 前序
B: 中序
C: 后序
D: 层次
answer: C
explanation: 先递归交换左右子树,再交换当前结点的左右孩子;教材标准答案写后序(前序/中序也能实现,但后序最自然)。

四、线索二叉树

QUIZ
question: 若 X 是二叉中序线索树中一个有左孩子的结点,且 X 不为根,则 X 的前驱为( )。
A: X 的双亲
B: X 的右子树中最左的结点
C: X 的左子树中最右结点
D: X 的左子树中最右叶结点
answer: C
explanation: 前驱 = 左子树"最右下的结点"(不一定是叶子,只要没有右孩子即可)。
QUIZ
question: 引入二叉线索树的目的是( )。
A: 加快查找结点的前驱或后继的速度
B: 方便插入删除
C: 方便找双亲
D: 使遍历结果唯一
answer: A
explanation: 线索把 n+1 个空指针改为前驱/后继,遍历时不需要栈或递归。

五、哈夫曼树

QUIZ
question: 设哈夫曼树中有 199 个结点,则该哈夫曼树中有( )个叶子结点。
A: 99
B: 100
C: 101
D: 102
answer: B
explanation: 哈夫曼树总点数 2n-1 = 199,解得 n = 100。
QUIZ
question: 有 n 个叶子的哈夫曼树的结点总数为( )。
A: 不确定
B: 2n
C: 2n+1
D: 2n-1
answer: D
explanation: 哈夫曼树是正则二叉树,n₂ = n-1,总数 n+(n-1) = 2n-1。
QUIZ
question: n(n≥2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述中,错误的是( )。
A: 该树一定是一棵完全二叉树
B: 树中一定没有度为 1 的结点
C: 两个权值最小的结点一定是兄弟结点
D: 任一非叶结点的权值一定不小于下一层任一结点的权值
answer: A
explanation: 哈夫曼树不一定是完全二叉树;B、C、D 都是哈夫曼树的性质。
QUIZ
question: 下述编码中哪一个不是前缀码?
A: `{00, 01, 10, 11}`
B: `{0, 1, 00, 11}`
C: `{0, 10, 110, 111}`
D: `{1, 01, 000, 001}`
answer: B
explanation: `0` 是 `00` 的前缀,`1` 是 `11` 的前缀;其余三组都没有"一个是另一个前缀"的情况。

六、其他概念

QUIZ
question: 在下列存储形式中,( )不是树的存储形式。
A: 双亲表示法
B: 孩子链表表示法
C: 孩子兄弟表示法
D: 顺序存储表示法
answer: D
explanation: 前三种是树的经典存储;顺序存储只适合完全二叉树,不是一般树的通用存储形式。
QUIZ
question: 树型结构最适合用来表示( )。
A: 有序数据元素
B: 元素之间具有分支层次关系的数据
C: 无序数据元素
D: 元素之间无联系的数据
answer: B
explanation: 树的本质是层次关系(一对多),不是简单的线性次序。
QUIZ
question: 在下述结论中,正确的是( )。
A: ①②③
B: ②③④
C: ②④
D: ①④
answer: D
explanation: ① 单结点度为 0,正确;② 二叉树度可以是 0/1/2,错误;③ 左右子树有序,不能任意交换,错误;④ 完全二叉树结点数不超过同深度满二叉树,正确。
QUIZ
question: 一棵完全二叉树一定是一棵( )。
A: 堆
B: 哈夫曼树
C: 二叉排序树
D: 平衡二叉树
E: 以上都不是
answer: E
explanation: 完全二叉树只保证"形状",不保证堆序、BST 序或平衡性;堆一定是完全二叉树,但反过来不成立。这类题若选项中没有"以上都不是",要警惕题目本身不严谨。

各语言标准库对比

语言树 / 平衡树容器说明
C无(手写)标准库不提供树容器,需手写 BST/AVL
C++std::map / std::set(红黑树)有序关联容器,查找/插入/删除
JavaTreeMap / TreeSet(红黑树)有序 Map/Set;HashMap 是哈希表
Python无内置平衡树dict 是哈希表;需要有序树可用 sortedcontainers
RustBTreeMap / BTreeSet标准库用 B 树实现有序映射
Go无内置需手写或用第三方库

工程结论:需要有序遍历/范围查询时选平衡树,只需要键值查找时选哈希表。C++/Java 的 map 是红黑树,Rust 的 BTreeMap 是 B 树——都是”有序 + “的不同实现。


应用场景

  • 文件系统 (目录树):Linux 的 dentry cache 使用树结构组织路径。每个目录是一个节点,子目录/文件是子节点
  • 数据库索引:BST → AVL → 红黑树 → B+树。自平衡 BST 是 B+树的元实现基础。详见 红黑树 和 B树
  • 编译器 语法树 (AST):编译器将源代码解析为抽象语法树——每个产生式规则对应一个节点,终结符在叶子
  • 域名系统 (DNS):域名本身就是一棵倒挂的树——根域 . → 顶级域 .com → 二级域 example → 主机名 www
  • 计算机网络 路由表:IP 路由的最长前缀匹配算法使用 Patricia Trie(压缩二叉 Trie)

练习

题号题目说明
94二叉树的中序遍历树遍历
98验证二叉搜索树BST 性质
108将有序数组转换为 BST构建平衡树
450删除二叉搜索树中的节点BST 删除三种情况
105从前序与中序构造二叉树前序+中序重建
222完全二叉树的节点个数树的性质

核心推演清单

练习题与上面的 LeetCode 互补——侧重手算推演,全部在正文中带完整答案:

自测位置内容
遍历序列 ×1 问遍历手算轨迹节四种遍历的序列输出
前序+中序重建 ×1 问重建手算节从序列画出二叉树
BST 删除 ×1 问BST 删除手算节三种情况的逐步操作
AVL 建树 ×1 问AVL 建树手算节逐步画树+标注旋转类型
哈夫曼编码 ×1 问哈夫曼手算节构建树+写出编码
树/森林转二叉树转换节左孩子右兄弟、根无右子树、右空指针
性质公式性质节、层/高度上限、完全二叉树叶子数
遍历序列互推遍历性质节前序+中序/后序+中序、前序+后序不唯一
线索树前驱/后继线索树节左子树最右、右子树最左
哈夫曼拓展哈夫曼拓展节、 叉补虚叶、前缀码

动手实验

编号题目说明
E1四种遍历递归 vs 迭代实现中序遍历的递归版和迭代版(用显式栈),对随机生成的 1000 节点 BST 分别执行并计时。对比递归的隐式栈和迭代的显式栈的性能差异
E2BST 退化的渐进分析随机顺序插入 1..10000 到 BST,每插入 1000 个测量一次树高,画出”树高 vs 插入量”曲线。再以递增顺序(1,2,3…)插入同样值——观察退化链的高 = n。解释差距的数学来源
E3AVL 旋转计数随机插入 1..10000 到 AVL,统计 LL/RR/LR/RL 四种旋转各自发生了多少次。验证 LR 和 RL 的发生频率是否显著低于 LL 和 RR