构建二叉树的二叉链表存储结构

《构建二叉树的二叉链表存储结构》由会员分享，可在线阅读，更多相关《构建二叉树的二叉链表存储结构（3页珍藏版）》请在装配图网上搜索。

1、二叉树的二叉链表存储结构构建方法 假设有关二叉树的二叉链表存储的类型定 义如下： typedef struct BiTNode / 结点结构 ElemType data ；/数据域 struct BiTNode *Lchild ；/左孩子指针 struct BiTNode *Rchild； 右孩子指针 BiTNode ，*BiTree ；1 利用扩展二叉树的先序序列构建只根据二叉树的先序序列是不能唯一确定 一棵二叉树的。针对这一问题，可做如下处理： 对二叉树中每个结点的空指针引出一个虚结点， 设其值为#，表示为空，把这样处理后的二叉树 称为原二叉树的扩展二叉树。扩展二叉树的先序 序列可唯一确定

2、这棵二叉树。如图 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);/建 右子树 / Create2 利用二叉树的先序序列和中序序列容易证明：由一棵二叉树的先序序列和中序

3、序列可唯一的确定一棵二叉树。基本思想：先根据先序序列的第一个元素建 立根结点；然后在中序序列中找到该元素，确定 根结点的左、右子树的中序序列；根据左、右子 树的中序序列确定左、右子树中结点的个数；再 根据结点个数在先序序列中确定左、右子树的先 序序列；最后由左子树的先序序列与中序序列建 立左子树，由右子树的先序序列与中序序列建立 右子树。显然，这是一个递归过程。假设先序序列放 在数组pre0.n-l中，中序序列放在数组 mid0.n-l中，n是二叉树中元素的个数，其算 法如下：int Find(ElemType *P, int L2 ,int H2, ElemType x)/在数组P的区间L2

4、.H2内确定x的位置 i=L2;while(Pi!=x) i+;return i;/ Findvoid Create (BiTree &T, int Ll, int Hl, int L2, int H2)/已知先序序列 preLl.Hl，中序序列midL2.H2构建二叉链表if (L2H2) T=NULL; /建空树else T =(BiTree)malloc(sizeof(BiTNode);创建根结点TT -data=preLl; /给根数据域赋值 k=Find(mid, L2, H2, preLl);/找根在中序序列的位置Create (T -Lchild, Ll+l,k+Ll-L2, L

5、2,k-l);/创建左子树Create(T-Rchild,k+Ll-L2+l,Hl,k+l, H2);/创建右子树/ Create3 利用扩展完全二叉树的顺序存储约定对二叉树上的结点从根结点起，自上而 下，自左而右进行连续编号，根结点的编号为 l。 深度为k的，有n个结点的二叉树，当且仅当其 每个结点的编号都与深度为 k 的满二叉树中编 号为1至n中的结点对应时，称其为完全二叉树。如果一棵二叉树不是完全二叉树，可以用添 加虚结点的方式将其扩展为一棵完全二叉树，虚 结点的值设为#，表示该结点不存在，把这样处 理后的二叉树称为原二叉树的扩展完全二叉树。 如图2中的(a不是完全二叉树，(b为(a的扩

6、展 完全二叉树。完全二叉树的性质2：如果一棵完全二叉树 有n个结点，则有：1)编号为i的结点如果有 左孩子，则左孩子的编号为2i; 2)如果有右孩 子，则右孩子的编号为2i+1。區1 23456789 1011 |罔#冋#|#|#|#|可司爼 (a)二叉树 (b)扩展的完全二义树c)扩展的完全二义树的顺序存储 图2基本思想：1)将二叉树扩展为一棵完全二 叉树;2)根据编号将结点的值依次放在数组 s 的s1.中。3)根据完全二叉树的性质，构造 二叉树的二叉链表存储结构。这里n为扩展完全 二叉树的结点个数，如图2中的n为11。对于第3)步，s1是二叉树的根结点，如果 2=n则s2是s1的左孩子，否

7、则左孩子为空； 如果3二n则s3是s1的右孩子，否则右孩子 为空；一般的，对于si： if (s=i# ) t!建空树； else 辻(2i二n) then s2i是 si的左孩子 else左孩子为空； if (2i+1=n) then2i+1 是 si的右孩子; else右孩子为空；显然，这是一个递归过程。其算法如下：void Create (Bitree &T , ElemType *s, int/ Create4利用二叉排序树的性质基本思想：从一棵空二叉树出发，按照先序 序列依次插入各结点。假设先序列放在pre1.n 中,中序序列放在mid1.n中,这里n是二叉树 的结点个数。pre1是

8、树的根，preii=2,3,n) 究竟插在左子树上还是右子树上，则要看prei 在中序序列中的位置，如果pre在pre1的之 前，则插入到左子树上，否则插在右子树上。为 此可定义一个函数Find来确定结点在中序序列 中的位置。Find: pre1.n 1. n 定义如下：如果 prei=midj Find(prei)=j这样，对于pre1.中的每个元素(即树上 的每个结点)都赋予了一个值，根据pre1.和 赋予每个元素prei(i=1；n)的Find(prei)直， 按照构造二叉排序树的方法依次插入各结点，建 立二叉树。其算法如下： int Find (ElemType *mid , int

9、n, ElemType x)/求 x在中序序列中的位置for( j=1;jdata=si;/给根结点的数据域赋值j=2*i;if (j=n)/创建左子树Create (T-Lchild , s, j, n);else T-Lchild=NULL;j+;if(jRchild , s, j, n); else T -Rchild=NULL;if (=NULL) T=s; /在空树上插入s else if(Find(T-data)Find(s-data)/将s所指结点插在左子树上Insert_Node(T-Lchild,s);else /将s所指结点插在右子树上Insert_Node(T-Rchild,s);/ Insert_Nodevoid Create (Bitree &T, int n)/建有n个结点的二叉树的二叉链表T=NULL; /先建立一棵空树for(j=1;j=n;j+) /依/次产生结点和插入结点s= (BiTree)malloc(*sizeof(BiTNode); s -data=prej;s-Lchild=NULL;s-Rchild=NULL;Insert_Node(T,s);/插入 s / Create