构建二叉树的二叉链表存储结构.doc
版权申诉
5星 · 超过95%的资源 170 浏览量
2022-07-06
12:48:55
上传
评论
收藏 670KB DOC 举报 
二叉树的二叉链表存储结构构建方法
假设有关二叉树的二叉链表存储的类型定
义如下：
typedef struct BiTNode{ // 结点结构
ElemType data ；//数据域
struct BiTNode *Lchild ；//左孩子指针
struct BiTNode *Rchild；//右孩子指针
} BiTNode ，*BiTree ；
1 利用扩展二叉树的先序序列构建
只根据二叉树的先序序列是不能唯一确定
一棵二叉树的。针对这一问题，可做如下处理：
对二叉树中每个结点的空指针引出一个虚结点，
设其值为#，表示为空，把这样处理后的二叉树
称为原二叉树的扩展二叉树。扩展二叉树的先
序序列可唯一确定这棵二叉树。如图 1 所示，
给出了一棵二叉树的扩展二叉树，以及该扩展
二叉树的先序序列。
建立二叉链表的算法如下：
void Create(BiTree &T)
{//输入扩展二叉树的先序序列，构建二叉链表
scanf(&ch); //输入一个元素
if (ch=='# ') T = NULL;
else
{ T= (BiTree)malloc(sizeof(BiTNode))；
//申请根结点
T->data =ch; // 给根结点数据域赋值
Create(T->Lchild);//建左子树
Create(T->Rchild);//建右子树
}
} // Create
2 利用二叉树的先序序列和中序序列
容易证明：由一棵二叉树的先序序列和中
序序列可唯一的确定一棵二叉树。
基本思想：先根据先序序列的第一个元素
建立根结点；然后在中序序列中找到该元素，
确定根结点的左、右子树的中序序列；根据左、
右子树的中序序列确定左、右子树中结点的个
数；再根据结点个数在先序序列中确定左、右
子树的先序序列；最后由左子树的先序序列与
中序序列建立左子树，由右子树的先序序列与
中序序列建立右子树。
显然，这是一个递归过程。假设先序序列
放 在 数 组 pre[0..n-1] 中 ， 中 序 序 列 放 在 数 组
mid[0..n-1]中，n 是二叉树中元素的个数，其算
法如下：
int Find(ElemType *P, int L2 ,int H2, ElemType
x)
{//在数组 P 的区间 L2..H2 内确定 x 的位置
i=L2;
while(P[i]!=x) i++;
return i;
}// Find
void Create (BiTree &T, int L1, int H1, int L2, int
H2)
{//已知先序序列 pre[L1..H1]，
//中序序列 mid[L2..H2]构建二叉链表
if (L2>H2) T=NULL; //建空树
else
{ T =(BiTree)malloc(sizeof(BiTNode));
//创建根结点 T
T ->data=pre[L1]; //给根数据域赋值
k=Find(mid, L2, H2, pre[L1]);
//找根在中序序列的位置
Create (T ->Lchild, L1+1,k+L1-L2, L2,k-1);
//创建左子树
Create(T->Rchild,k+L1-L2+1,H1,k+1, H2);
//创建右子树
}
}// Create
3 利用扩展完全二叉树的顺序存储
约定对二叉树上的结点从根结点起，自上
而下，自左而右进行连续编号，根结点的编号
为 1。深度为 k 的，有 n 个结点的二叉树，当且
仅当其每个结点的编号都与深度为 k 的满二叉
树中编号为 1 至 n 中的结点一一对应时，称其
为完全二叉树。
如果一棵二叉树不是完全二叉树，可以用添
加虚结点的方式将其扩展为一棵完全二叉树，
1
- 1
- 2
前往页