【408考研·数据结构专题】二叉树、树与森林、线索树及哈夫曼树核心考点与秒杀技巧深度总结

文章目录一、 二叉树的基本概念与形态推导1. 二叉树的核心操作逻辑2. 卡特兰数Catalan与二叉树形态推导二、 经典例题复盘完全二叉树结点最值问题 【例题】 【解析与推导过程】三、 二叉树的遍历方法与还原技巧1. 三大基础遍历逻辑2. 实例深度分析3. 双序列恢复二叉树四、 线索二叉树Threaded Binary Tree1. 线索二叉树的底层本质2. 线索化核心规则3. 各种遍历下的线索流向趋势五、 树与森林的存储结构1. 双亲表示法2. 孩子表示法3. 孩子兄弟表示法二叉链表表示法六、 树、森林与二叉树的转换及遍历对应1. 转换规则2. 树与森林的遍历序列示例对应上述存储结构树3. 核心对应关系表重中之重七、 哈夫曼树Huffman Tree1. 核心定义2. 基础概念拆解一、 二叉树的基本概念与形态推导1. 二叉树的核心操作逻辑基本操作查找结点、删除二叉树结点、输出高度、统计结点数。核心方法总结左→ \rightarrow→右→ \rightarrow→根后序思维。在树的性质及操作中凡是涉及左右子树的部分一般都要用到递归。2. 卡特兰数Catalan与二叉树形态推导对于长度为n nn的入栈序列其可能产生的出栈序列数量与n nn个结点所能构成的二叉树形态数量完全一致出栈序列数量 二叉树的形态数量 C 2 n n n 1 ( 2 n ) ! n ! ( n 1 ) ! \text{出栈序列数量} \text{二叉树的形态数量} \frac{C_{2n}^n}{n1} \frac{(2n)!}{n!(n1)!}出栈序列数量二叉树的形态数量n1C2nn​​n!(n1)!(2n)!​二、 经典例题复盘完全二叉树结点最值问题 【例题】完全二叉树第 5 层有 9 个叶子结点则该树最多有 _____ 个结点。 【解析与推导过程】已知得在满二叉树状态下第 5 层原本应该有2 5 − 1 16 2^{5-1} 1625−116个结点。现在题干指出第 5 层有9 个是叶子结点这意味着这 9 个结点已被确认在下一层无子结点。因此第 5 层还剩下16 − 9 7 16 - 9 716−97个非叶子结点可以向下延伸长出子女。为了让整棵树的结点数最多这 7 个非叶子结点在第 6 层必须全部长满即在第 6 层最多拥有7 × 2 14 7 \times 2 147×214个结点。总结点数计算前 4 层满结点数 第 5 层结点数 第 6 层最大结点数最多结点数 7 × 2 16 8 4 2 1 14 24 7 45 \text{最多结点数} 7 \times 2 16 8 4 2 1 14 24 7 45最多结点数7×21684211424745答案45三、 二叉树的遍历方法与还原技巧1. 三大基础遍历逻辑先序遍历根→ \rightarrow→左→ \rightarrow→右中序遍历左→ \rightarrow→根→ \rightarrow→右后序遍历左→ \rightarrow→右→ \rightarrow→根核心方法总结遍历的遍历顺序可以理解为根的遍历顺序不同先序—— 根先中序—— 根中后序—— 根后注无论哪种遍历左子树永远在右子树前面访问。2. 实例深度分析针对经典二叉树拓扑结构其遍历序列具体表现如下先序序列1 → 2 → 4 → 7 → 5 → 8 → 3 → 6 → 9 → 10 1 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 5 \rightarrow 8 \rightarrow 3 \rightarrow 6 \rightarrow 9 \rightarrow 101→2→4→7→5→8→3→6→9→10特性观察易见先序序列是图中的多个连续段。中序序列7 → 4 → 2 → 5 → 8 → 1 → 3 → 9 → 6 → 10 7 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 8 \rightarrow 1 \rightarrow 3 \rightarrow 9 \rightarrow 6 \rightarrow 107→4→2→5→8→1→3→9→6→10特性观察易见中序序列到是三合一的一个模块例如末尾的9, 6, 10构成小局部模块。后序序列7 → 4 → 8 → 5 → 2 → 9 → 10 → 6 → 3 → 1 7 \rightarrow 4 \rightarrow 8 \rightarrow 5 \rightarrow 2 \rightarrow 9 \rightarrow 10 \rightarrow 6 \rightarrow 3 \rightarrow 17→4→8→5→2→9→10→6→3→1秒杀技巧中序投影法中序序列可用投影法速成以左、根、右的相对几何位置向下作垂直投影即可直接读出中序遍历结果。3. 双序列恢复二叉树可唯一确定二叉树的组合【先序 中序】、【后序 中序】、【层次 中序】。核心方法总结以中序序列为划分基准用于切分左右子树另一序列先序/后序/层次为实际结点的层次或确定当前的根节点。四、 线索二叉树Threaded Binary Tree1. 线索二叉树的底层本质n nn个结点的二叉树其二叉链表中必然含有n 1 n1n1个空指针域。利用这些空指针域存放指向前驱和后继的指针即为“线索”。主要应用① 找第一个和最后一个结点② 找前驱③ 找后继。2. 线索化核心规则核心方法总结若无左子树lchild指向前驱若无右子树rchild指向后继。所以只需要考虑叶子结点及缺少单侧子树的结点。3. 各种遍历下的线索流向趋势先序方向a - b - c - d - e中序方向b - a - d - c - e后序方向b - d - e - c - a五、 树与森林的存储结构1. 双亲表示法实现方式采用连续的数组存储每个结点包含数据域与双亲结点的数组下标。特点易找双亲结点不易删除结点。【示例键值表】数组下标 (index)数据域 (data)双亲下标 (parent)0A-1 根节点1B02C03D14E32. 孩子表示法实现方式数组与单链表结合。数组存放各结点链表存放该结点的所有孩子。【示例链表结构】0 [A]→ 1 → 2 → NULL \rightarrow 1 \rightarrow 2 \rightarrow \text{NULL}→1→2→NULL1 [B]→ 3 → NULL \rightarrow 3 \rightarrow \text{NULL}→3→NULL2 [C]→ NULL \rightarrow \text{NULL}→NULL3 [D]→ 4 → NULL \rightarrow 4 \rightarrow \text{NULL}→4→NULL4 [E]→ NULL \rightarrow \text{NULL}→NULL3. 孩子兄弟表示法二叉链表表示法核心方法总结记住指针分配口诀左指孩子右指兄弟。六、 树、森林与二叉树的转换及遍历对应1. 转换规则树⇒ \Rightarrow⇒二叉树左指孩子右指兄弟。森林⇒ \Rightarrow⇒二叉树左指孩子右指兄弟。各棵树的根结点从左往右依次连接。2. 树与森林的遍历序列示例对应上述存储结构树树的先根遍历A B D E C树的后根遍历E D B C A3. 核心对应关系表重中之重二叉树树森林先序遍历先根遍历先序遍历中序遍历后根遍历后序遍历七、 哈夫曼树Huffman Tree1. 核心定义哈夫曼树是指带权路径长度WPL最小的二叉树。2. 基础概念拆解权Weight给结点赋予的具有某种特定实际意义的数值。路径长度该结点到根结点的跳数。带权路径长度WPL所有叶子结点到根结点的带权跳数即叶子结点的权值× \times×路径长度之和。