数据结构与算法 · 第 5 讲：二叉树、堆与 Huffman 编码
数据结构与算法 第五讲：二叉树、堆与 Huffman
来源：第五章 Binary Tree 课件（69 页）及配套 Markdown。
1. 二叉树的定义与计数
二叉树为空，或由根与互不相交的左右子树组成。左、右位置固定，因此单独左孩子与单独右孩子是不同形态。 本讲根的深度为 0；高度按层数计，空树高度为 0，单结点高度为 1。
课件的 full（满） 指每个非叶结点都有两个孩子；perfect 指每层全满；complete（完全） 指最后一层前全满，最后一层从左向右连续。full 与 complete 互不包含，perfect 同时满足二者。
第 层至多 个结点，高度 的二叉树至多 个结点。非空完全二叉树高度为 。
令度为 0、1、2 的结点数分别为 。由结点总数与边数
得到 。二叉链表有 个孩子指针，其中 个非空，故有 个空指针。
扩充二叉树把每个空子树替换为外部叶。若原树有 个结点，内部路径长度为 ，外部路径长度为 ，则 。由向空位置加入一个内部结点的归纳可证：深度 的外部叶换成内部结点和两个深度 的外部叶， 增加 ， 增加 。
2. 四种遍历
前序：根左右；中序：左根右；后序：左右根；层次：队列逐层访问。 对 A(B(D,E),C)，分别得到 ABDEC、DBEAC、DEBCA、ABCDE。
深度优先访问每个结点一次，时间 ，辅助栈 。层次遍历每个结点入出队一次，时间 ，队列空间 ， 为最大层宽。
前序迭代先压右后压左；中序迭代沿左链压栈，弹出访问后转右；后序可用访问状态标记模拟递归。递归的空子树处理是算法的终止条件。
表达式树内部结点为运算符，叶为操作数；前序对应前缀，后序对应后缀。中序直接输出会丢括号，需要按树形或优先级恢复括号。
3. 由序列重建
关键码互异时，前序加中序或后序加中序唯一确定二叉树。先从前序首端或后序末端取根，在中序定位，以左右区间大小切分另一序列，再递归。
只用前序加后序一般不唯一：AB 与 BA 无法区分 B 是左孩子还是右孩子。实现传递下标区间，避免每层复制子数组。中序位置用散列表可使期望时间 ；排序索引加二分为 。
4. 存储、释放与拷贝
二叉链表保存左右孩子，三叉链表再保存父指针。完全二叉树按层从 0 编号，左右孩子为 ，父结点为 。稀疏树的顺序存储可能浪费大量空位。
释放结点用后序：先处理左右子树，再释放根。拷贝须递归建立独立结点；只复制根指针会共享所有权。树高决定递归深度，显式栈可保存待处理子树。
5. 二叉搜索树 BST
每个结点左子树所有键更小，右子树所有键更大，本课实现不存重复键。中序遍历得到升序序列。 查找、插入和删除沿根到结点的路径进行，均为 ；升序插入可能退化为高度 的链。
删除叶子直接摘除；只有一个孩子则由该孩子顶替；有两个孩子则用左子树最大结点（中序前驱）或右子树最小结点（中序后继）顶替。摘前驱时须接回它可能存在的左孩子，然后再接被删结点的两棵子树。
检查 BST 需要维护整棵子树的上下界，或验证中序序列严格递增；只比较父结点与直接孩子不够。
6. 堆与优先队列
最小堆是完全二叉树，且每个父结点不大于孩子。堆序只约束祖先与后代，不保证兄弟大小，也不支持普通二分查找。
插入：放数组末尾，再上浮；删除最小值：移末元素到根，长度减一，再与较小孩子比较下沉。查询堆顶 ，插入与删顶 。
建堆从最后一个非叶结点 开始向前下沉。高度为 的结点约有 个，因此
逐个插入建堆最坏 。
对顶堆维护中位数：小的一半放最大堆，大的一半放最小堆；保证前者元素不大于后者，且前者大小等于后者或多 1。前者堆顶是下中位数，插入 ，查询 。
7. Huffman 树与编码
带权路径长度为 。每次取两棵最小权树合并，新根权为两者之和，重复 次。使用最小堆，时间 。
最优性的交换论证：把最小的两个权放到最深的一对兄弟叶上不会增加 WPL；合并后形成规模减少 1 的同类问题。归纳得到贪心最优。
WPL 也等于全部合并代价之和：每个叶权在它的每个内部祖先处计算一次。权 2、3、4、7：合并得到 5、9、16，所以 WPL 为 。
左边标 0、右边标 1，根到叶的串为码字。字符只在叶上，因此没有码字是另一编码的前缀。译码逐位沿树走，到叶输出字符再回根。单字符字母表可约定编码为 0。
若权值按数量成批给出，最小权 有 棵，可先合成 棵权 的树，累加同量合并代价；奇数时保留一棵 与下一最小项合并。
8. 例题
先序 ABCDEFG，中序 CBDAFEG：根为 A，左子树根 B、孩子 C 与 D；右子树根 E、孩子 F 与 G。后序为 CDBFGEA。
权 2、3、4、7、8：合并 5、9、15、24，WPL 为 53。一组码为：2→100，3→101，4→00，7→11，8→01；逐项计算也得到 53。