数据结构与算法 · 第 6 讲：树、森林与并查集
数据结构与算法 第六讲：树、森林与并查集
来源：第六章 Tree 课件（61 页）及配套 Markdown。
1. 树与森林
非空有根树有唯一根，其余结点恰有一个父结点，且均可从根到达。森林由零棵或多棵互不相交的树组成。树可用树形图、凹入表、包含图、嵌套括号表示。
一般有序树按孩子次序区分，没有固定的左右空位置；二叉树保留左右位置。因此度不超过 2 的有序树与二叉树的定义不同。
2. 森林与二叉树的转换
左孩子指向第一个孩子，右孩子指向下一个兄弟。森林中各树的根也按右兄弟连接。单棵树转成的二叉树根的右孩子为空。
课件的操作图可以概括为：连接兄弟，保留到第一个孩子的父子边，删去其余父子边，再调整画法。逆过程将左孩子及其右兄弟链恢复为同一父结点的全部孩子。
森林的先根序对应转换后二叉树的前序，森林的后根序对应二叉树的中序。二叉树的后序一般不对应原森林的后根序。
对 A(B(E,F),C,D)：先根 ABEFCD，后根 EFBCDA，层次 ABCDEF。
3. 链式表示
| 表示 | 空间与操作 |
| 子结点表 | 每个结点保存孩子列表，便于依次访问全部孩子 |
| 静态左子右兄 | 用数组下标保存第一个孩子、下一兄弟 |
| 动态孩子数组 | 孩子序号可随机访问，插入删除可能移动元素 |
| 动态左子右兄 | 两个指针支持任意度，第 k 个孩子需沿链走 k 步 |
| 父指针数组 | 找父亲和根方便，枚举孩子需要额外结构或扫描 |
左子右兄表示的先根递归：访问根，再依次处理孩子；后根递归：先处理全部孩子，再访问根。释放一个子树时要明确兄弟是否属于该子树的所有权范围。
4. 并查集
每个集合由一棵父指针树表示，根作为代表。初始 parent[i]=i，每个集合大小为 1。 find(x) 沿父链到根；unite(a,b) 先找根，仅在根不同时合并。
按重量合并把较小集合的根挂到较大集合根下。每当一个结点深度增加，其所在集合至少翻倍，因此无路径压缩时高度至多 。按重量使用元素数，按秩使用高度上界，手算时不能互换。
路径压缩在查询时把路径上的结点直接接到根；没有经过的结点保持原父指针。按重量加路径压缩，初始化后 次操作的总时间为 ，另计初始化 。
课件规定同重量时较大编号根挂到较小编号根。依次合并 (0,1),(1,2),(3,4)，父数组由 [0,1,2,3,4] 变为 [0,0,0,3,3]。
动态连通分量初始为 ，每次成功合并减 1。大小为 的不同分量合并新增 对连通无序点对；重复边不改变计数。规模读取合并前两个根保存的值。
5. 顺序编码与还原
带右链先根序：每项保存是否为叶及下一兄弟下标；有孩子时第一个孩子恰在下一项。
双标记先根序：ltag=0 表示有孩子，rtag=0 表示有下一兄弟，1 表示不存在。扫描时用栈保存有待连接兄弟的位置；走到叶后回退，接到最近尚未完成的兄弟位置。
带度数后根序：每项保存孩子数，读到一个结点时从栈中取它的各棵子树，按原次序挂接，再将新子树压栈。弹栈顺序与孩子的左右次序相反。
双标记层次序：用队列记录待处理父结点，按有无孩子和兄弟标记恢复每一组孩子。两位逻辑标记只有在位压缩存储中才实际占两位。
6. K 叉树
每个结点固定有 K 个有序孩子位置，可用 K 个指针或按层存放。0 起始的完全 K 叉树中，结点 的孩子下标为 至 ，非根父下标为 。
深度 层至多 个结点；高度 的最多结点数为 ，这里 。任意孩子数的树转左子右兄后，二叉树的深度可能明显增加。