树与二叉树的定义与基本概念

2026 大纲 四（一）树的基本概念、四（二）1 二叉树的定义及其主要特性、四（二）2 二叉树的顺序存储结构和链式存储结构 三条，本篇同时承载。

树的定义为什么非递归不可

树是 $n\ge 0$ 个结点的有限集：$n=0$ 是空树；$n>0$ 时有且仅有一个根，其余结点分成 $m\ge 0$ 个互不相交的有限集，每个本身又是一棵树，称为根的子树。

定义里"子树本身又是一棵树"这句自我引用不是偷懒，是没有别的写法。树的层数事先不知道——用"根、孩子、孙子……"逐层列举来定义，就必须先固定层数，可树的高度是任意的。递归定义把"任意深"压成一句话，代价是后面所有关于树的算法与证明也天然是递归的：求高度、数结点、四种遍历，写出来几乎全是三行递归。根源就在这里。

"互不相交"这个词也删不得，它一次挡住两件事：

• 共享结点——若两棵子树共用一个结点，那个结点就有两个双亲，"从根到它的路径"不再唯一；
• 成环——若子树里含有自己的祖先，从根出发可以无限走下去，递归不终止。

删掉这个条件得到的结构就是图。图的遍历必须额外记"访问过没有"，树的遍历不用——这个便利完全来自"互不相交"。换个说法：树是"连通且无回路"的图，$n$ 个结点的树恰有 $n-1$ 条边，多一条必成环、少一条必不连通。

术语：先把三处约定钉死

            A          ← 根结点（第 1 层）
          / | \
        B   C   D      ← 第 2 层
       / \     / \
      E   F   G   H    ← 第 3 层
         /
        I              ← 第 4 层

大部分术语看一眼就懂，先说三处不钉死就会算错的约定。

第一，层次从 1 起算。 本站与严蔚敏教材一致，根在第 1 层，所以高度为 $h$ 的树有 $h$ 层。少数材料从 0 起算，那样所有公式里的 $h$ 都要减 1。做题以题面给的定义为准；题面没给，按根在第 1 层。

第二，"路径长度"数的是边，不是点。 $A\to I$ 经过 $A,B,F,I$ 共 4 个结点、3 条边，路径长度是 3。而"查找时的比较次数"数的是结点数，是 4。哈夫曼树的 WPL 用边数口径，二叉排序树的 ASL 用结点数口径，两者差 1，混用是这一章最容易算错的地方。

第三，"结点的高度"数的是结点数。 从该结点到最远叶子路径上的结点个数，所以叶子的高度是 1 不是 0。树的高度就是根的高度，也等于最大层次。

其余术语对着上图看一遍就够：

术语	定义（括号内为上图示例）
结点的度 / 树的度	该结点的子树个数 ／ 全树结点度的最大值（$A$ 度 3、$C$ 度 0，树的度 3）
叶子（终端）/ 分支结点	度为 0 ／ 度 $>0$（$C,E,G,H,I$ ／ $A,B,D,F$）
孩子 / 双亲 / 兄弟 / 堂兄弟	子树的根是孩子、该结点是双亲；同双亲互称兄弟；双亲同层但不同的是堂兄弟（$E$ 与 $G$）
祖先 / 子孙	根到该结点路径上的所有结点是它的祖先，反之为子孙（$I$ 的祖先 $F,B,A$）
带权路径长度	结点的权 × 它到根的路径长度，见 哈夫曼树
有序树 / 森林	子树从左到右有次序（交换两棵子树就是另一棵树）／ $m\ge 0$ 棵互不相交的树的集合

顺带把森林、树、结点三者的转化关系记住，它是后面"森林 ↔ 二叉树"转换的地基：一棵树删去根得到一个森林（原来的各棵子树）；一个森林加一个公共根得到一棵树；一棵树本身就是只含一棵树的森林；空集是合法的森林（$m=0$），但不是一棵合法的树。

一般树 / m 叉树的四条性质与推导（做"度为 m 的树"计算题时展开）

T1：结点数 = 所有结点的度之和 + 1，即 $n=\sum _{v}d(v)+1$。

证明（边数双计数）：树中每条边恰好由一个结点"射出"（从双亲指向孩子），所以边数 $=\sum _{v}d(v)$；另一方面除根之外每个结点恰有一条边"射入"，所以边数 $=n-1$。两式相等即得。这条是二叉树性质 3 的母版，凡"给定各度结点个数、求总结点数"的题一律用它列方程。

T2：度为 $m$ 的树第 $i$ 层至多有 $m^{i-1}$ 个结点。 对 $i$ 归纳：$i=1$ 时只有根，$m^0=1$；设第 $i-1$ 层至多 $m^{i-2}$ 个，每个至多 $m$ 个孩子，故第 $i$ 层至多 $m^{i-1}$ 个。

T3：高度为 $h$ 的 $m$ 叉树至多 ${\displaystyle \frac{m^h-1}{m-1}}$ 个结点。 把 T2 各层上界求和（首项 1、公比 $m$ 的等比数列）：

$$\sum _{i=1}^h{m}^{i-1}=\frac{m^h-1}{m-1}$$

$m=2$ 时退化为 $2^h-1$，就是二叉树的性质 2。

T4：$n$ 个结点的 $m$ 叉树最小高度为 $\lceil {\log }_m(n(m-1)+1)\rceil$。 高度最小意味着每层都塞满，由 T3 要装下 $n$ 个必须

$$\frac{m^h-1}{m-1}\ge n⟹m^h\ge n(m-1)+1⟹h\ge {\log }_m(n(m-1)+1)$$

$h$ 取整数即得。

边界提醒："度为 $m$ 的树"和"$m$ 叉树"不是一回事。$m$ 叉树要求每个结点至多 $m$ 个孩子，允许所有结点的度都小于 $m$；度为 $m$ 的树要求至少存在一个度恰为 $m$ 的结点。求"最少结点数"时这个差别会直接改变答案。

二叉树不是"度为 2 的有序树"

二叉树：或为空集，或由一个根和两棵互不相交的左、右子树组成。三个要点——至多两棵子树、严格区分左右、允许为空。

   空树      只有根      只有左子树     只有右子树     左右都有
              ●             ●              ●             ●
                           /                \            / \
                          ●                  ●          ●   ●

五种基本形态里，第三种和第四种是同一个"根 + 一个孩子"的结构，只因为孩子挂左边还是挂右边就算成两棵不同的二叉树。这就是二叉树与"度为 2 的有序树"的分水岭：

	二叉树	度为 2 的有序树
子树数量	每个结点至多 2 棵子树	树的度恰为 2，即必须存在度为 2 的结点
空树	允许（$n=0$）	不允许；度为 2 的树至少有 3 个结点
左右之分	严格区分：只有一个孩子时，"它是左孩子"和"它是右孩子"是两棵不同的二叉树	只有一棵子树时无左右可分，是同一棵树

判别办法就一条：拿"根 + 一个孩子"去试。 作为二叉树它有两种（左挂、右挂），作为有序树只有一种。

这个差别看着琐碎，其实是后面一条重要结论的根源：前序 + 后序不能唯一确定一棵二叉树——因为独生子的左右身份，前序和后序都表达不出来。

同样的措辞陷阱还有一对："$m$ 叉树"要求每个结点至多 $m$ 个孩子，允许所有结点的度都小于 $m$；"度为 $m$ 的树"则要求至少存在一个度恰为 $m$ 的结点。 求"最少结点数"时这个差别直接改变答案。

满二叉树与完全二叉树：差别在"允不允许度 1"

   满二叉树          完全二叉树         非完全二叉树
      1                 1                  1
     / \               / \                / \
    2   3             2   3              2   3
   / \ / \           / \ /              /     \
  4  5 6  7         4  5 6             4       7

满二叉树：高度 $h$ 且含 $2^h-1$ 个结点，每层都取到上界。等价说法是不存在度为 1 的结点——每个内部结点都有左右两个孩子。

完全二叉树：每个结点都与高度 $h$ 的满二叉树中编号 $1\sim n$ 的结点一一对应。等价说法是前 $h-1$ 层满、第 $h$ 层从左连续排列。满二叉树是它的特例。

两者最要紧的差别：完全二叉树允许有一个度为 1 的结点，满二叉树一个都没有。 当 $n$ 是偶数时，完全二叉树必然恰有一个只带左孩子的结点。把"满"的性质套到"完全"上去，是这一节最典型的错法。

定义里的"与满二叉树编号一一对应"不好直接检查，实际判定用下面任一条：

1. 层序编号法：按层序给结点编号，若编号 $1..n$ 全部有结点、无空缺，就是完全二叉树。上图第三棵中编号 5、6 空缺而 7 有结点，故不是。
2. 层序遍历法：做层序遍历，把空孩子也入队；一旦出队遇到空结点，此后不允许再出现非空结点。这是写代码判定的标准做法，见 层序遍历。
3. 形态法：前 $h-1$ 层是满的，第 $h$ 层的结点从左到右连续排列，中间不许断。

两个结构特点顺带记住：叶子只可能出现在最后两层；对任一结点，若其右分支下子孙的最大层次为 $l$，则其左分支下子孙的最大层次必为 $l$ 或 $l+1$——左边永远不比右边浅，这正是"从左到右连续"的局部表述。

另有按值组织的二叉排序树（左 $<$ 根 $<$ 右，中序递增，见 BST）与平衡二叉树（左右子树高度差 $\le 1$ 的 BST，见 AVL），它们约束的是结点的值而不是形状，与上面两种是两个维度的事。

五条性质，两条要会推

	结论	适用范围
性质 1	第 $i$ 层至多 $2^{i-1}$ 个结点	任意二叉树
性质 2	高度为 $h$ 至多 $2^h-1$ 个结点（取等即满二叉树）	任意二叉树
性质 3	$n_0=n_2+1$	任意二叉树，与是否完全、是否满无关
性质 4	完全二叉树高度 $=\lceil {\log }_2(n+1)\rceil =\lfloor {\log }_{2}n\rfloor +1$	只对完全二叉树
性质 5	层序编号 $i$：双亲 $\lfloor i/2\rfloor$、左孩子 $2i$、右孩子 $2i+1$	只对完全二叉树，一般二叉树套用必错

性质 1、2 是逐层翻倍再求和，看一眼就明白。要真正会推的是性质 3 和性质 5——前者是所有计数题的入口，后者划定了顺序存储的边界。

性质 3：$n_0=n_2+1$，靠边数双计数

同一个量（结点总数）从两个角度各数一遍，然后让两式相等。

角度一，按度分类。 二叉树中结点的度只能是 0、1、2，所以

$$\begin{array}{}\text{(1)}& n=n_0+n_1+n_2\end{array}$$

角度二，按边数。 除根之外每个结点头上恰有一条边射入，所以边数 $B=n-1$，即 $n=B+1$；而这些边都由度为 1 或 2 的结点射出，度 1 的射出 1 条、度 2 的射出 2 条，故 $B=n_1+2n_2$：

$$\begin{array}{}\text{(2)}& n=n_1+2n_2+1\end{array}$$

联立 $(1)=(2)$：$n_0+n_1+n_2=n_1+2n_2+1$，得 $n_0=n_2+1$。

关键在于 $n_1$ 在两式里都出现，联立时自动消掉——这正是结论中不含 $n_1$、因而对任意形态的二叉树都成立的原因。理解了这一点，变体就能照着做：三叉树里 $n=n_0+n_1+n_2+n_3$ 与 $n=n_1+2n_2+3n_3+1$ 联立，得 $n_0=n_2+2n_3+1$。一般地

$$n_0=1+\sum _{k\ge 2}(k-1)n_k$$

性质 5：编号关系，以及它为什么只对完全二叉树成立

设结点 $i$ 在第 $k$ 层、是该层从左数第 $j$ 个（$j=i-(2^{k-1}-1)$）。前 $k$ 层共 $2^k-1$ 个结点，第 $k+1$ 层的结点全部由第 $k$ 层按顺序生出、每个生 2 个，所以 $i$ 的左孩子是第 $k+1$ 层的第 $2j-1$ 个，编号

$$(2^k-1)+(2j-1)=2^k+2j-2=2(2^{k-1}+j-1)=2i$$

右孩子紧随其后是 $2i+1$；反推即得双亲 $\lfloor i/2\rfloor$。

推导里用到的"第 $k$ 层每个结点都生 2 个孩子、且孩子按顺序连续排列"，只有完全二叉树才满足。 一般二叉树按层序编号后，中间缺的结点会让后面的编号整体串位，$2i$ 号位置未必是 $i$ 的左孩子。顺序存储之所以必须先补空位补成完全二叉树的形状，正是为了让这条公式重新成立。

性质 1、2、4 的证明（想补全推导就展开）

性质 1（对 $i$ 归纳）：$i=1$ 时只有根结点，$2^{1-1}=1$ 成立；设第 $i-1$ 层至多 $2^{i-2}$ 个结点，二叉树每个结点的度至多为 2，故第 $i$ 层至多是它的 2 倍，即 $2^{i-1}$。

性质 2：把性质 1 逐层求和

$$\sum _{i=1}^h{2}^{i-1}=2^0+2^1+\cdots +2^{h-1}=2^h-1$$

取到等号的正是满二叉树。反过来，$n$ 个结点的二叉树高度至少为 $\lceil {\log }_2(n+1)\rceil$（由 $2^h-1\ge n$ 解出），至多为 $n$（退化成单支链）。

性质 4：设高度为 $h$。完全二叉树前 $h-1$ 层是满的、第 $h$ 层至少有 1 个结点，因此 $2^{h-1}-1<n\le 2^h-1$，即 $2^{h-1}\le n<2^h$。取对数得 $h-1\le {\log }_{2}n<h$，$h$ 是整数故 $h=\lfloor {\log }_{2}n\rfloor +1$。另一形式由 $2^{h-1}-1<n\le 2^h-1$ 加 1 得 $2^{h-1}<n+1\le 2^h$，取对数得 $h=\lceil {\log }_2(n+1)\rceil$。

两式为什么等价却写法不同：$\lceil {\log }_2(n+1)\rceil$ 在 $n$ 恰为 $2^k-1$（满二叉树）时更直观；$\lfloor {\log }_{2}n\rfloor +1$ 计算时不用先加 1，手算更快。$n=7$：$\lceil {\log }_{2}8\rceil =3$，$\lfloor {\log }_{2}7\rfloor +1=3$，一致。

完全二叉树的三条导出结论

把性质 3 与性质 5 合起来用，能挤出三条直接可用的结论。

第一，$n_1$ 只能是 0 或 1。 由性质 5，结点 $i$ 只有左孩子意味着 $2i\le n<2i+1$，即 $n=2i$——这样的 $i$ 至多一个，且要求 $n$ 为偶数。所以 $n$ 偶时 $n_1=1$，$n$ 奇时 $n_1=0$。

第二，叶子数 $n_0=\lceil n/2\rceil$。 由 $n=n_0+n_1+n_2$ 与 $n_0=n_2+1$ 得 $n=2n_0-1+n_1$，即 $n_0=\frac{n+1-n_1}{2}$；两种奇偶情形合并即 $\lceil n/2\rceil$。$n=7$ 时 $n_0=4$，$n=8$ 时也是 4。

第三，最后一个分支结点的编号是 $\lfloor n/2\rfloor$。 由性质 5，结点 $i$ 是叶子当且仅当 $2i>n$，即 $i>n/2$。编号大于 $\lfloor n/2\rfloor$ 的全是叶子——这正是建堆要从 $\lfloor n/2\rfloor$ 往前扫的原因。

一个方向性的坑：正问单值，反问双值。 由 $n$ 求 $n_0$ 答案唯一；但已知 $n_0=k$ 反求 $n$，$n=2k-1$（奇）与 $n=2k$（偶）都成立。原因是第 $2k$ 号结点作为第 $k$ 号结点的左孩子挂上去时，它自己是叶子、同时把双亲从叶子变成了分支结点，一进一出，叶子总数不变。

存储结构：顺序存储的代价藏在编号里

	顺序存储	链式存储（二叉链表）
怎么定位 / 找双亲孩子	下标即层序编号，靠性质 5 的公式，均 $O(1)$	靠指针；找孩子 $O(1)$，找双亲要从根重查 $O(h)$
适用形态 / 最坏空间	只适合完全二叉树（含满二叉树、堆）；单支树 $h$ 个结点要占 $2^h-1$ 格	任意二叉树；空间与结点数成正比
空间开销	无指针开销，编号连续时恰好装满	每结点 2 个指针，空指针恰有 $n+1$ 个

typedef struct BiTNode {
    ElemType data;                       // 数据域
    struct BiTNode *lchild, *rchild;     // 左右孩子指针
} BiTNode, *BiTree;

顺序存储用一维数组按完全二叉树的层序编号放结点：编号 $i$ 放在下标 $i$（下标 0 空着不用，好让 $2i$、$2i+1$ 直接用）。对一般二叉树必须先把它"补"成完全二叉树的形状，缺的位置填 0 或特殊标记：

一般二叉树              数组（0 表示该位置无结点）
      A                 下标  1  2  3  4  5  6  7
     / \                值    A  B  C  0  0  0  D
    B   C
         \
          D

这一补，最坏情形就出来了。 高度为 $h$ 的单支树只有 $h$ 个结点，但最深结点的编号最大可达 $2^h-1$（全走右分支时），数组必须开到 $2^h-1$ 个单元。$h=10$ 时 10 个结点要开 1023 格，利用率不到 1%；$h=20$ 时 20 个结点要开一百多万格。

所以顺序存储不省空间，它只是用"编号占位"换来"下标算父子"的便利。 这也解释了堆为什么把"必须是完全二叉树"写进定义——不是为了好看，是为了让顺序存储成立，从而免掉全部指针开销。

链式存储这边有个数字要记住：$n$ 个结点的二叉链表恰有 $n+1$ 个空指针域。 $n$ 个结点共 $2n$ 个指针域，非空指针与边一一对应共 $n-1$ 个，故空指针 $=2n-(n-1)=n+1$。把这些空域改成指向前驱／后继，就得到线索二叉树——线索树的全部动机就在这个数字上。

三叉链表与一般树的三种存储结构（想看结构定义与对照表就展开）

三叉链表在二叉链表上再加一个 parent 指针：

typedef struct TriTNode {
    ElemType data;
    struct TriTNode *lchild, *rchild, *parent;   // 多一个双亲指针
} TriTNode, *TriTree;

什么时候必须用三叉链表：需要自下而上回溯的场合。二叉链表里"找结点 $x$ 的双亲"只能从根重查（$O(h)$），三叉链表是 $O(1)$。前序线索树找前驱、后序线索树找后继在二叉链表上做不到，正是因为它们本质上要回溯到双亲。

一般树的三种存储结构（结点度不固定，不能照搬二叉链表；完整内容见 树与森林）：

存储方式	结点结构	找双亲	找孩子	适用场景
双亲表示法	data + parent（双亲下标）	$O(1)$	$O(n)$	以"找双亲"为主，如并查集
孩子表示法	每个结点的孩子用单链表串联	$O(n)$	$O(\text{度})$	以"找孩子"为主
孩子兄弟表示法	firstChild + nextSibling	不方便	第一个 $O(1)$、第 $k$ 个 $O(k)$	树 ↔ 二叉树转换

树 ↔ 二叉树的具体转换规则见 树与森林的转换。

考点速记

三条会被反复调用的结论：

1. $n_0=n_2+1$ 对任意二叉树成立，与是否完全、是否满无关；证法是边数双计数，$n_1$ 联立时自动消掉。
2. 编号关系（双亲 $\lfloor i/2\rfloor$、孩子 $2i$ 与 $2i+1$）只对完全二叉树成立，一般二叉树套用必错——顺序存储要先补空位，正是为了让它重新成立。
3. 二叉链表的空指针域恰有 $n+1$ 个（$2n$ 个域减 $n-1$ 条边），这正是线索二叉树要利用的空间。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）。这是整门里出题最密的一节，考法分四类：

① 完全二叉树的结点计数。 两道典型：给"第 6 层有 8 个叶结点"问最多结点数——做法是逐层往下算，前 5 层满（31 个），第 6 层因为下面还有第 7 层所以也满（32 个），其中 8 个是叶子、剩下 24 个各生 2 个孩子，第 7 层最多 48 个，合计 111。给"768 个结点"问叶结点数——直接套 $n_0=\lceil n/2\rceil =384$。这两道方向相反：前者从层往下推，后者用导出公式一步到位。

② 顺序存储的两问。 一问"至少要多少存储单元"：题面强调"任意一棵高度为 5 且有 10 个结点的二叉树"，就是要按最坏形态预留，答案是最大编号 $2^h-1=31$，与结点数 10 无关。一问"哪个数组不能表示二叉树"：判据是每个非空数据结点的父位置必须也非空（0 起始下标时父下标 $\lfloor (i-1)/2\rfloor$），出现"父是空、孩子非空"就非法；中间连着几个空位并不违规。

③ 中序序列里的位置关系。 两道都建立在同一条性质上：有两个孩子的结点 $v$，其中序前驱是左子树中"一路向右到底"的结点（必然没有右孩子），中序后继是右子树中"一路向左到底"的结点（必然没有左孩子）。给中序相邻的 $p,q$ 问哪种关系不可能——答案是右兄弟，因为两人分处共同双亲的左右子树，中间一定夹着双亲。给中序 $\cdots p,v,q\cdots$ 且 $v$ 有两个孩子，问 $p$、$q$ 的孩子情况——$p$ 无右孩子、$q$ 无左孩子。

④ 形态计数与判断题。 计数题考的是卡特兰数：先序序列固定时不同二叉树的形态数为 $C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})$，$n=4$ 得 14。数列前几项 1, 1, 2, 5, 14, 42 值得眼熟。判断题则把满／完全、一般／特例混着摆，逐条核对即可。另有一道问"先序与中序序列相同的条件"，答案是所有非叶结点只有右子树（只要哪个结点有左子树，两序列立刻分叉）。

易错：把满二叉树的性质套到完全二叉树上。 完全二叉树可以有度为 1 的结点——$n$ 为偶数时必然恰有一个。

易错：以为"二叉树的分支结点比叶结点少"。 那只对满二叉树成立。反例是单支链：$n$ 个结点里 1 个叶子、$n-1$ 个分支结点。

易错：顺序存储把"存储单元数"当成"结点数"。 单元数取决于最大编号，高度 $h$ 的最坏情形是 $2^h-1$；也别把它记成 $2^{h-1}$。

易错：由 $n_0$ 反求 $n$ 时只答一个。 $n=2k-1$ 与 $n=2k$ 的完全二叉树叶子数相同。

易错：路径长度与比较次数混用。 前者数边、后者数结点，差 1；WPL 用边数口径，ASL 用结点数口径。

教材出处

• 树的递归定义（"树是 $n$ 个结点的有限集，它或为空树；或为非空树，对于非空树 $T$：有且仅有一个称之为根的结点；除根结点以外的其余结点可分为 $m$ 个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树"）：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p111（5.1.1 节）
• 树的基本术语逐条定义：结点的度、树的度、叶子（终端结点）、非终端结点（分支结点、内部结点）、双亲和孩子、兄弟、祖先、子孙、堂兄弟、结点的层次：印刷 p112；树的深度（"树中结点的最大层次称为树的深度或高度"）、有序树与无序树、森林（"$m$ 棵互不相交的树的集合；对树中每个结点而言，其子树的集合即为森林"）：印刷 p113（5.1.2 节）
• 二叉树的递归定义、"二叉树与树的区别主要有两点：每个结点至多只有两棵子树；子树有左右之分，其次序不能任意颠倒"，以及二叉树的 5 种基本形态：印刷 p113（5.2 节）
• 二叉树的性质 1、2、3 及其完整证明（含"设 $B$ 为分支总数，$n=B+1$，$B=n_1+2n_2$"的双计数推导）：印刷 p118（5.4.1 节）
• 满二叉树与完全二叉树的定义、完全二叉树的两个特点、性质 4 及其证明：印刷 p119
• 性质 5（编号与双亲、左右孩子的对应关系）、二叉树的顺序存储结构，以及"深度为 $k$ 且只有 $k$ 个结点的单支树需要长度为 $2^k-1$ 的一维数组"这一空间浪费结论：印刷 p120（5.4.2 节）
• 二叉链表与三叉链表的结点结构、"含有 $n$ 个结点的二叉链表中有 $n+1$ 个空链域"及其与线索链表的衔接：印刷 p121

相关知识

前序遍历｜中序遍历｜后序遍历｜层序遍历｜构造二叉树｜线索二叉树（用掉那 $n+1$ 个空指针）｜树与森林｜森林转换｜堆｜哈夫曼树｜BST｜AVL｜红黑树

相关文章

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 由遍历序列构造二叉树
• 线索二叉树
• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 红黑树
• 哈夫曼树
• 堆（大根堆/小根堆）
• 并查集
• 树与森林
• 树与森林的转换

真题练习

相关真题（21题）

2026Q42分2025Q32分2025Q42分2024Q32分2023Q52分2022Q32分2022Q52分2020Q32分2020Q92分2019Q22分2018Q42分2017Q42分2017Q52分2015Q22分2011Q42分2011Q62分2010Q32分2010Q62分2009Q32分2009Q52分2009Q62分