六章树ppt课件

1、第六章 树树的概念和基本术语n树由n (n 0)个结点组成的有限集合。n如果n = 0，称为空树；n如果n 0，则n有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；n除根以外的其它结点划分为m (m 0)个互不相交的有限集合t0, t1, , tm-1，每个集合又是一棵树，并且称之为根的子树(subtree)。n每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。n树的表示n树型表示na是根；nt1,t2都是根a的子树，且本身也是一棵树nt1=b,d,e,f,i,j； t2=c,g,h；bacghdefijn凹入表表示abdeijfcghn嵌套集合表示n嵌

2、套括号表示a ( b ( d, e ( i, j ), f ), c ( g, h ) )ijdfghabcen树的基本术语n结点(node)n结点的度(degree)n结点的子树个数n分支(branch)结点 n度不为0的结点n叶(leaf)结点n度为0的结点n子女(child)结点n某结点子树的根结点n双亲(parent)结点n某个结点是其子树之根的双亲bacghdefijn兄弟(sibling)结点n具有同一双亲的所有结点n祖先(ancestor)结点n若树中结点k到ks存在一条路径，则称k是ks的祖先 n子孙(descendant)结点n若树中结点k到ks存在一条路径，则称ks是k的子

3、孙 n结点所处层次(level)n根结点的层数为1，其余结点的层数为双亲结点的层数加1 n树的高度(depth)n树中结点的最大层数 bacghdefijn 有序树n树中结点的子树由左向右有序，子树的次序不能互换n 无序树n子树的次序可以互换n 森林nm(m 0)棵互不相交的树的集合n对树中每个结点而言，其子树的集合即为森林n树的基本操作n初始化n求指定结点所在树的根结点n求指定结点的双亲结点n求指定结点的某一孩子结点n求指定结点的最右边兄弟结点n将一棵树插入到另一树的指定结点下作为它的子树n删除指定结点的某一子树n树的遍历二叉树 (binary tree)n二叉树的定义n一棵二叉树是n（n0

4、）个结点的一个有限集合，该集合或者为空(n=0)，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。(递归定义：用二叉树定义二叉树)n二叉树的每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）n在二叉树中，子树是有顺序的，下面两棵二叉树是不同的。n思考：画出由三个结点所能组成的所有二叉树。n二叉树的性质n性质1 若二叉树的层次从1开始, 则在二叉树的第 i 层最多有 2i-1 个结点。(i 1)证明：i = 1 时，有2i-1 = 20 =1，成立假定 ：i = k 时性质成立，即第k层最多有2k-1个结点；当 i = k+1 时，由于二叉树的每个结点的度至多为2

5、，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，第k+1的结点至多是第k层结点的两倍，即总的结点个数至多为22k-1 = 2kn性质2 高度为k的二叉树最多有2k 1个结点。(k 1)证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质1可得二叉树的结点数至多为：20 + 21 + 22 + 23 + + 2k-1 = 2k 1n性质3 对任何一棵二叉树, 如果其度为0的叶结点个数为n0, 度为2的非叶结点个数为 n2, 则有n0n21证明：1、结点总数n=度为0的结点数度为1的结点数度为2的结点：n = n0 + n1 + n22、另一方面，二叉树中一度结点有一个孩子

6、，二度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n = n1 + 2n2 + 13、两式相减，得到：n0 = n2 + 1n特殊形态的二叉树n满二叉树 (full binary tree)n一棵深度为k且有2k -1个结点的二叉树n完全二叉树(complete binary tree)n若设二叉树的高度为h。除第h层外，其它各层的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。n性质4 具有 n (n 0) 个结点的完全二叉树的深度为log2n 1证明：设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有2h-1 - 1 n 2h 1 ，即 2h-

7、1 n 2h取对数 h-1 log2n 1, 则 i 的双亲为i /2n若2*i n/2 的结点必定是叶结点n若2*i+1 leftchild ); /递归 visit( t-data); inorder ( t-rightchild ); /递归 n先序遍历 (preorder traversal)n先序遍历二叉树算法的定义：若二叉树为空，则空操作；否则访问根结点 (v)；先序遍历左子树 (l)；先序遍历右子树 (r)。n遍历结果- + a * b - c d / e fn先序遍历二叉树的递归算法void preorder ( bitreenode *t ) if ( t != null )

8、 visit( t-data); preorder ( t-leftchild ); preorder ( t-rightchild ); n后序遍历 (postorder traversal)n后序遍历二叉树算法的定义：若二叉树为空，则空操作；否则后序遍历左子树 (l)；后序遍历右子树 (r)；访问根结点 (v)。n遍历结果a b c d - * + e f / -n后序遍历二叉树的递归算法：void postorder ( bitreenode * t ) if ( t != null ) postorder ( t-leftchild ); postorder ( t-rightchil

9、d ); visit( t-data); n*层序遍历n层序遍历二叉树算法的定义若二叉树为空，则空操作；否则，根结点入队，并作为当前结点；如队列不空，循环：将当前结点的左右孩子(非空)入队；做出队操作，队首元素作为当前结点最后，出队序列就是层序遍历序列n遍历结果- + / a * e f b - c d二叉树遍历应用n1、按先序建立二叉树(递归算法)n输入结点值的顺序必须对应二叉树结点先序遍历的顺序。n约定以输入序列中不可能出现的值作为空结点的值以结束递归。n例如用“”或用“-1”表示字符序列或正整数序列空结点。a b c d e g f abcdegfa b c d e g f status

10、 createbitree ( bitree& t ) scanf(&ch); /读入根结点的值 if ( ch= ) t=null; else if ( !(t=(bitreenode *) malloc(sizeof(bitreenode) /建立根结点 exit(overflow); t-data = ch; createbitree ( t-leftchild ); createbitree ( t-rightchild ); return ok;/createbitreen2、计算二叉树结点个数(递归算法)int count ( bitreenode *t ) if ( t = nu

11、ll ) return 0; else return (1 + count ( t-leftchild ) + count ( t-rightchild ) );n3. 求二叉树中叶子结点的个数(递归算法)int leaf_count(bitree t) if(!t) return 0; /空树没有叶子else if (!t-lchild & !t-rchild) return 1; /叶子结点else return (leaf_count(t-lchild) +leaf_count(t-rchild) ); /左子树的叶子数加上右子树的叶子数n4. 求二叉树高度(递归算法)int depth

12、 ( bitreenode * t ) if ( t = null ) return 0; else int m = depth ( t-leftchild ); int n = depth ( t-rightchild ) ); return (m n) ? (m+1) : (n+1); n5、在二叉树中查找具有给定值的结点bitree findnode(bitree t, datatype x) if ( t = null) return null; else if ( t-data = x) return t; else return( findnode(t-lchild, x)| fi

13、ndnode(t-rchild, x) );n6、给定一棵二叉树，输出其嵌套括号表示void print(bitree t) if (t) printf(“%d”, t-data); if (t-lchild |t-rchild) printf(“(”); print(t-lchild); if (t-rchild) printf(“,”); print(t-rchild); printf(“)”); 二叉排序树(binary sort tree)n二叉排序树或者是一棵空二叉树；或者是具有下列性质的二叉树：n（1）若它的左子树左子树不空，则左子树上所有结点的值均小于它的根结点的值；n（2）若它

14、的右子树右子树不空，则右子树上所有结点的值均大于它的根结点的值。n（3）根结点的左右子树分别也是二叉排序树。n二叉排序树可以用来组织一组数据，并且实现在这组数据上的快速检索。n在二叉排序树上检索给定的值限定二叉查找树上任何两个结点均不相同）n（1）若二叉排序树为空，查找失败。n（2）首先用给定的值和根结点的值进行比较，若相等，则查找成功。n（3）若给定的值比根结点的值小，则转根结点的左子树进行查找。n（4）若给定的值比根结点的值大，则转根结点的右子树进行查找。n在上图的二叉排序树中查找下列关键字 ：（1）kay（2）eva （3）royn计算在查找上述关键字时，各进行了几次比较运算？n试想一下

15、，在线性表中查找上述关键字需要作几次比较？树和森林n树的存储结构n1、双亲表示法n以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。n该方法利用每个结点只有一个双亲的特点，可以很方便求结点的双亲，但不方便求结点的孩子。abcdefgdataparenta b c d e f g- -1 0 0 0 1 1 30 1 2 3 4 5 6n用双亲表示实现的树定义#define maxsize100 /最大结点个数typedef char treedata; /结点数据类型定义typedef struct /树结点类型定义 treedata data; int par

16、ent; treenode;typedef treenode treemaxsize; /树n2、孩子表示法(多重链表 )n第一种方案：等数量的链域n空链域n(d-1)+1个。(d为树的度，n为结点数)n=总链域n*d 已用链域(n-1)abcdefgabcdefg data child1child2child3 childd n第二种方案：孩子链表n将每个结点的孩子链在该结点之后组成链表，再将所有头结点组成一个线性表abcdefgg6f5e4d3c2b1a0123 45 6 struct ctnode int child; /孩子所在位置ctnode *next;typedef ctnode

17、* childptr; struct ctbox elemtype data;childptr firstchild;struct ctree ctbox nodesmax_tree_size;int n, root;/结点数和根的位置;g6f5e4d3c2b1a0123 45 6 n3、树的左子女(第1个)-右兄弟(第1个)表示n二叉链表，结点结构：n空链域n+1个 datafirstchildnextsiblingabcdefgbcdgfe a n用左子女-右兄弟表示实现的树定义typedef char treedata;typedef struct node treedata data;

18、 struct node *firstchild, *nextsibling; treenode;typedef treenode* tree;n森林与二叉树的转换t1 t2 t3afhb c dgijek3 棵树的森林t1 t2 t3afbcdeghikj各棵树的二叉树表示abcedhikjfg森林的二叉树表示 n森林转换成二叉树n如果f = t1,t2,tm是森林，则可按照如下的规则将其转换成一棵二叉树b = (root, lb, rb)n1）若f为空，即m0，则b为空。n2）若f非空，即m0，则b的根root即为森林中第一棵树的根root(t1)；b的左子树lb是从t1中根节点的子树森林

19、f1= t11,t12, t1m1转换而成的二叉树；b的右子树rb是从森林f=t2, t3, , tm转换而成的二叉树。n二叉树转换成森林n如果b = (root, lb, rb)是一棵二叉树，则可按照如下规则转换成森林f = t1,t2,tm。n1）若b为空，则f为空。n2）若b非空，则f中第一棵树t1的根root(t1)即为二叉树的根root；t1中根结点的子树森林f1是由b的左子树lb转换而成的森林；f中除t1之外其余树组成的森林f=t2, t3, , tm是由b的右子树rb转换而成的森林。n若结点 x 是其双亲 y 的左孩子，则把 x 的右孩子，右孩子的右孩子，都与 y 用连线连起来，

20、最后去掉所有双亲到右孩子的连线。 n树的遍历n先根(次序)遍历n（1）访问树的根结点；n（2）从左向右依次先根遍历根的每棵子树。n后根(次序)遍历n（1）从左向右依次后根遍历根的每棵子树；n（2）访问树的根结点。n先根遍历 a，b，e，f，c，g，d，h，i，jn后根遍历e，f，b，g，c，h，i，j，d，aabcdefghijn树的遍历算法可借助二叉树的实现n先根遍历某树等价于先序遍历该树对应的二叉树n后根遍历某树等价于中序遍历该树对应的二叉树abcdefghijabcdefghija，b，e，f，c，g，d，h，i，j树,先根遍历二叉树,先序遍历abcdefghijabcdefghije，

21、f，b，g，c，h，i，j ，d，a树,后根遍历二叉树,中序遍历赫夫曼树 (huffman tree)n路径长度 pl (path length)n两个结点之间的路径长度，是连接两结点的路径上的分支数。n树的外部路径长度epl(external )n各叶结点(外结点)到根结点的路径长度之和n树的内部路径长度ipl(internal )n各分支结点(内结点)到根结点的路径长度之和n树的路径长度 pl = epl + ipl12345678树的外部路径长度树的外部路径长度epl = 3*1+2*3 = 9树的外部路径长度树的外部路径长度epl = 1*1+2*1+3*1+4*1 = 1023456

22、781n带权路径长度wpl (weighted path length)n二叉树的带权 (外部) 路径长度是树的各叶各叶结点所带的权值结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。10niiilwwplwpl = 2*2+ wpl = 2*1+ wpl = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35 222444555777带权带权( (外部外部) )路径路径长度达到最小长度达到最小n赫夫曼树n带权路径长度达到最小的二叉树即为赫夫曼树（最优二叉树）。n在赫夫曼树中，权值越大的结点离根越近。n赫夫曼算法(

23、构造赫夫曼树)n(1) 由给定的 n 个权值 w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林 f = t0, t1, t2, , tn-1 ，其中每棵扩充二叉树 ti只有一 个带权值 wi 的根结点, 其左、右子树均为空。n(2) 重复以下步骤, 直到 f 中仅剩下一棵树为止： 在 f 中选取两棵根结点的权值最小的扩充二叉树, 作为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 f 中删去这两棵二叉树。 把新的二叉树加入 f。n例：赫夫曼树的构造过程f : 7 5 2 47524初始f : 7 5 6合并2 475246f

24、 : 7 11 1175246合并5 6f : 18 5合并7 1127461118n上例存储结构5274weight parent leftchild rightchild7 -1 -1 -15 -1 -1 -12 -1 -1 -14 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -10123456初初 态态52746weight parent leftchild rightchild 7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 4 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -10123456p1p24423i过过 程程5

25、274611weight parent leftchild rightchild 7 -1 -1 -1 5 -1 -1 -1 2 4 -1 -1 4 4 -1 -1 6 -1 2 311 -1 -1 -1 -1 -1 -10123456p1p25514i5274611weight parent leftchild rightchild 7 -1 -1 -1 5 5 -1 -1 2 4 -1 -1 4 4 -1 -1 6 5 2 311 -1 1 418 -1 -1 -10123456p1p26605i18终终 态态n赫夫曼树的定义const int n = 20; /叶结点数const int

26、 m = 2*n -1; /结点数typedef struct float weight; int parent, leftchild, rightchild; htnode;typedef htnode huffmantreem;n建立赫夫曼树的算法void createhuffmantree(huffmantree t, float fr ) for ( int i=0; i n; i+ ) ti.weight = fri;for ( i=0; i m; i+ ) ti.parent = -1; ti.leftchild = -1; ti.rightchild = -1; for ( i

27、= n; i m; i+ ) n int min1 = min2 = maxnum;n int pos1, pos2;n for ( int j = 0; j i; j+ )n if ( tj.parent = -1 )n if ( tj.weight min1 )n pos2 = pos1; min2 = min1;n pos1 = j; min1 = tj.weight;n n else if ( tj.weight min2 )n pos2 = j; min2 = tj.weight; n ti.leftchild = pos1;n ti.rightchild = pos2;n ti.weight = tpos1.weight + tpos2.weight;n tpos1.parent = tpos2.parent = i;n n赫夫曼树的应用n最佳判定树考试成绩分布表考试成绩分布表 0, 60 ) 60, 70 ) 70, 80 ) 80, 90 ) 90, 1