全国计算机等级考试四级复习纲要：树和二叉树

　　计算机四级网络工程师主要考察考核网络系统规划与设计的基础知识及中小型网络的系统组建、设备配置调试、网络系统现场维护与管理的基本技能。以下是学习啦小编为你整理的2015年计算机四级考试复习纲要：线性表，供大家参考和学习。

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

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

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

　　(2)二叉树的顺序存储结构

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

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

　　在这一存储结构中，由于一结点的存储位置(即下标)也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。

　　(3)双亲表示法

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

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

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