Chapter 06 树

1. 树的定义¶

树是包括n个结点的有限集合 T（n≥1），使得：

一个根结点
除根以外的其它结点被分成m个(m≥0)不相交的集合T1，T2，…，Tm，而且这些集合的每一个又都是树。树T1，T2，…，Tm称作这个根的子树

四种表示法:

1.1 有序树¶

把树结点的子结点按从左到右的次序编号.

Warning

度小于等于 2 的有序树并不一定是二叉树

这是因为树的孩子不区分左右, 当第 1 子节点被删除后, 第 2 子节点自动称为第 1 子节点. 但是二叉树中删除左子树后右子树不能替代左子树.

只有严格区分左右两个子节点的有序树才是二叉树.

1.2 森林¶

零棵或多棵不相交的树的集合.

2. 森林与二叉树的等价转换¶

2.1 森林->二叉树¶

转换过程:
- 兄弟之间加线 (森林之间的根也加线)
- 从第二个子结点开始断开与父结点的边
- 适当旋转为二叉树

2.2 二叉树->森林¶

转换过程即为森林->二叉树的逆过程.

加线: 若p结点是父结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来
删线: 删除所有结点和右孩子的连线.
适当旋转.

Tips

对于森林, 可以看作增加一个虚点, 虚点向森林中每一棵树的根连线.

3. 树的周游¶

3.1 先根次序¶

若树非空，则遍历方法为：
- 访问根结点
- 从左到右，依次先根遍历根结点的每一棵子树

3.2 后根次序¶

若树非空，则遍历方法为：
- 从左到右，依次后根遍历根结点的每一棵子树
- 访问根结点

3.3 周游性质¶

按先根次序周游树正好等于对应二叉树的前序周游

按后根次序周游树正好等于对应二叉树的中序周游

4. 树的链式存储¶

4.1 子结点表示法¶

4.2 动态结点表示法¶

4.3 左孩子右兄弟法¶

本质上，是使用二叉树来替换树

优点: 每个结点所需空间一致.

4.4 父指针表示法¶

5. 树的顺序存储¶

5.1 带右链的先根次序表示法¶

核心观察:
- 先序遍历中, 子树的所有结点连续排列.
- 如果一个结点有子节点, 先序遍历中该结点的后一个结点一定是它的第一个子结点.

因此, 可以使用一个 ltag 标记是否有子节点. 0 表示有子节点, 1 表示无子节点 (这一点非常反常), 且先序遍历中下一个结点就是第一个子结点. 再用 rlink 指向该结点的下一个兄弟, 这样就实现了左孩子右兄弟表示法. 用 0/1 代替 llink 节省了空间.

5.2 带双标记位的先根次序表示法¶

事实上, 带右链的先根次序表示法中的 rlink 也不是必须的.

我们使用 rtag 标记. rtag 为 1 表示无兄弟, rtag 为 0 表示有兄弟 (这一点非常反常)

当一个结点x的rtag为1时，它的rlink显然应为空
当一个结点x的rtag为0时，它的rlink应指向结点序列中排在以结点x为根的子树中最后结点的后面的那个结点y

有兄弟的结点(rtag=0)，都唯一对应一个无孩子的结点(ltag=1)，成对出现，满足栈特性，即

扫描到一个rtag为0的结点就将它进栈
扫描到一个ltag为1的结点就从栈顶弹出一个结点，并为其设置rlink，下一个要读出的节点即为其兄弟节点

5.3 带度数的后根次序表示法¶

5.4 带双标记的层次次序表示¶

顺序扫描带双标记的层次次序序列

如果结点的ltag值为1，则置其llink为空；当结点的ltag为0时，该结点入队列；
如果结点的rtag值为0，那么其后的结点y就是其右兄弟；
否则，如果结点的rtag值为1，则rlink为空，此时出队列x，并将x的llink指向序列中后续结点 y即可。