|
顺序存储结构 该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中结点在这个序列中的相互位置还能反映出结点之间的逻辑关系 ．完全二叉树结点编号 （） 编号办法 在一棵n个结点的完全二叉树中从树根起自上层到下层每层从左至右给所有结点编号能得到一个反映整个二叉树结构的线性序列 【例】如下图所示 （） 编号特点 完全二叉树中除最下面一层外各层都充满了结点每一层的结点个数恰好是上一层结点个数的倍从一个结点的编号就可推得其双亲左右孩子兄弟等结点的编号假设编号为i的结点是ki(≤i≤n)则有 ①若i>则ki的双亲编号为 若i=则Ki是根结点无双亲 ②若i≤n则Ki的左孩子的编号是i否则Ki无左孩子即Ki必定是叶子因此完全二叉树中编号 的结点必定是叶结点 ③若i+≤n则Ki的右孩子的编号是i+否则Ki无右孩子 ④若i为奇数且不为则Ki的左兄弟的编号是i否则Ki无左兄弟 ⑤若i为偶数且小于n则Ki的右兄弟的编号是i+否则Ki无右兄弟 ．完全二叉树的顺序存储 将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[n]中 其中 bt[．．n]用来存储结点 bt[]不用或用来存储结点数目 【例】表是图所示的完全二叉树的顺序存储结构bt[]为结点数目b[]的双亲左右孩子分别是bt[]bt[l]和bt[] ．一般二叉树的顺序存储 （） 具体方法 ① 将一般二叉树添上一些 虚结点成为完全二叉树 ② 为了用结点在向量中的相对位置来表示结点之间的逻辑关系按完全二叉树形式给结点编号 ③ 将结点按编号存入向量对应分量其中虚结点用∮表示 【例】图中单支树的顺序存储结构如下图 （） 优点和缺点 ① 对完全二叉树而言顺序存储结构既简单又节省存储空间 ② 一般的二叉树采用顺序存储结构时虽然简单但易造成存储空间的浪费 【例】最坏的情况下一个深度为k且只有k个结点的右单支树需要k个结点的存储空间 ③在对顺序存储的二叉树做插入和删除结点操作时要大量移动结点 ．二叉树的顺序存储结构类型定义 【参见参考书】 链式存储结构 ．结点的结构 二叉树的每个结点最多有两个孩子用链接方式存储二叉树时每个结点除了存储结点本身的数据外还应设置两个指针域lchild和rchild分别指向该结点的左孩子和右孩子结点的结构为 ．结点的类型说明 typedef char DataType //用户可根据具体应用定义DataType的实际类型 typedef struct node{ DataType data Struct node *lchild*rchild //左右孩子指针 }BinTNode //结点类型 typedef BinTNode *BinTree//BinTree为指向BinTNode类型结点的指针类型 ．二叉链表（二叉树的常用链式存储结构） 在一棵二叉树中所有类型为BinTNode的结点再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root就构成了二叉树的链式存储结构并将其称为二叉链表 【例】下面左图所示二叉树的二叉链表如下面中图所示 注意 ① 一个二叉链表由根指针root惟一确定若二叉树为空则root=NULL若结点的某个孩子不存在则相应的指针为空 ② 具有n个结点的二叉链表中共有n个指针域其中只有n个用来指示结点的左右孩子其余的n+个指针域为空 ．带双亲指针的二叉链表 经常要在二叉树中寻找某结点的双亲时可在每个结点上再加一个指向其双亲的指针parent形成一个带双亲指针的二叉链表 【例】上面右图是上面左图所示的二叉树的带双亲指针的二叉链表 注意 二叉树存储方法的选择主要依赖于所要实施的各种运算的频度 |
