返回：0300 数据结构总目录 · 上一章：0304 Chap4 栈与队列 · 下一章：0306 Chap6 图

1、学习目标

树把线性结构扩展成层次结构。二叉树是后续搜索树、堆、Huffman 编码和表达式树的基础。本章要抓住两条线：一是树的结构表示，二是遍历如何把递归结构转成线性序列。

模块 要掌握的内容
树基础 根、父子、兄弟、祖先、深度、高度、度
表示 父亲表示法、孩子表示法、长子兄弟表示法
二叉树 真二叉树、节点类、树类、高度维护
遍历 先序、中序、后序、层次遍历
重构 由遍历序列恢复二叉树
应用 PFC、Huffman 编码

2、资料范围

PDF 课件 内容
05.Binary_Tree.A.Tree.pdf 树的概念
05.Binary_Tree.B.Representation.pdf 树的表示
05.Binary_Tree.C.Binary_Tree.pdf 二叉树
05.Binary_Tree.D.Implementation.pdf BinNode、BinTree 实现
05.Binary_Tree.E1-E5 先序、中序、后序、层次遍历和重构
05.Binary_Tree.F.PFC.pdf 前缀无歧义编码
05.Binary_Tree.G.Huffman.pdf Huffman 树

3、树的基本概念

概念 说明
根 没有父节点的节点
叶子 没有孩子的节点
深度 从根到该节点的边数
高度 从该节点到最深叶子的边数
度 节点孩子数量
子树 某节点及其后代形成的树

二叉树中，每个节点最多有两个孩子，分别称为左孩子和右孩子。

真二叉树是每个内部节点都有两个孩子的二叉树。很多编码树和表达式树常被扩充成真二叉树，便于统一处理。

4、树的表示

表示法 思路 特点
父亲表示法 每个节点记录父节点位置 找父亲快，找孩子慢
孩子表示法 每个节点维护孩子列表 找孩子快，空间和实现较复杂
长子兄弟表示法 每个节点只记录第一个孩子和下一个兄弟 任意树可转二叉树

长子兄弟表示法非常重要：

1
2
firstChild  表示左孩子
nextSibling 表示右孩子

它把多叉树统一转化为二叉树，为树结构的通用实现提供入口。

5、二叉树节点

典型节点字段：

1
2
3
4
5
6
7
8
template <typename T>
struct BinNode {
    T data;
    BinNode<T>* parent;
    BinNode<T>* lc;
    BinNode<T>* rc;
    int height;
};

高度更新：

1
2
3
4
5
6
7
int stature(BinNode<T>* x) {
    return x ? x->height : -1;
}

void updateHeight(BinNode<T>* x) {
    x->height = 1 + max(stature(x->lc), stature(x->rc));
}

插入节点后，要从插入位置向祖先逐层更新高度。

6、遍历

6.1 先序遍历

顺序：根、左、右。

1
2
3
4
5
6
void preorder(Node* x) {
    if (!x) return;
    visit(x);
    preorder(x->left);
    preorder(x->right);
}

迭代版本可用栈，先压右孩子再压左孩子。

6.2 中序遍历

顺序：左、根、右。

1
2
3
4
5
6
void inorder(Node* x) {
    if (!x) return;
    inorder(x->left);
    visit(x);
    inorder(x->right);
}

中序遍历对 BST 极其重要：BST 的中序序列是非降序列。

6.3 后序遍历

顺序：左、右、根。后序适合释放树、计算子树信息。

1
2
3
4
5
6
void postorder(Node* x) {
    if (!x) return;
    postorder(x->left);
    postorder(x->right);
    visit(x);
}

6.4 层次遍历

层次遍历用队列：

1
2
3
4
5
6
7
8
queue<Node*> q;
q.push(root);
while (!q.empty()) {
    Node* x = q.front(); q.pop();
    visit(x);
    if (x->left) q.push(x->left);
    if (x->right) q.push(x->right);
}

7、遍历序列重构

常见结论：

已知序列 能否唯一重构
先序 + 中序 能
后序 + 中序 能
先序 + 后序 通常不能，除非有额外条件
层序 + 中序 能

先序 + 中序重构思路：

  1. 先序第一个元素是根。
  2. 在中序中找到根，左边是左子树，右边是右子树。
  3. 根据左右子树规模切分先序序列。
  4. 递归构造左右子树。

8、PFC 与 Huffman 编码

PFC 是前缀无歧义编码：任意字符编码都不是另一个字符编码的前缀。这样解码时从左往右读，不会产生歧义。

Huffman 编码构造：

1
每次选权重最小的两棵树合并，新树权重为二者之和，直到只剩一棵树。

优点：

  1. 高频字符路径短。
  2. 低频字符路径长。
  3. 在给定频率下得到最优前缀编码。

可用优先级队列实现，每次取出两个最小权重节点，复杂度 O(n log n)。

9、复杂度汇总

操作 复杂度
遍历整棵树 O(n)
查找某节点高度 若已维护字段 O(1)
插入后更新高度 O(h)
Huffman 建树 O(n log n)

10、易错点

易错点 修正
混淆深度和高度 深度从根往下，高度从节点往叶子
中序遍历能单独重构树 不能，必须配合其他序列
后序只会递归写法 后序迭代需要更细地维护访问状态
忘记更新祖先高度 插入、删除和旋转后都要维护高度
Huffman 只按字符排序 关键是频率或权重，不是字符值

11、复盘清单

检查项 状态
能解释长子兄弟表示法 待复盘
能写出四种遍历框架 待复盘
能用先序和中序重构二叉树 待复盘
能说明 BST 中序有序的原因 待复盘
能手动构造 Huffman 树 待复盘