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

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

2、 所示，给出了一棵二叉树的扩展二叉树，以及该扩展二叉树的先序序列。建立二叉链表的算法如下： 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树的中序序列确定左、右子树中结点的

3、个数；再根据结点个数在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。显然，这是一个递归过程。假设先序序列放在数组pre0.n-1中，中序序列放在数组mid0.n-1中，n是二叉树中元素的个数，其算法如下：int Find(ElemType *P, int L2 ,int H2, ElemType x)/在数组P的区间L2.H2内确定x的位置 i=L2;while(Pi!=x) i+; return i; / Findvoid Create (BiTree &T, int L1, int H1, int L2, i

4、nt H2)/已知先序序列preL1.H1，/中序序列midL2.H2构建二叉链表 if (L2>H2) T=NULL; /建空树 else T =(BiTree)malloc(sizeof(BiTNode); /创建根结点TT ->data=preL1; /给根数据域赋值 k=Find(mid, L2, H2, preL1); /找根在中序序列的位置Create (T ->Lchild, L1+1,k+L1-L2, L2,k-1);/创建左子树Create(T->Rchild,k+L1-L2+1,H1,k+1, H2); /创建右子树 / Create3 利用扩展完全

5、二叉树的顺序存储约定对二叉树上的结点从根结点起，自上而下，自左而右进行连续编号，根结点的编号为1。深度为k的，有n个结点的二叉树，当且仅当其每个结点的编号都与深度为k的满二叉树中编号为1至n中的结点一一对应时，称其为完全二叉树。如果一棵二叉树不是完全二叉树，可以用添加虚结点的方式将其扩展为一棵完全二叉树，虚结点的值设为#，表示该结点不存在，把这样处2 利用二叉树的先序序列和中序序列容易证明：由一棵二叉树的先序序列和中序序列可唯一的确定一棵二叉树。基本思想：先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；根据左、右子理后的二叉树称为原二叉树的扩

6、展完全二叉树。如图2中的(a)不是完全二叉树，(b)为(a)的扩展完全二叉树。完全二叉树的性质2：如果一棵完全二叉树有n个结点，则有：1）编号为i的结点如果有左孩子，则左孩子的编号为2i；2）如果有右孩子，则右孩子的编号为2i+1。 / Create 4 利用二叉排序树的性质 基本思想：从一棵空二叉树出发，按照先序序列依次插入各结点。假设先序列放在pre1.n中，中序序列放在mid1.n中，这里n是二叉树的结点个数。pre1是树的根，prei（i=2,3,n）究竟插在左子树上还是右子树上，则要看prei在中序序列中的位置，如果prei在pre1的之前，则插入到左子树上，否则插在右子树上。为此可

7、定义一个函数Find来确定结点在中序序列基本思想：1）将二叉树扩展为一棵完全二中的位置。叉树；2）根据编号将结点的值依次放在数组sFind：pre1.nà1.n 定义如下：的s1.n中。3）根据完全二叉树的性质，构造如果prei=midj 则 Find(prei)=j ；二叉树的二叉链表存储结构。这里n为扩展完全这样，对于pre1.n中的每个元素（即树上二叉树的结点个数，如图2中的n 为11。 的每个结点）都赋予了一个值，根据pre1.n和对于第3)步，s1是二叉树的根结点，如果赋予每个元素prei(i=1,2n)的Find（prei）值，2<=n则s2是s1的左孩子，否则左孩

8、子为空；按照构造二叉排序树的方法依次插入各结点，建如果3<=n则s3是s1的右孩子，否则右孩子立二叉树。其算法如下：int Find (ElemType *mid , int n, 为空；一般的，对于si：ElemType x) if (si= '#' ) then 建空树;else if (2i<=n) then s2i是si的左孩子/求x在中序序列中的位置for( j=1;j<=n ; j+) else 左孩子为空；if (2i+1<=n) then s2i+1是si的右孩子; if(x=midj) return j;/ Find else 右孩子为

9、空; 显然，这是一个递归过程。其算法如下： void Insert_Node(Bitree &T , Bitree s) void Create (Bitree &T , ElemType *s, int i, int n) /将s插在以T为根的二叉树的合适位置上 /创建一棵以si值为根的值的二叉树的二 if (T=NULL) T=s; /在空树上插入s /叉链表，树的根为T elseif(si='#') T =NULL; if(Find(T->data)>Find(s->data) else /将s所指结点插在左子树上 T =(BiTree)

10、malloc(*sizeof(BiTNode); Insert_Node(T->Lchild,s);/申请根结点 else /将s所指结点插在右子树上T ->data=si; Insert_Node(T->Rchild,s);/ 给根结点的数据域赋值 / Insert_Nodej=2*i; void Create (Bitree &T, int n)if (j<=n) /创建左子树 /建有n个结点的二叉树的二叉链表Create (T->Lchild , s, j, n); T=NULL; /先建立一棵空树else T->Lchild=NULL; for(j=1;j<=n;j+)j+; /依次产生结点和插入结点s= (BiTree)malloc(*sizeof(BiTNode);