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

文章作者 100test 发表时间 2007:03:10 18:40:44
来源 100Test.Com百考试题网

其中，data域称为数据域，用于存储二叉树结点中的数据元素.lchild域称为左孩子指针域，用于存放指向本结点左孩子的指针（这个指针及指针域有时简称为左指针）。类似地，rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针（简称右指针）。二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。此外，每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。根指针具有标识二叉链表的作用，对二叉链表的访问只能从根指针开始。值得注意的是，二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。

若二叉树为空，则root=NULL。若某结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的左右孩子，其余的n 1个指针域为NULL。

二叉树的链式存储结构操作方便，表达简明（二叉树的逻辑关系———结点间的父子关系———在二叉链表和三叉链表中被直接表达成对应存储结点之间的指针），因而成为二叉树最常用的存储结构。然而在某些情况下，二叉树的顺序存储结构也很有用。

（2）二叉树的顺序存储结构

二叉树的顺序存储结构由一个一维数组构成，二叉树上的结点按某种次序分别存入该数组的各个单元。显然，这里的关键在于结点的存储次序，这种次序应能反映结点之间的逻辑关系（父子关系），否则二叉树的基本运算就难以实现。

由二叉树的性质5可知，若对任一完全二叉树上的所有结点按层编号，则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。因此，对于任何完全二叉树来说，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。具体地说就是:将编号为i的结点存入一维数组的第i个单元。

在这一存储结构中，由于一结点的存储位置（即下标）也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。来源：www.examda.com

5.二叉树的遍历

由于二叉树的基本运算在链式存储结构上的实现比较简单，无需详加讨论。下面研究二叉树的一种较为复杂的重要运算———遍历及其在二叉链表上的实现。

遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。所谓“访问”一个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。遍历运算的关键在于访问结点的“次序”，这种次序应保证二叉树上的每个结点均被访问一次且仅一次。

由定义可知，一棵二叉树由三部分组成:根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”:

①访问根根点.

②遍历左子树（即依次访问左子树上的全部结点）.③遍历右子树（即依次访问右子树上的全部结点）。

因为左、右子树都是二叉树（可以是空二叉树），对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。由此可见，上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务，则人有六种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任务②在子任务③之前完成，这样就只剩下前三种次序，按这三种次序进行的遍历分别称为先根遍历（或前序遍历）、中根（或中序）遍历、后根（或后序）遍历。三种遍历方法的定义如下:

先根遍历 若需遍历的二叉树为空，执行空操作.否则，依次执行下列操作:

①访问根结点.

②先根遍历左子树.

③先根遍历右子树。

中根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作:

①中根遍历左子树.②访问根结点.③中根遍右子树。

后根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作:

①后根遍历左子树。②后根遍历右子树。③访问根结点。

显然，上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同.最先（最后、在中间）执行此子任务，则为先根（后根、中根）遍历。

按某种遍历方法遍历一棵二叉树，将得到该二叉树上所有结点的访问序列。

6.树

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

（1）孩子链表表示法

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

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

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

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

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