二叉树的存储表示.doc

二叉树的存储表示1二叉树的顺序存储表示2二叉树的链式存储表示3三叉链表1二叉树的顺序存储表示 二叉树的顺序存储结构的定义如下：#define MAXSIZE = 100； /暂定二叉树中节点数的最大值为100Typedef struct ElemType *data； /存储空间基址（初始化时分配空间）Int nodeNum； /二叉树中节点数SqBiTree； /二叉树的顺序存储结构为了能在存储结构中反映出节点之间的逻辑关系，必须将二叉树中节点依照一定规律安排在这组存储单元中。对于完全二叉树，只要从根起按层序存储即可。显然，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为 k 且只有 k 个结点的单支树（树中不存在度为 2 的结点）却需要长度为2k-1的一维数组。二叉树的顺序存储图如图1所示：图1 顺序存储2二叉树的链式存储表示二叉树有不同的链式结构，其中最常用的是二叉链表与三叉链表。二叉链表的结点形式如表1所示：lchilddatarchild表 1链式存储date域：称为数据域，用于存储二叉树结点中的数据元素，1child域：称为左孩子指针域，用于存放指向本结点左孩子的指针(左指针)。rchild域：称为右孩子指针域，用于存放指向本结点右孩子的指针(右指针)二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。根指针：每个二叉链表还必须有一个指向根结点的指针。根指针具有标识二叉链表的作用，对二叉链表的访问能从根指针开始。图2中（a）（b）表示一棵二叉树及其二叉链表。值得注意的是，二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。二叉链表的类型定义如下：Typedef struct btnode *bitreptr；Struct btnodeDatatype data；Bitreptr lchild,rchild；Bitreptr root；若二叉树为空，则root=NULL。若某结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的的左右孩子，其余的n+1个指针域为NULL。在二叉链表这种存储结构上，二叉树的多数基本运算如求根,求左、右孩子等很容易实现。但求双亲运算PARENT(BT,X)的实现却比较麻烦，而且其时间性能不高。3三叉链表三叉链表的类型定义如下：protected:BiTreeNode *lchild； / 指向左子树的指针BiTreeNode *rchild； / 指向右子树的指针BiTreeNode *parent； / 指向双亲的指针三叉链表存储每个节点由四个域组成，具体结构为：LchildDataRchildParent其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。为了便于查找