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

1、构建二叉树的二叉链表存储结构文献标识码：B1 引言高等学校计算机科学与技术专业发展战略研究报告暨专业规范中将“计算机科学与技术”专业名称下的人才培养规格归纳为三种类型、四个不同的专业方向：科学型（计算机科学专业方向）、工程型（包括计算机工程专业方向和软件工程专业方向）、应用型（信息技术专业方向）。“数据结构”课程出现在四个专业方向的核心课程中，而树型结构同样无一例外的出现在了四个专业方向的核心知识单元中。树型结构描述的是研究对象之间一对多的关系。在存储树时，如果用指针来描述元素之间的父子关系，则由于对每个元素的孩子数量没有限制（最小可以是0，最多可以是树的度d），若结点的结构定义为一个数据域d

2、ata和d个指针域，则可以证明，有n个结点、度为d的树的多重链表存储结构中，有n*（d-1）+1个空链域，采用这样的存储将造成很大的浪费。二叉树是树型结构的一种特殊情况，对于它的操作和存储要比树简单的多，且树和森林可以用二叉链表做媒介同二叉树进行相互转换，所以对二叉树的研究就显得特别重要。二叉树的二叉链表存储是二叉树的一种重要的存储结构，在每一本“数据结构”教材中都占据了一定的篇幅，但对于怎样建立一棵二叉树的二叉链表存储结构，却很少提及。笔者从事“数据结构”课程教学已二十余年，总结出了以下四种构建方法，希望能对同仁和学数据结构的学生有所帮助。通过本文的学习，学生将会对二叉链表和递归有更深入的理

3、解。2 二叉树的二叉链表存储结构构建方法假设有关二叉树的二叉链表存储的类型定义如下：typedefstructBiTNode/结点结构ElemTypedata；/数据域structBiTNode*Lchild；/左孩子指针structBiTNode*Rchild；/右孩子指针BiTNode，*BiTree；说明：ElemType为二叉树的元素值类型，根据具体情况进行定义，本文假设为char型；BiTNode为结点类型；BiTree为指向BiTNode的指针类型。下面的算法均用类C描述。2.1 利用扩展二叉树的先序序列构建只根据二叉树的先序序列是不能唯一确定一棵二叉树的。针对这一问题，可做如下处

4、理：对二叉树中每个结点的空指针引出一个虚结点，设其值为#，表示为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的先序序列可唯一确定这棵二叉树。如图1所示，给出了一棵二叉树的扩展二叉树，以及该扩展二叉树的先序序列。建立二叉链表的算法如下：voidCreate(BiTree&T)/输入扩展二叉树的先序序列，构建二叉链表scanf(&ch);/输入一个元素if(ch='#')T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode)；/申请根结点T->data=ch;/给根结点数据域赋值Create(T->Lchi

5、ld);/建左子树Create(T->Rchild);/建右子树/Create2.2 利用二叉树的先序序列和中序序列容易证明：由一棵二叉树的先序序列和中序序列可唯一确定一棵二叉树。基本思想：先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；根据左、右子树的中序序列确定左、右子树中结点的个数；再根据结点个数在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。显然，这是一个递归过程。假设先序序列放在数组pre0.n-1中，中序序列放在数组mid0.n-1中，n是二叉树中元素

6、的个数，其算法如下：intFind(ElemType*P,intL2,intH2,ElemTypex)在数组P的区间L2.H2内确定x的位置i=L2;while(Pi!=x)i+;returni;/FindvoidCreate(BiTree&T,intL1,intH1,intL2,intH2)/已知先序序列preL1.H1，/中序序列midL2.H2构建二叉链表if(L2>H2)T=NULL;/建空树elseT=(BiTree)malloc(sizeof(BiTNode);/创建根结点TT->data=preL1;/给根数据域赋值k=Find(mid,L2,H2,preL1

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

8、为原二叉树的扩展完全二叉树。如图2中的(a)不是完全二叉树，(b)为(a)的扩展完全二叉树。完全二叉树的性质：如果一棵完全二叉树有n个结点，则有1) 编号为i的结点如果有左孩子，则左孩子的编号为2i；2)如果有右孩子，则右孩子的编号为2i+1。基本思想：1) 将二叉树扩展为一棵完全二叉树；2) 根据编号将结点的值依次放在数组s的s1.n中；3) 根据完全二叉树的性质，构造二叉树的二叉链表存储结构。这里n为扩展完全二叉树的结点个数，如图2中的n为11。对于第3)步，s1是二叉树的根结点，如果2/创建一棵以si值为根的值的二叉树的二/ 叉链表，树的根为 Tif(si='#')T=N

9、ULL;elseT=(BiTree)malloc(*sizeof(BiTNode);/申请根结点T->data=si;/给根结点的数据域赋值j=2*i;if(jLchild,s,j,n);elseT->Lchild=NULL;j+;if(jRchild,s,j,n);elseT->Rchild=NULL;/Create2.4 利用二叉排序树的性质基本思想：从一棵空二叉树出发，按照先序序列依次插入各结点。假设先序列放在pre1.n中，中序序列放在mid1.n中，这里n是二叉树的结点个数。pre1是树的根，prei(i=2,3,-n)究竟插在左子树上还是右子树上，则要看prei在

10、中序序列中的位置，如果prei在pre1的之前，则插入到左子树上，否则插在右子树上。为此可定义一个函数Find来确定结点在中序序列中的位置。Find:pre1.na1.n定义如下：如果prei=midj则Find(prei)=j；这样，对于pre1.n中的每个元素(即树上的每个结点)都赋予了一个值，根据pre1.n和赋予每个元素prei(i=1,2门)的Find(prei)值，按照构造二叉排序树的方法依次插入各结点，建立二叉树。其算法如下：intFind(ElemType*mid,intn,ElemTypex)/求x在中序序列中的位置for(j=1;jdata)>Find(s->data)/将s所指结点插在左子树上Insert_Node(T->Lchild,s);else/将s所指结点插在右子树上Insert_Node(T->Rch