资源描述：
《二叉树的顺序存贮.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1.判断正误:完全二叉树的某结点若无左孩子,则它必是叶子结点(对)将一棵树转换成二叉树后,根结点没有左子树.(错)用二叉树的前序和中序可以导出二叉树的后序遍历.(对)2.由二叉树的前序和后序遍历序列(B)唯一地确定这棵二叉树.A.能B.不能3.有二叉树中序序列为:ABCEFGHD后序序列:ABFHGEDC，请画出此二叉树。4.若一棵二叉树,左右子树均有三个结点,其左子树的前序序列与中序序列相同,右子树的中序序列与后序序列相同,试构造该树如下图所示的二叉树是由有序树T1转换而来的二叉树,则树T1有(4)个叶子结点.ABECHFDI二叉树的存贮
2、二叉树的链接存贮树的标准存贮结构树的逆存贮结构树的扩充标准存贮结构二叉树的顺序存贮结构把树中的结点按某种适当的次序依次存放到一组连续的存贮单元中,使得结点的这种适当的次序能反映树结构的部分信息按层次序的存储形式首先对该二叉树中每个结点进行编号,然后以各结点的编号为下标,把各结点的值对应存储到一维数组中首先把树根结点的编号定为0然后按层次从上到下,每层从左到右的顺序,对每一结点进行编号当它的双亲结点的编号为i时,若它为左孩子,则编号为2i+1,若为右孩子,则编号为2(i+1)ABCGHDFEABCDEGFH0123456789101112按前
3、序的存贮形式附加左标志位和右指针附加两个标志位ABCEHDFG前序:ABDFCEGH附加左标志位和右指针左标志位:存放结点k后面的结点是否为k的左子结点ltag=0结点k后面的结点是k的左子结点ltag=1结点k无左子结点右指针rchild:指向结点k的右子结点ltagdatarchildABCEHDFGABDFCEGH0101001142-1-1-1 -17-1附加左标志位和右指针LtagdatarchildABCEHDFG#defineMAXN100structnode{intltag;chardata;intrchild;};type
4、defstructnodeNODE;NODEa[MAXN];ABCEHDFG附加左标志位和右指针01234567ABDFCEGH0101001142-1-1-1 -17-1Ltagdatarchild查找结点k的左子结点:if(a[p].ltag==0)printf(“%c”,a[p+1].data);else<结点k无左子结点>;查找结点k的右子结点:if(a[p].rchild==-1)<结点k没有右子结点>elseprintf(“%c”,a[a[p].rchild].data);查找结点k的按前序的前面结点:if(p-1<0)<结点k
5、没有按前序的前面结点>;elseprintf(“%c”,a[p-1].data);查找结点k的按前序的后面结点:if(p+1>=n)<结点k没有按前序的后面结点>;elseprintf(“%c”,a[p+1].data);查找结点k的父结点:if(p-1<0)<结点k没有父结点>elseif(a[p-1].tag==0)printf(“%c”,a[p-1].data);else{for(q=p-1;a[q].rchild!=p;q--);printf(“%c”,a[q].data);}附加两个标志位左标志位:存放结点k后面的结点是否为k的左
6、子结点ltag=0结点k后面的结点是k的左子结点ltag=1结点k无左子结点右标志位:结点k是否有右子结点rtag=0结点k有右子结点rtag=1结点k无右子结点ltagdatartagABCEHDFGLtagdatartagABDFCEGH0101001100111101structlrnode{chardata;charltag,rtag;};typedefstructrlnnodeLRNODE;查找k的左子结点:if(a[p].ltag==0)printf(“%c”,a[p+1].data);else<结点k无左子结点>;ABCEHD
7、FGLtagdatartagABDFCEGH0101001100111101查找树中所有结点的右子结点栈:存放rtag=0且尚末找到右子结点的结点的地址从根结点开始往下查找rtag=0的结点,依次把这些结点的地址进栈ltag=1的结点,此结点的后一个结点一定是栈顶结点的右子结点,栈顶结点退栈直到树中的结点都找到右子结点为止#include#defineMAXN100structnode{chardata;structnode*lchild;structnode*rchild;};typedefstructnodeNODE;
8、structlrnode{chardata;charltag,rtag;};typedefstructlrnodeLRNODE;NODE*transfer(tree,n)LRNO
