【数据结构】4. 树与二叉树(6)

该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但是求结点的孩子时却需要遍历整个结构。

1. 孩子表示法
   孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，则 N 个结点就
   有 N 个孩子链表（叶子结点的孩子链表为空表），如图 4-14(a) 所示。
   对于这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历 N 个结点中孩子链表指针域所指向的 N 个孩子链表。
   3.孩子兄弟表示法
   孩子兄弟表示法又称为二叉树表示法，即以二叉链表作为树的存储结构。
   孩子兄弟表示法是使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针和指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点），如图 4-14(b) 所示。
   

   

孩子兄弟表示法的存储结构描述如下：

typedef struct CSNode {
    ElemType data; //数据域
    struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针
} CSNode,*CSTree;

这种存储表示法比较灵活。
其最大的优点就是可以方便地实现树转换为二叉树的操作，易于査找结点的孩子等，但缺点是从当前结点査找其双亲结点比较麻烦。
如果为每个结点增设一个 parent 域指向其父结点，则査找结点的父结点也很方便。

4.4.2 树、森林与二叉树的转换

由于二叉树和树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可以导出树与二叉树的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应。
从物理结构上看，树的孩子兄弟表示法与二叉树的二叉链表表示法相同，即每个结点共有两个指针，分别指向结点第一个孩子和结点的下一兄弟结点，而二叉链表中使用双指针。
因此，就可以用同一存储结构的不同解释将一棵树转换为二叉树。

树转换为二叉树的规则：每个结点左指针指向它的第一个孩子结点，右指针指向它在树中的相邻兄弟结点，可表示为“左孩子右兄弟”。
由于根结点没有兄弟，所以由树转换而得的二叉树没有右子树，如图 4-15 所示：

将森林转换为二叉树的规则与树类似。
先将森林中的每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为
转换后二叉树的右子树，第三棵树作为转换后二叉树根的右子树的右子树……依此类推，就可将森林转换为二叉树。

二叉树转换为森林的规则： 若二叉树非空，则二叉树根及其左子树为第一棵树的二叉树形式，二叉树根的右子树又可以看做是一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后产生一棵没有右子树的二叉树为止，这样就得到了原森林，如图 4-16 所示。
二叉树转换为树的规则与此类似，二叉树转换为树或森林是唯一的。

树转换成二叉树的画法：

1. 在兄弟结点之间加一连线；
2. 对每一个结点，只保留它与第一个子结点的连线，与其他子结点的连线全部抹掉；
3. 以树根为轴心，顺时针旋转 \(45^\circ\)。

森林转换成二叉树的画法：

1. 将每棵树的根相连；
2. 将森林中的每棵树转换成相应的二叉树；
3. 以第一棵树的根为轴心顺时针旋转 \(45^\circ\)（结合综合应用题第 2 题模拟）。

4.4.3 树和森林的遍历

树的遍历操作是以某种方式访问树中每一个结点，且仅访问一次。
树的遍历操作主要有先根遍历和后根遍历。

1. 先根遍历：若树非空，则先访问根结点，再按从左到右的顺序遍历根结点的每一棵子树。
   其访问顺序与这棵树相应二叉树的先序遍历顺序相同。
2. 后根遍历：若树非空，则按从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。
   其访问顺序与这棵树相应二叉树的中序遍历顺序相同（结合图 4-15 自行模拟）。
   另外，树也有层次遍历，与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。
   按照森林和树相互递归的定义，可得到森林的两种遍历方法。
   1. 先序遍历森林。
      若森林为非空，则按如下规则进行遍历：
      • 访问森林中第一棵树的根结点。
      • 先序遍历第一棵树中根结点的子树森林
      • 先序遍历除去第一棵树之后剩余的树构成的森林
   2. 中序遍历森林。若森林为非空，则按如下规则进行遍历：
      • 中序遍历森林中第一棵树的根结点的子树森林。
      • 访问第一棵树的根结点。
      • 中序遍历除去第一棵树之后剩余的树构成的森林。

树和森林的遍历：可采用对应二叉树的遍历算法来实现，见表 4-1。

4.4.4 树的应用—并查集

并査集是一种简单的集合表示，它支持以下 3 种操作：

1. Union(S,Rootl,Root2)：把集合 S 中的子集合 Root2 并入子集合 Rootl 中。
   要求 Root1 和 Root2 互不相交，否则不执行合并。
2. Find(S,x)：査找集合 S 中单元素 x 所在的子集合，并返回该子集合的名字。
3. Initial(S)：将集合 S 中每一个元素都初始化为只有一个单元素的子集合。

（编辑：ASP站长网）