第27讲复习1.ppt

52 22 39 13 31 7 3 24 29 0 Vl(i) 52 22 39 13 24 4 3 6 1 0 Ve(i) W H G F E D C B A α 顶点 40 22 39 13 36 20 31 7 3 34 31 24 29 3 0 18 28 l(i) 22 22 39 13 13 13 24 4 3 3 6 6 1 0 0 0 0 e(i) a17 a16 a15 a14 a13 a12 a11 a10 a9 a8 a7 a6 a5 a4 a3 a2 a1 活动 A C D E F G H W B 1 2 8 13 7 6 3 4 6 10 5 21 11 16 1 12 17 5、试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态 。 b a c e d f g 15 12 2 6 8 10 4 5 2 4 9 5、试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态 。 b a c e d f g 15 12 2 6 8 10 4 5 2 4 9 顶点a到顶点b，c，d，e，f，g间的最短路径分别是15，2，11，10，6，13。 Homework： 21 21 21 21 21 21 * * 授课者：章 英 E-mail：walking7876@ Essential of Lecture Twenty-Seven： 一、树 二、图 二叉树的性质 遍历二叉树 线索二叉树 森林和二叉树的转换 哈夫曼树 知识体系结构 树 图 图的存储结构 图的遍历 最小生成树 拓扑排序和关键路径 最短路径 1、一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_____________。 1、一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_____________。 1+2*2+3*3+4*4 = n-1 = 1+2+3+4+X -1 得 X=21 2、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。 2、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。 n0+n1+n2 = n 20+30+n2 = n 而 n2=n0-1 = 19 得 n=69 3、设y指向中序二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild，rchild分别代表左，右孩子) x-ltag= ________; x-lchild= ________; y-ltag= ________; y-lchild= _____; x-rtag= _______; x-rchild= ________; if (x-lchild!=NULL) (x-lchild-rtag==1) x-lchild-rchild=__________; 3、设y指向中序二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild，rchild分别代表左，右孩子) x-ltag= 1; x-lchild= y-lchild; y-ltag= 0; y-lchild= x; x-rtag= 1; x-rchild= y; if (x-lchild!=NULL) (x-lchild-rtag==1) x-lchild-rchild= x ; 4、以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下： typedef struct node {char data; struct node *lchild,*rchild;}*bitree; void vst(bitree bt) /*bt为根结点的指针*/ { bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/ while(p || !empty(s)) /*栈s不为空*/ if(p) { push (s,p); (1)___; }