}//if
else Forest_Prim(G,k); /*对另外一个连通分量执行算法*/ }/*for*/
}/*Forest_Prim */
void Addto_Forest(CSTree &T,int i,int j)/*把边(i,j)添加到孩子兄弟链表表示的树T中*/ {
p=Locate(T,i); /*找到结点i对应的指针p,过程略*/ q=(CSTNode*)malloc(sizeof(CSTNode)); q->data=j;
if(!p) /*起始顶点不属于森林中已有的任何一棵树*/ {
p=(CSTNode*)malloc(sizeof(CSTNode)); p->data=i;
for(r=T;r->nextsib;r=r->nextsib); r->nextsib=p; p->firstchild=q;
} /*作为新树插入到最右侧*/
else if(!p->firstchild) /*双亲还没有孩子*/ p->firstchild=q; /*作为双亲的第一个孩子*/ else /*双亲已经有了孩子*/ {
for(r=p->firstchild;r->nextsib;r=r->nextsib);
r->nextsib=q; /*作为双亲最后一个孩子的兄弟*/ }
}/*Addto_Forest */ main()
{ ...
T=(CSTNode*)malloc(sizeof(CSTNode)); /*建立树根*/ T->data=1; Forest_Prim(G,1,T);
...
}/*main*/
分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得
到的,其时间复杂度为O(n^2).
11. 求出图7.27从顶点v1到其它各顶点之间的最短路径。绘制图表解题。 答:
dist path dist path dist path dist path dist path dist path V2 20 V1 20 V1 20 V1 20 V1 V3 5 V1 V4 ∞ V1 ∞ V1 V5 ∞ V1 ∞ V1 25 V6 25 V6 V6 ∞ V1 15 v3 S V1 V-S V2, v3,v4, v5, v6 shortpath v3 V1,v3 V2, v4,v5, v6 V6 19 V6 V1,v3, v6 v2, v4, v5 v4 V1,v3, v6,v4 V1,v3, v6,v4,v2 v2, v5 v5 v2 v5 25 V6 V1,v3, v6,v4,v2, v5
12. 写出图7.28的三种可能的拓朴排序结果。 答:
5,2,1,3,4,6,7,8 5,2,4,3,1,7,6,8 7,5,2,1,3,4,6,8
5 10 4 6 5 4 10 2 2 30 10 图7.27 1 20 1 5 2 3 8 7 4 3 5 4 图7.28 6
讨论小课堂8
[参考内容]
1．若二叉排序树中的一个结点存在两个孩子，那么它的中序后继结点是否有左孩子？它的中序前驱结点是否有右孩子？
【参考答案】：若p是给定的二叉排序树中的某个结点，且p有左、右孩子。按照中序遍历的思想，先中序遍历p的左子树，再访问根结点p，最后遍历p的右子树。左子树最后访问的结点x为p的前驱结点，x一定没有右子树，否者x不是左子树上中序遍历中最后访问的结点。因而，p的前驱结点x没有右孩子。同理，p的中序后继结点x没
有左孩子。
2．若将关键字1，2，3，┅，2k-1依次插入到一棵初始为空的AVL中，能证明结果树是完全平衡的吗？
【参考答案】：所谓“完全平衡”是指所有叶子结点处于树的同一层次上，并在该层是满的。
第一步，当k=1时，2-1=1，AVL树只有一个结点，它既是根又是叶子并处在第0层，根据二叉树性质，应具有20=1个结点。因此，满足完全平衡要求。
第二步，设k=n，插入关键码1，2，3，┅，2n-1到AVL树中，恰好每一层(层次号码是i=0，1，2，3，┅，n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k=n+1时，插入关键码为1，2，3，┅，2-1，2，┅，2-1，总共增加了从2n到2n+1-1的2n+1-1-2n+1=2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因此，满足完全平衡要求。
由上可的，能证明它是完全平衡的。
3．假设有关键码A、B、C和D，按照不同的输入顺序，共可能组成多少不同的二叉排序树？AVL树有几种？完全二叉树有几种？请画出其中高度较小的6种。
【参考答案】：本题的含义是：给定中序序列1，2，3，4，有几种不同的二叉排序树，这是树的计数问题。设中序遍历序列中元素数为n，则二叉树的数目为1这里n=4，故有14种。
AVL树有4种。 完全二叉树有1种。
6种高度较小的二叉排序树如下所示。
A B B C A C A D B D D C C B D A D B A B C 1
nnn+1
(n?1)?C2n，
nD A C
习题8
1．设二叉排序树中记录关键字由1至1000的整数构成，现在要查找关键字为363的记录结点，下述关键字序列哪个不可能是在二叉排序树上查找到的序列？
(1){2，252，401，398，330，344，397，363}； (2){924，220，911，244，898，258，362，363}； (3){925，202，911，240，912，245，363}；
(4){2，399，387，219，266，382，381，278，363}。 【参考答案】：(3)
2．设有一记录集合，集合中各记录的关键字分别为：90，31，12，40，74，94，14，26，35，85，64，9，55，60。
(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树。
(2)若对表中元素进行排序，构成有序表，求在等概率情况下对此有序表进行折半查找时，查找成功时的平均查找长度。 【参考答案】：
(1)
60 55 26 64 85 9 14 35 74 12 40 31 31 90
(2)折半查找判定树为
2 4 6 8 10 12 14 1 5 9 13 3 11 7
ASL=(1+2×2+3×4+4×7)/14=45/14
3．已知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用折半查找90时，需进行多少次查找了确定成功；当查找47时，需要经过多少次确定查找成功；查找100时，需要经过多少次确定查找不成功。 【参考答案】：2、4、3
4．已知一组关键字序列为：（17，31，13，11，20，35，25，8，4，24，40，27），按照依次插入结点的方法生成一棵平衡二叉排序树。(湖南大学2003年考研题) 【参考答案】：
4 20 25 40 8 13 24 35 11 31 17
5．将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插入初态为空的二叉排序树中(大小按照首字母在字母表中的先后次序)，请画出所得到的树T。然后画出删去for之后的二叉排序树T'，若再将for 插入T'中得到的二叉排序树T''是否与T相同?最后给出T\的先序、中序和后序序列。 【参考答案】：T\的先序序列是：do case class const while protected private if for int virtual public template
T\的中序序列是：case class const do for if int private protected public template virtual while
T\的后序序列是：const class case for int if private template public virtual protected