全国计算机等级考试四级复习纲要二

6.树

　　树是一种常用的数据结构。为了适应各种应用问题的需要，多种不同的存储结构也相应地建立起来。下面介绍树的三种常用存储结构。

　　（1）孩子链表表示法

　　孩子链表表示法是树的一种链式存储结构。与二叉树的二叉链表存储方法类似，孩子链表表示法的基本思想是:树上的一个结点的内容（数据元素）以及指向该结点所有孩子的指针存储在一起以便于运算的实现。由于树上的结点的度（孩子数）没有限制，而且各个结点的度可能相差很大，一种自然的表示方法是为树上的每个结点X建立一个“孩子链表”，以便存储X中的数据元素和指向X的所有孩子的指针。一个孩子链表是一个带头结点的单链表，单链表的头结点含两个域:数据域和指针域。其中，数据域用于存储结点X中的数据元素;指针域用于存储指向该单链表中第一个表结点（首结点）的指针。为了检索方便，所有头结点组织成一个数组，称为表头数组。对每个结点X的孩子链表来说，其中的所有表结点也含两个域，孩子域（即数据域）和指针域。第i个表结点的孩子域存储X的第i个孩子在头结点数组中的下标值。

　　（2）孩子兄弟链表表示法

　　孩子兄弟链表中所有存储结点的形式相同，均含三个域:数据域———用于存储树上的结点中的数据元素;孩子域———用于存储指向本结点第一个孩子的指针;兄弟域———用于存放指向本结点下一个兄弟的指针。

　　值得注意的是，孩子兄弟链表的结构形式与二叉链表完全相同;但存储结点中指针的含义不同。二叉链表中存储结点的左、右指针分别指向左、右孩子;而孩子兄弟链表中存储结点的两个指针分别指向“长子”和“大弟”。

　　在孩子兄弟链表表示法中，结点形式统一，结点间的联系比较简捷。同时，在这种存储结构上容易实现树数据结构的大多数运算。

　　（3）双亲表示法
　　
　　树上每个结点的孩子可以有任意多个，但双亲只有一个。因此，通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简法的。树的这种存储表示方法称为双亲表示法。在双亲表示法下，每个存储结点由两个域组成:数据域———用于存储树上结点中的数据元素;“指针”域———用于指示本结点之双亲所在的存储结点。值得注意的是，“指针”域的类型定义可以有两种选择。第一种是将其定义为高级语言（如C语句）中的指针类型。通过将存储结点中的指针域定义为高级语言中的指针类型，就得到各种链式存储结构，如单链表、二叉链表、孩子链表等等。第二种选择是将“指针”域定义为整型、子界型等型。严格地说，无论选择上述哪种定义，得到的都是链式存储结构，因为在这两种定义之下，各存储结点之间的联结是通过“指针”完成的，而且这些指针反映了结点之间的逻辑关系。

　　为了区别这两种链式结构，通常将指针域定义为高级语言中的指针类型的各种链式存储结构（如单链表、二叉链表等等）称为“动态链表”，相应的指针称为“动态指针”;将指针域定义为整型、子界型等类型的各种键式存储结构称为“静态链表”，相应的“指针”称为:“静态指针”。动态链表中的结点是通过高级语言中的标准过程例如C语言的库函数malloc（size）动态（即运行期间）生成的（动态链表由此得名），无需事先规定链表的容量，因此动态链表的大小是动态变化的。相反，静态链有的容量必须事先说明，因而其大小是固定的。然而，在某些情况下，特别是当结点数固定不变且可事先确定时，采用静态链表往往更加方便、直观。

　　静态双亲链表由一个一维数组树成。数组的每个分量包含两个域:数据域和双亲域。数据域用于存储树上一个结点中的数据元素;双亲域用于存放本结点的双亲结点在数组中的序号（下标值）。

　　7.树的遍历

　　与二叉树类似，遍历是树的一种重要运算。树的主要遍历方法有以下三种。

　　（1）先根遍历若树非空，则

　　①访问根结点;

　　②依次先根遍历根的各个子树T 1 ，…，T m 。

　　（2）后根遍历若树非空，则

　　①依次先根遍历根的各个子树T 1 ，…，T m 。②访问根结点;

　　（3）层次遍历

　　①若树非空，访问根结点;
　　
　　②若第1，…，i（i≥1）层结点已被访问，且第i+1层结点未访问，则从左到右依次访问第i+1层结点。

　　显然，按层次遍历所得的结点访问序列中，各结点的序号与按层编号所得的编号一致。
　　　
　　8.树与二叉树之间的转换
　　
　　一般树转换为二叉树的基本思想是:将树中每个结点用两个链接表示就可以了，一个指向它最左边的孩子，另一个指向它右边的一个兄弟，从图形上看，具体步骤是:

　　①加线:在兄弟结点直接加一虚线;
　　
　　②抹线:对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的边线;

　　③旋转:将新加上的虚线改为实线，并将虚线以及有关的实线顺时钟旋转45度。

　　二叉树还原为一般树的步骤是:
　　
　　①加线:若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来;
　　　
　　②抹线:抹去原二叉树中所有结点与其右孩子的连线;

　　③旋转:将虚线及有关实线逆时钟旋转约45度，并将几个结点按层次排列。

　　9.二叉树与森林之间的转换

　　森林转换为二叉树的步骤是:
　　
　　①将森林中的每棵树转换为二叉树;
　　
　　②森林中第一棵树的根结点就是转换后二叉树的根结点，依次将后一棵树作为前一棵树根结点的右子树。
　　
　　二叉树转换为森林的步骤是:

　　①森林第一棵树的根就是二叉树的根;

　　②二叉树的左子树转换为森林的第一棵树，二叉树的右子树对应于森林中其余的树;③二叉树右子树的根结点作为余下树中第一棵树的根结点……，以此类推。

希望与更多计算机等级考试的网友交流，请进入计算机等级考试论坛

更多信息请访问：考试吧计算机等级考试栏目