数据结构课件：11 【习题课】第4章（含拓扑排序）

1、第四章习题作业4-2由三个结点A、B、C可以构成多少棵不同的树？不同的二叉树？二叉树区分左右子树 9种， 30种21作业4-3判断：一棵二叉树的所有叶结点在先根、中根和后根次序下的排列都按相同的相对位置出现。正确，按照先左后右的顺序。作业4-5判别给定二叉树是否为完全二叉树。完全二叉树：按层次顺序编号其中的结点，对应于满二叉树中的那些结点。高为k的完全二叉树第k-1层是满的，第k层如有空缺，则结点集中在最左边。123456按层次顺序遍历树的结点，判断：无左、有右孩子，则不是完全二叉树 (结点1)无左、无右孩子，则记录状态，判断后续结点是否有孩子。对于完全二叉树，后续结点不能有孩子。(结点2)有

2、左、右孩子，则继续下一结点。(结点5)有左、无右孩子，则记录状态，判断后续结点是否有孩子。对于完全二叉树，后续结点不能有孩子。(结点6)变量M变量Sint complete(BinTreeNode *t) AQueue q; /队列 bool S=1; bool M=1; if( t!=null) /根结点非空 q.QInsert(t); while(! q.IsEmpty() ) /队列非空 q.QDelete(p); /取出元素p if(p-left=null) if(p-right!=null) then M=0; return M; else S=0; /记录状态 else q.QIn

3、sert(p-left); if(p-right=null) then S=0; /记录状态 else q.QInsert(p-right); 作业4-6编写算法求任意二叉树中一条最长的路径，并输出此路径上各结点的值。（最左的一条路径）（从根结点到任意点的路径）非递归的后根遍历算法 设置一个工作栈： 结点所处状态i = 0, 1或2： 0：结点及左右子树均未被访问； 1：遍历左子树； 2：遍历右子树。树中任一结点q都需进栈三次，出栈三次。第一次出栈是为遍历结点q的左子树，第二次出栈是为遍历结点q的右子树，第三次出栈是为访问结点q . 结点 结点状态 i 当结点状态为2，且结点为栈顶元素时，栈中

4、存放了根结点到该结点的路径。这样可以得到所有结点到根节点的路径。(绿色圆圈)当结点状态为2，且当前结点为叶子结点时，栈中存放一条从根到叶子结点的路径。(红色圆圈)变量m记录最长路径的长度，数组long存放最长路径中的结点；每次当前结点的状态为2，且是叶子结点时，看栈中元素个数，若大于m，则将此时栈中元素存入long中。算法NPOS(t. path)N1建立堆栈 CREATS(S). CREATS(tmp). N2特殊情况 IF t=NULL RETURN.N3初始化 S (t,0). m0. N4利用栈实现递归 WHILE NOT(StackEmpty(S) DO ( (P,i) S. /弹出

5、元素 IF i=0 THEN ( S (P,1). IF left(P) null THEN S (left(P),0) . ) IF i=1 THEN ( S (P,2). IF right (P) null THEN S(right(P),0). ) IF i=2 THEN IF(left(P) =null AND right(P)=null AND S.topm) THEN ( j 0. long 0Data(P). m S.top. WHILE( !S.IsEmpty() DO (q pop(S). longj Data(q). tmp.push(q). j+.） WHILE( !tm

6、p.IsEmpty() DO （q pop(tmp). S.push(q).） ) . ). ) 总结1所有路径 总结2最左路径存储路径栈S遍历的结点； 栈I-对应结点的遍历情况，左子结点遍历 则为0，右子结点遍历则为1。尽量向深层搜索开始一直找左子结点，将结点入栈S，且结点状态为0，入栈I；（结点A）无左子结点时，将栈S顶部结点状态变为1，找该结点的右子节点，再继续上步操作；当前结点为空时，看栈顶元素，若状态为1，则查看栈S中元素个数，若大于当前最大长度，则更新最大长度值，更新数组path。ABCVoid Longpath(BinTreeNode *t, int size) BinTreeN

7、ode * Ssize; int Isize; BinTreeNode *now;/当前结点的指针 int m, top; /最长路径长度，栈顶指针 char pathsize;/保存最长路径的数组 now=t; top=0; m=0; if(t=null) return. if(t-left=null)&(t-right=null) return. while(now!=null | top 0) while(now!=null) top+, Stop=now; Itop=0; now=now-left; /沿左分支向下 /当前结点无左子节点If( top0) if(Itop=1) If(S

8、top-left=null)&(Stop right=null) &(topm) /叶子结点且 for(int i=1;idata; m=top; top-; else /栈顶元素状态为0 now=Spop; if(top0) now=now-right; Itop=1; For(int i=1;i=m;i+) coutpathi; cout“length=”maxd) maxd=d; p=NextBrother(p); Return maxd+1;作业4-12构造权值为5，13，21，7，18，31，41的哈夫曼树。5713拓扑排序 若图中存在边，则在拓扑序列中vi在vj之前。基本步骤： 从

9、图中选择一个入度为0的顶点且输出之。 从图中删除该顶点及其所有出边。执行 ，直至所有顶点已输出，或图中剩余顶点入度均不为0 (说明图中存在回路，无法继续拓扑排序)思想：数组count存放各个结点的入度， 找到count中所有入度为0的顶点并入栈； 栈顶取出一个顶点，输出，删除该顶点及所有出边，更改其余顶点的入度信息。ABCDE011120A0021BCDE121CBED0111 BED宽度优先遍历00343 E D不为栈另外分配存储空间，而是直接利用入度为0的顶点对应的count数组元素值来模拟堆栈的压入和弹出。 方法：设置一个指针top，指示栈顶位置；初始时，top=-1，表示栈空；当顶点i

10、的入度为0，需要入栈时，将指针所指的顶点序号放在counti中，即counti=top; 更新top，令其指向顶点i，即top=i；当弹出顶点时，记录栈顶位置，j=top; top退到次栈顶位置，即top=counttop;入栈操作：counti=top； top=i。顶点1，即i=1；则count1=-1，top=1；假设顶点3的入度变为0，将其入栈，即i=3；则count3=1； top=3； 栈元素为顶点3和顶点1。出栈操作： j=top；top=counttop。j=3，top=count3=1; 新栈顶为顶点1。30152 0 1 2 3 4 52Count数组：顶点的入度3-115

11、223-115023-11512算法TopoOrder(n) TOrder1初始化 /* 计算count数组 */ FOR i = 0 TO n-1 DO counti 0. FOR i = 0 TO n-1 DO ( p adjacent( Headi ) . WHILE p DO (countVerAdj(p) countVerAdj(p)+1. p link (p). ) )Head-顶点表；adjacent-边链表头指针VerAdj(p)-p所指的顶点序号325140002123013425count02431524235355拓扑排序算法： top -1. /栈顶指针top FOR

12、i = 0 TO n-1 DO/入度为0的顶点入栈IF counti = 0 THEN ( counti top. top i. )top102123013425count325140102123013425counttop1拓扑排序算法： top -1. /栈顶指针top FOR i = 0 TO n-1 DO/入度为0的顶点入栈IF counti = 0 THEN ( counti top. top i. )325140TOrder2拓扑排序 FOR i = 1 TO n DO IF top = - 1 THEN / 若循环体尚未被执行n次，栈顶指针已为-1 (PRINT “有回路! ”.

13、 RETURN. ) /说明有回路，终止程序 ELSE ( j top. top counttop . /* 弹出栈顶j */ PRINT ( j ) . p adjacent( Headj ) . / 扫描j的边链表 WHILE p DO ( k VerAdj(p) . countk countk-1. / 顶点k的入度减1 IF countk = 0 THEN /若入度为0，则k入栈 (countk top. top k.) p link (p). ) ) 删除边，更改相关顶点的入度；若度为0，则压入栈中 024315242353551 1013013425counttop32540ppp

14、 j top. top counttop . PRINT ( j ) . p adjacent( Headj ) . WHILE p DO /* 扫描j的边链表 */ (k VerAdj(p) . /*k的入度减1，若入度为0，则k入栈 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) p link (p). )原数组：-1,0,2,2,1,3top=1；弹栈之后，top=0； 32501 1 12013425counttopj top. top counttop . /* 弹出堆栈顶点j */PRINT ( j ) .p

15、adjacent( Headj ) . WHILE p DO/* 扫描j的边链表 */ (k VerAdj(p) . /* k的入度减1，若入度为0，则k入栈 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入栈 p link (p). ) 1 1 2013425counttop325j top. top counttop . /* 弹出堆栈顶点j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 扫描j的边链表 */ (k VerAdj(p) . /* k的入度减1，若入度为0，则k入栈 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入栈 p link (p). )1 1013425counttop35j top. top counttop . /* 弹出堆栈顶点j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 扫描j的边链表 */ (k VerAdj(p) . /* k的入度减1，若入度为0，则k入栈 */ countk countk-1. IF countk = 0 THEN (countk top.