软考软件设计师/系统架构设计师必考：树与二叉树（性质、遍历、线索、哈夫曼、二叉排序树、平衡二叉树）最全详解

目标：一文彻底掌握软考上午题中“树与二叉树”所有高频考点。包含树的基本概念、二叉树性质、四种遍历（递归/非递归）、线索二叉树、哈夫曼树与编码、二叉排序树、平衡二叉树（AVL）的旋转与判断。配大量例题与解题技巧，看完这篇，无需再翻其他资料。

一、树的基本概念

1. 树的定义

树是n（n≥0）个节点的有限集合。n=0时称为空树。非空树满足：

• 有且仅有一个根节点。
• 其余节点可分为m个互不相交的子树。

2. 基本术语

3. 树的存储结构

• 双亲表示法：每个节点存双亲下标，找双亲快，找孩子慢。
• 孩子表示法：每个节点存孩子链表，找孩子快，找双亲慢。
• 孩子兄弟表示法：左指针指向第一个孩子，右指针指向下一个兄弟，可将树转为二叉树。

软考常考：节点数与度的关系。对于树，节点数 = 所有节点度之和 + 1。

例题1：一棵树有5个度为2的节点，3个度为1的节点，求叶子节点数。
解析：

• 设叶子节点数为n0，总节点数 = n0 + 5 + 3 = n0 + 8。
• 总度数 = 5×2 + 3×1 = 13。
• 节点数 = 总度数 + 1 = 14。
• 所以 n0 + 8 = 14，n0 = 6。
  答案：6个叶子节点。

二、二叉树

1. 二叉树的定义

二叉树是n个节点的有限集合，每个节点最多有两棵子树（左子树和右子树），且左右子树有顺序。

2. 二叉树的五种基本形态

3. 特殊二叉树

• 满二叉树：每一层节点数都达到最大，深度为k时有2^k – 1个节点。
• 完全二叉树：只有最后一层可能不满，且节点集中在左边。深度为k时节点数在2^(k-1)到2k – 1之间。
• 二叉排序树（BST）：左子树所有节点 < 根 < 右子树所有节点。
• 平衡二叉树（AVL）：任意节点左右子树高度差不超过1。

4. 二叉树的重要性质（软考高频）

例题2：一棵二叉树有10个度为2的节点，5个度为1的节点，求叶子节点数。
解析：n0 = n2 + 1 = 10 + 1 = 11。

例题3：完全二叉树有100个节点，求叶子节点数。
解析：

• n=100，n2 = ⌊n/2⌋ = 50？更准确：n0 = n2 + 1，n = n0 + n1 + n2。
• 完全二叉树中，n1只能为0或1。n=100为偶数，所以n1=1。
• n0 + 1 + n2 = 100，且n0 = n2 + 1。
• 解得 n2 = 49，n0 = 50。
  答案：50个叶子节点。

5. 二叉树的存储结构

• 顺序存储：用数组存储，适合完全二叉树。节点i的左孩子2i，右孩子2i+1。
• 链式存储：二叉链表，每个节点有data、lchild、rchild。

typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

三、二叉树的遍历

1. 四种遍历方式

2. 递归遍历代码（以先序为例）

void PreOrder(BiTree T) {
if (T != NULL) {
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}

中序、后序只需调整visit位置。

3. 非递归遍历（重点）

先序非递归

void PreOrderNonRec(BiTree T) {
Stack S; InitStack(S);
BiTree p = T;
while (p || !IsEmpty(S)) {
if (p) {
visit(p);
Push(S, p);
p = p->lchild;
} else {
Pop(S, p);
p = p->rchild;
}
}
}

中序非递归

void InOrderNonRec(BiTree T) {
Stack S; InitStack(S);
BiTree p = T;
while (p || !IsEmpty(S)) {
if (p) {
Push(S, p);
p = p->lchild;
} else {
Pop(S, p);
visit(p);
p = p->rchild;
}
}
}

后序非递归

需记录最近访问的节点，判断是从左子树返回还是右子树返回。

void PostOrderNonRec(BiTree T) {
Stack S; InitStack(S);
BiTree p = T, r = NULL;
while (p || !IsEmpty(S)) {
if (p) {
Push(S, p);
p = p->lchild;
} else {
GetTop(S, p);
if (p->rchild && p->rchild != r) {
p = p->rchild;
} else {
Pop(S, p);
visit(p);
r = p;
p = NULL;
}
}
}
}

4. 由遍历序列确定二叉树

• 先序 + 中序：可唯一确定。
• 后序 + 中序：可唯一确定。
• 层次 + 中序：可唯一确定。
• 先序 + 后序：不能唯一确定。

方法：先序的第一个是根，后序的最后一个是根，在中序中找到根，左边是左子树，右边是右子树，递归。

例题4：已知先序序列为 ABDECFG，中序序列为 DBEAFCG，求后序序列。
解析：

• 先序第一个A是根，中序中A左边DBE是左子树，右边FCG是右子树。
• 左子树先序BDE，中序DBE → 根B，左D，右E。
• 右子树先序CFG，中序FCG → 根C，左F，右G。
• 后序：左子树后序DEB，右子树后序FGC，根A → DEBFGCA。

5. 层次遍历

用队列实现：

void LevelOrder(BiTree T) {
Queue Q; InitQueue(Q);
if (T) EnQueue(Q, T);
while (!IsEmpty(Q)) {
DeQueue(Q, p);
visit(p);
if (p->lchild) EnQueue(Q, p->lchild);
if (p->rchild) EnQueue(Q, p->rchild);
}
}

软考常考：遍历序列的相互推导、非递归代码填空、层次遍历应用。

四、线索二叉树

1. 为什么需要线索二叉树

普通二叉树中，n个节点有n+1个空指针域，浪费空间。线索二叉树利用这些空指针指向节点的前驱或后继，加速遍历。

2. 线索化规则

• 若节点有左孩子，lchild指向左孩子；否则lchild指向前驱。
• 若节点有右孩子，rchild指向右孩子；否则rchild指向后继。
• 增加两个标志位ltag、rtag：0表示指向孩子，1表示指向前驱/后继。

3. 三种线索二叉树

• 先序线索二叉树
• 中序线索二叉树（最常用）
• 后序线索二叉树

4. 中序线索二叉树的遍历

// 找中序第一个节点
BiTree FirstNode(BiTree p) {
while (p->ltag == 0) p = p->lchild;
return p;
}
// 找中序后继
BiTree NextNode(BiTree p) {
if (p->rtag == 0) return FirstNode(p->rchild);
else return p->rchild;
}

软考常考：线索二叉树的定义、标志位含义、中序线索化后找前驱/后继。

例题5：中序线索二叉树中，节点p有右孩子，则其中序后继是（ ）。
A. p的右孩子
B. p的右子树中最左下的节点
C. p的右子树中最右下的节点
D. p的双亲
答案：B
解析：有右孩子时，中序后继为右子树中最左下的节点。

五、哈夫曼树与哈夫曼编码

1. 哈夫曼树的定义

给定n个权值，构造一棵带权路径长度（WPL）最小的二叉树，称为哈夫曼树（最优二叉树）。

带权路径长度 WPL = Σ(叶子权值 × 叶子到根的路径长度)

2. 构造方法

3. 哈夫曼编码

• 左分支标0，右分支标1。
• 从根到叶子的路径上的0/1序列即为该字符的编码。
• 哈夫曼编码是前缀编码，任一编码不是其他编码的前缀，不会产生歧义。
• 权值越大的字符编码越短，实现压缩。

例题6：给定权值 {5, 7, 2, 3, 9}，构造哈夫曼树并求WPL。
解析：

• 排序：2,3,5,7,9
• 合并2+3=5，森林：5,5,7,9
• 合并5+5=10，森林：7,9,10
• 合并7+9=16，森林：10,16
• 合并10+16=26
• 树结构：根26，左10，右16；10的左5，右5；5的左2，右3；16的左7，右9。
• WPL = 2×3 + 3×3 + 5×2 + 7×2 + 9×2 = 6+9+10+14+18 = 57。

例题7：哈夫曼编码属于（ ）。
A. 定长编码 B. 前缀编码 C. 循环编码 D. 校验编码
答案：B
解析：哈夫曼编码是前缀编码，任一编码不是其他编码的前缀。

软考常考：构造哈夫曼树、计算WPL、判断哈夫曼编码、求字符编码。

六、二叉排序树（BST）

1. 定义

二叉排序树（二叉查找树）满足：

• 若左子树非空，左子树所有节点值 < 根节点值。
• 若右子树非空，右子树所有节点值 > 根节点值。
• 左右子树也分别是二叉排序树。

2. 查找

从根开始，小于根往左，大于根往右，等于则找到。

3. 插入

按查找路径找到空位置插入，保持BST性质。

4. 删除

• 叶子节点：直接删除。
• 只有一个孩子：用孩子替代。
• 有两个孩子：用中序前驱（左子树最右）或中序后继（右子树最左）替代，然后删除替代节点。

5. 查找效率

• 最好情况：平衡时，O(log n)。
• 最坏情况：退化为单链表，O(n)。

例题8：依次插入 {45, 24, 53, 12, 37, 93} 构造BST，求查找37的比较次数。
解析：

• 45为根，24<45左，53>45右，12<24左，37>24右且<45，93>53右。
• 查找37：45→24→37，比较3次。

软考常考：BST的构造、查找、删除、判断是否为BST、平均查找长度。

七、平衡二叉树（AVL）

1. 定义

平衡二叉树（AVL树）是二叉排序树，且任意节点左右子树高度差（平衡因子）绝对值不超过1。

平衡因子 BF = 左子树高度 – 右子树高度，取值 -1, 0, 1。

2. 失衡与旋转

插入或删除导致BF绝对值超过1时，需旋转调整。

3. 旋转示例

LL型右旋：

A B
/ / \\
B → C A
/
C

RR型左旋：

A B
\\ / \\
B → A C
\\
C

LR型：

A A C
/ / / \\
B → C → B A
\\ /
C B

RL型：

A A C
\\ \\ / \\
B → C → A B
/ \\
C B

4. AVL树的高度

含n个节点的AVL树最大高度约为 1.44 log₂(n+2)。

例题9：依次插入 {16, 3, 7} 构造AVL树，画出旋转过程。
解析：

• 插入16，根。
• 插入3，16的左孩子。
• 插入7，3的右孩子，此时16的BF=2，属于LR型。
• 先对3左旋：3的右孩子7变成3的双亲，3变成7的左孩子。
• 再对16右旋：7变成根，16变成7的右孩子，3保持为7的左孩子。
• 最终：根7，左3，右16。

软考常考：判断是否AVL、插入后旋转类型、AVL树高度、平衡因子计算。

八、软考常见题型与技巧

题型一：二叉树性质计算

例题10：一棵完全二叉树有767个节点，求叶子节点数。
解析：

• n=767为奇数，n1=0。
• n0 = n2 + 1，n = n0 + n2 = 2n2 + 1 = 767 → n2 = 383，n0 = 384。
  答案：384个叶子节点。

题型二：遍历序列推导

例题11：已知后序序列为 DEBFGCA，中序序列为 DBEAFCG，求先序序列。
解析：

• 后序最后A是根，中序A左DBE，右FCG。
• 左子树后序DEB，中序DBE → 根B，左D，右E。
• 右子树后序FGC，中序FCG → 根C，左F，右G。
• 先序：A B D E C F G。

题型三：哈夫曼树WPL

例题12：权值 {1, 2, 3, 4, 5}，构造哈夫曼树，求WPL。
解析：

• 合并1+2=3，森林：3,3,4,5
• 合并3+3=6，森林：4,5,6
• 合并4+5=9，森林：6,9
• 合并6+9=15
• WPL = 1×3 + 2×3 + 3×2 + 4×2 + 5×2 = 3+6+6+8+10 = 33。

题型四：BST与AVL

例题13：下列序列中，能构成二叉排序树查找路径的是（ ）。
A. 45, 24, 53, 12, 37
B. 45, 24, 53, 12, 60
C. 45, 24, 53, 12, 37, 93
D. 以上都是
答案：D
解析：都满足BST查找路径（左小右大）。

例题14：AVL树中，节点A的平衡因子为2，其左孩子B的平衡因子为-1，则需要进行（ ）旋转。
A. LL B. RR C. LR D. RL
答案：C
解析：A左子树高，B右子树高，属于LR型，先左旋后右旋。

九、易错点与注意事项

十、总结与速记

速记1：二叉树性质

• 第i层最多2^(i-1)
• 深度k最多2^k – 1
• n0 = n2 + 1
• 完全二叉树深度 ⌊log₂n⌋ + 1

速记2：遍历

• 先序：根左右
• 中序：左根右
• 后序：左右根
• 层次：队列，逐层

速记3：线索二叉树

• 空左指针指前驱，空右指针指后继
• ltag=1前驱，rtag=1后继

速记4：哈夫曼树

• 每次合并最小两个权值
• WPL = Σ(权值 × 路径长度)
• 编码是前缀编码

速记5：BST与AVL

• BST：左<根<右
• AVL：平衡因子∈{-1,0,1}
• 旋转：LL右旋，RR左旋，LR先左后右，RL先右后左

掌握以上内容，配合历年真题练习，树与二叉树部分即可轻松得分。建议重点练习遍历序列推导、哈夫曼树WPL计算、BST构造和AVL旋转判断。

下期预告：数据结构与算法（下）——图（存储、遍历、最小生成树、最短路径、拓扑排序），敬请关注。

发布日期：2026-09-16