讲树及叉树的顺序存储.docVIP

第8讲 树的定义和二叉树的顺序存储 重点：二叉树的性质、顺序存储 难点：二叉树性质的应用 一、树的定义和和基本术语 1．定义 树是n个结点的有限集。在任意一棵非空树中， （1）有且仅有一个称为根的结点。 （2）其余的结点被分为若干个互不相交的有限集，每个集合又是一棵树，称为该树的子树。 2．树的表示法 图示法 广义表表示法 集合表示法 缩进表示法 3．结点的分类 终端结点和非终端结点 根、叶子、分支 双亲、孩子、祖先、子孙、兄弟、堂兄弟 4．度 结点的度 树的度 5．深度（高度/层数） 结点深度 树的深度 6．有序树与无序树 7．有向树与无向树 8．n元树：度为n 9．位置树：有序树，每个结点位置固定 *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 证毕 满二叉树和完全二叉树 下面的性质均以完全二叉树为前提!!! 性质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个结点，问 树的高度？ 最后两层上各有多少个结点？ 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．类型定义 #define VirNode ‘ ‘ /* 用空格符描述“虚结点” */ #define MAXSIZE 64 typedef char ElemType; typedef ElemType SqBitTree[MAXSIZE]; 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++) { scanf(%c,BT+j); if(BT[j]!=VirNode) m++; } i=2*i; } BT[0]=i-1; } （2）层次遍历（输出） void levellist(SqBitTree BT) { int i,j; i=1; while(i=BT[0]) { for(j=i;j2*i;j++) if(BT[j]==VirNode) printf(*); else printf(%c,BT[j]); printf(\n); i*=2; } } （3）求二叉树的高度 int high(SqBitTree BT) { int h=0,i; i=1; while(i=BT[0]) { h++;i*=2;} return h; } （4）交换所有结点的左右子树 void exchlr(SqBitTree BT) { int i,m,n;ElemType t; i=2; while(iBT[0]) { for(m