全国计算机等级考试四级复习纲要二[3]
其中,data域称为数据域,用于存储二叉树结点中的数据元素;lchild域称为左孩子指针域,用于存放指向本结点左孩子的指针(这个指针及指针域有时简称为左指针)。类似地,rchild域称为右孩子指针域,用于存放指向本结点右孩子的指针(简称右指针)。二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。此外,每个二叉链表还必须有一个指向根结点的指针,该指针称为根指针。根指针具有标识二叉链表的作用,对二叉链表的访问只能从根指针开始。值得注意的是,二叉链表中每个存储结点的每个指针域必须有一个值,这个值或者是指向该结点的一个孩子的指针,或者是空指针NULL。
若二叉树为空,则root=NULL。若某结点的某个孩子不存在,则相应的指针为空。具有n个结点的二叉树中,一共有2n个指针域,其中只有n-1个用来指向结点的左右孩子,其余的n+1个指针域为NULL。
二叉树的链式存储结构操作方便,表达简明(二叉树的逻辑关系———结点间的父子关系———在二叉链表和三叉链表中被直接表达成对应存储结点之间的指针),因而成为二叉树最常用的存储结构。然而在某些情况下,二叉树的顺序存储结构也很有用。
(2)二叉树的顺序存储结构
二叉树的顺序存储结构由一个一维数组构成,二叉树上的结点按某种次序分别存入该数组的各个单元。显然,这里的关键在于结点的存储次序,这种次序应能反映结点之间的逻辑关系(父子关系),否则二叉树的基本运算就难以实现。
由二叉树的性质5可知,若对任一完全二叉树上的所有结点按层编号,则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。因此,对于任何完全二叉树来说,可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。具体地说就是:将编号为i的结点存入一维数组的第i个单元。
在这一存储结构中,由于一结点的存储位置(即下标)也就是它的编号,故结点间的逻辑关系可通过它们下标间的数值关系确定。
前程网推荐课程
咨询QQ:279768085 、879324637