第8讲树及二叉树的顺序存储

1、第8讲 树的定义和二叉树的顺序存储重点：二叉树的性质、顺序存储难点：二叉树性质的应用一、树的定义和和基本术语1定义 树是n个结点的有限集。在任意一棵非空树中，（1）有且仅有一个称为根的结点。（2）其余的结点被分为若干个互不相交的有限集，每个集合又是一棵树，称为该树的子树。2树的表示法图示法广义表表示法集合表示法 A B E F L G C H I M N D K J(d) 缩进表示法ADBCIMNHGEFLKJ(c) 集合表示法图5.1 树的几种表示法(A(B(E,F(L),G),C(H,I(M,N),D(J,K)(b) 广义表表示法ACEFGHJKLNM(a) 图示法BID缩进表示法3结点的

2、分类 终端结点和非终端结点 根、叶子、分支 双亲、孩子、祖先、子孙、兄弟、堂兄弟4度 结点的度 树的度5深度（高度/层数） 结点深度 树的深度6有序树与无序树7有向树与无向树8n元树：度为n9位置树：有序树，每个结点位置固定*10m叉树：m元位置树11森林：多个树构成。*12结论：n个结点的树中一定有n-1条边！ e=n-1二、二叉树的性质1二叉树的定义二叉树或者为空，或者是由一个根结点和两个互不相交的分别称为左子树和右子树的二叉树构成。(a) 空二叉树 (b) 仅有根结点 (c) 仅有左子树的 (d) 既有左子树又有 (e) 仅有右子树 的二叉树 二叉树 右子树的二叉树 的二叉树图5.2 二

3、叉树的五种基本形态2二叉树的五种形态3二叉树性质性质1：在二叉树的第i层上至多有2i-1个结点。 性质2：深度为k的二叉树至多有2k-1结点。(a) 满二叉树 (b) 完全二叉树图5.5 满二叉树与完全二叉树124895101137612425891011141537136121 *性质3：在二叉树中，叶子结点总数总比度为2的结点总数多一个。n0=n2+1证明：设n1和n为度为1的结点总数和整个结点总数。则，n0+n1+n2=n （1） 又 n1+n2*2=n-1 (2)作差并整理，得 n0=n2+1证毕 满二叉树和完全二叉树下面的性质均以完全二叉树为前提! 性质4：有n个结点的完全二叉树的深

4、度为log2n +1。 2k-1-1n2k-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)三

5、、二叉树的顺序存储利用一维数组将二叉树按完全（满）二叉树的形状存储，注意虚结点。 1类型定义 #define VirNode /* 用空格符描述“虚结点” */ #define MAXSIZE 64 typedef char ElemType; typedef ElemType SqBitTreeMAXSIZE; 0号单元存结点总数（满二叉树），（有时也存高度）2基本操作实现 （1）建立二叉树 void crebitree(SqBitTree BT,int n) /* n为二叉树真实结点数 */ int i,j,m; i=1; m=0; while(mn) for(j=i;j2*i;j+) s

6、canf(%c,BT+j); if(BTj!=VirNode) m+; i=2*i; BT0=i-1;（2）层次遍历（输出）void levellist(SqBitTree BT) int i,j; i=1; while(i=BT0) for(j=i;j2*i;j+) if(BTj=VirNode) printf(*); else printf(%c,BTj); printf(n); i*=2; （3）求二叉树的高度int high(SqBitTree BT) int h=0,i; i=1; while(i=BT0) h+;i*=2; return h;（4）交换所有结点的左右子树void e

7、xchlr(SqBitTree BT) int i,m,n;ElemType t; i=2; while(iBT0) for(m=i,n=2*i-1;mn;m+,n-) t=BTm;BTm=BTn;BTn=t; i*=2; （5）统计各类结点的数目（n0,n1,n2）int countleaf(SqBitTree BT) int i,n=0; for(i=1;i=BT0/2;i+) if(BTi!=VirNode&BT2*i=VirNode&BT2*i+1=VirNode) n+; for(;i=BT0;i+) if(BTi!=VirNode) n+; return n;int countn1

8、(SqBitTree BT) int i,n=0; for(i=1;i=BT0/2;i+) if(BTi!=VirNode&(BT2*i=VirNode&BT2*i+1!=VirNode| BT2*i!=VirNode&BT2*i+1=VirNode) n+; return n;int countn2(SqBitTree BT) int i,n=0; for(i=1;i=BT0/2;i+) if(BTi!=VirNode&BT2*i!=VirNode&BT2*i+1!=VirNode) n+; return n;ABCDE可参考的主函数：main() SqBitTree T;int n; clrscr(); crebitree(T,5); （见右侧图） l