2017年全国计算机等级考试四级复习辅导7

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

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

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

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

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

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

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

5.二叉树的遍历

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

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

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

①访问根根点;

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

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

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

①访问根结点;

②先根遍历左子树;

③先根遍历右子树。

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

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

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

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

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

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

6.树

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

（1）孩子链表表示法

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

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

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

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

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

（3）双亲表示法

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

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

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

7.树的遍历

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

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

①访问根结点;

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

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

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

（3）层次遍历

①若树非空，访问根结点;

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

显然，按层次遍历所得的结点访问序列中，各结点的序号与按层编号所得的编号一致。

8.树与二叉树之间的转换

一般树转换为二叉树的基本思想是:将树中每个结点用两个链接表示就可以了，一个指向它最左边的孩子，另一个指向它右边的一个兄弟，从图形上看，具体步骤是:

①加线:在兄弟结点直接加一虚线;

②抹线:对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的边线;

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

二叉树还原为一般树的步骤是:

①加线:若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来;
计算机等级考试