搜索
第8讲树的定义和二叉树的顺序存储重点：二叉树的性质、顺序存储难点：二叉树性质的应用一、树的定义和和基本术语1．定义树是n个结点的有限集。在任意一棵非空树中，（1）有且仅有一个称为根的结点。（2）其余的结点被分为若干个互不相交的有限集，每个集合又是一棵树，称为该树的子树。2．树的表示法图示法广义表表示法集合表示法缩进表示法3．结点的分类终端结点和非终端结点根、叶子、分支双亲、孩子、祖先、子孙、兄弟、堂兄弟4．度结点的度树的度5．深度（高度/层数）结点深度树的深度6．有序树与无序树7．有向树与无向树8．n元树：度为nABEFLGCHIMNDKJ(d)缩进表示法ADBCIMNHGEFLKJ(c)集合表示法图5.1树的几种表示法(A(B(E,F(L),G),C(H,I(M,N)),D(J,K)))(b)广义表表示法ACEFGHJKLNM(a)图示法BID9．位置树：有序树，每个结点位置固定*10．m叉树：m元位置树11．森林：多个树构成。**12．结论：n个结点的树中一定有n-1条边！！！e=n-1二、二叉树的性质1．二叉树的定义二叉树或者为空，或者是由一个根结点和两个互不相交的分别称为左子树和右子树的二叉树构成。2．二叉树的五种形态3．二叉树性质性质1：在二叉树的第i层上至多有2i-1个结点。性质2：深度为k的二叉树至多有2k-1结点。**性质3：在二叉树中，叶子结点总数总比度为2的结点总数多一个。n0=n2+1证明：设n1和n为度为1的结点总数和整个结点总数。则，n0+n1+n2=n（1）又n1+n2*2=n-1(2)作差并整理，得n0=n2+1证毕(a)空二叉树(b)仅有根结点(c)仅有左子树的(d)既有左子树又有(e)仅有右子树的二叉树二叉树右子树的二叉树的二叉树图5.2二叉树的五种基本形态(a)满二叉树(b)完全二叉树图5.5满二叉树与完全二叉树124895101137612425891011141537136121满二叉树和完全二叉树下面的性质均以完全二叉树为前提!!!性质4：有n个结点的完全二叉树的深度为log2n+1。2k-1-1≤n≤2k-1（略）性质5：对于完全二叉树，双亲i/2，左孩子2i，右孩子2i+1。性质6：对于完全二叉树，结点个数为偶数时，n1=1，否则n1=0。性质7：对于完全二叉树，编号大于n/2的均为叶子结点。例，已知一棵完全二叉树中有723个结点，问（1）树的高度？（2）最后两层上各有多少个结点？（3）n0、n1、n2各是多少？解：（1）log2723+1=log2512+1=10（2）第9层有：29-1=256个，第10层上有：723-（29-1）=723-511=212（3）n1=0,n2=361,n0=362(n0=n2+1)三、二叉树的顺序存储利用一维数组将二叉树按完全（满）二叉树的形状存储，注意虚结点。○○○○○1．类型定义#defineVirNode‘‘/*用空格符描述“虚结点”*/#defineMAXSIZE64typedefcharElemType;typedefElemTypeSqBitTree[MAXSIZE];0号单元存结点总数（满二叉树），（有时也存高度）2．基本操作实现（1）建立二叉树voidcrebitree(SqBitTreeBT,intn)/*n为二叉树真实结点数*/{inti,j,m;i=1;m=0;while(mn){for(j=i;j2*i;j++){scanf(%c,BT+j);if(BT[j]!=VirNode)m++;}i=2*i;}BT[0]=i-1;}（2）层次遍历（输出）voidlevellist(SqBitTreeBT){inti,j;i=1;while(i=BT[0]){for(j=i;j2*i;j++)if(BT[j]==VirNode)printf(*);elseprintf(%c,BT[j]);printf(\n);i*=2;}}（3）求二叉树的高度inthigh(SqBitTreeBT){inth=0,i;i=1;while(i=BT[0]){h++;i*=2;}returnh;}（4）交换所有结点的左右子树voidexchlr(SqBitTreeBT){inti,m,n;ElemTypet;i=2;while(iBT[0]){for(m=i,n=2*i-1;mn;m++,n--){t=BT[m];BT[m]=BT[n];BT[n]=t;}i*=2;}}（5）统计各类结点的数目（n0,n1,n2）intcountleaf(SqBitTreeBT){inti,n=0;for(i=1;i=BT[0]/2;i++)if(BT[i]!=VirNode&&BT[2*i]==VirNode&&BT[2*i+1]==VirNode)n++;for(;i=BT[0];i++)if(BT[i]!=VirNode)n++;returnn;}intcountn1(SqBitTreeBT){inti,n=0;for(i=1;i=BT[0]/2;i++)if(BT[i]!=VirNode&&(BT[2*i]==VirNode&&BT[2*i+1]!=VirNode||BT[2*i]!=VirNode&&BT[2*i+1]==VirNode))n++;returnn;}intcountn2(SqBitTreeBT){inti,n=0;for(i=1;i=BT[0]/2;i++)if(BT[i]!=VirNode&&BT[2*i]!=VirNode&&BT[2*i+1]!=VirNode)n++;returnn;}可参考的主函数：main(){SqBitTreeT;intn;clrscr();crebitree(T,5);（见右侧图）levellist(T);printf(High=%d\n,high(T));exchlr(T);levellist(T);printf(n2=%d\n,countn2(T));getch();}作业：查找值为x的第一个结点，并输出其双亲结点和孩子结点的值。ABCDE