{ front=front%maxsize+1; //出队 t=que[front]; printf(t->data);
if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1;
que[rear]=t->lchild; }
if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild;
}
}while (rear= =front); //队列为空时结束 }
}
3. 写出在中序线索二叉树中结点P的右子树中插入一个结点s的算法。
3. 解答：设该线索二叉树类型为bithptr，包含5个域：lchild，ltag，data，rchild，rtag。
insert(p, s) //将s结点作为p的右子树插入 BiThrNode *p,*s; { BiThrNode *q;
if (p->rtag= =1) //无右子树，则有右线索 { s->rchild=p->rchild; s->rtag=1; p->rchild=s; p->rtag=0; } else
{ q=p->rchild;
while(q->ltag= =0) //查找p所指结点中序后继，即为其右子树中最左下的结点
q=q->lchild; q->lchild=p->rchild; s->rtag=0; p->rchild=s; }
s->lchild=p; //将s结点的左线索指向p结点 s->ltag=1; }
4. 给定一棵二叉树，用二叉链表表示，其根指针为t，试写出求该二叉树中结点n的双亲结点的算法。若没有结点n或者该结点没有双亲结点，分别输出相应的信息；若结点n有双亲，输出其双亲的值。
4. 解答：利用一个队列来完成，设该队列类型为指针类型，最大容量为maxnum。算法中的front为队头指针，rear为队尾指针，若当前队头结点的左、右子树的根结点不是所求结点，
则将两子树的根结点入队，否则，队头指针所指结点即为结点的双亲。
parentjudge(t,n) BiTree *t; int n;
{ BiTree *que[maxnum]; int front,rear; BiTree *parent; parent=NULL; if (t)
if (t->data= =n)
printf(“no parent!”); //n是根结点，无双亲 else
{ front=0; //初始化队列
rear=1;
que[1]=t; //根结点进队 do
{ front=front%maxsize+1; t=que[front];
if((t->lchild->data= =n)|| (t->rchild->data= =n)) //结点n有双亲 { parent=t; front=rear;
printf(“parent”,t->data); } else
{ if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1; }
}while(rear= =front); //队空时结束
} }
if (parent = =NULL) printf(“结点不存在”);
}
if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild; }
que[rear]=t->lchild;
习题5参考答案
一、单项选择题
二、判断题 三、填空题 四、应用题 A B G C H K D I L E J M F N O
图5-16
五、算法设计题
50 20
30
9 11 14 16
7 7
2 5 图5-17
第6章 图
【例6-1】回答下列问题：
（1）具有n个顶点的连通图至少有多少条边?
（2）具有n个顶点的强连通图至少有多少条边?这样的图应该是什么形状? （3）具有n个顶点的有向无环图最多有多少条边? 解：
（1）具有n个顶点的连通图至少有n-1条边。
这是一个与生成树相关的问题。生成树是一个连通图，它具有能够连通图中任何两个顶点的最小边集，任何一个生成树都具有n-1边。因此，具有n个顶点的连通图至少有n-1条边。
（2）具有n个顶点的强连通图至少有n条边，这样的图是一个由n个顶点构成的环。 强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通，因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧，每个顶点的入度和出度至少各为1，即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数=2×n/2=n。
（3）具有n个顶点的有向无环图最多有n×(n—1)/2条边。 这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，?，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有(n-1)+(n-2)+ ? +2+1=n×(n-1)/2条边。
2．图的存储结构
常用的存储结构有邻接矩阵和邻接表。 （1）邻接矩阵表示法
设G＝(V，E)是有n(n≥1)个顶点的图。则G的邻接矩阵是按如下定义的n阶方阵： 1 当（Ｖi,Vj）∈E或<Ｖi,Vj >∈E时
cost[i,j]=
0 其它
例如，图6-1中G1，Ｇ2的邻接矩阵分别表示为A1、A2，矩阵的行列号对应于图6-1中结点的序号。 0 1 1 0 0 1 1
A2= 1 0 1 1 A1= 0 0 1 1 1 0 1 0 0 0 0 1 1 0 由邻接矩阵的定义可知，无向图的邻接矩阵必定是对称阵；有向图的邻接矩阵不一定是对称的。
根据邻接矩阵，很容易判定任意两个顶点之间是否有边相连。求各顶点的度也是非常容易的。对于无向图，顶点Vi的度就是邻接矩阵中第i行(或第j列)上非零元的个数，即
di??cost[i,j]i?1n。对于有向图，第i行中非零元的个数为顶点Vi的出度，而第i列上的非
零元个数为顶点Vi的入度。
（2）邻接表表示法
图的邻接链表存储结构是一种顺序分配和链式分配相结合的存储结构括两个部分：一部分是向量，另一部分是链表。
邻接链表中的表头部分是向量，用来存储n个表头结点。向量的下标指示顶点的序号。 例如，对于图6-1中G1和G2，其邻接链表如图6-3所示。
在无向图的邻接表中顶点vi的度就是第i个链表中结点的个数。在有向图中，第i个链表的结点数仅是vi的出度，求vi的入度，必须查遍n个链表才能得出。
1 3 2 ∧ 1 3 4 4 3 2 ∧ 3 2 2 ∧ 1 ∧ 1 ∧ 2 3 ∧ ∧ 3 (a) G1的邻接表
2 3 4 (b) G2的邻接表 图6-3 邻接表
【例6-2】 图G＝(V，E)，其中V={1,2,3,4,5,6}，Ｅ＝{<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>,
<3,6>,<4,6>,<5,6>}，请画出图G，并写出其邻接矩阵和邻接表表示。
解：图G如图6-4中的(a)所示，图G的邻接矩阵和邻接表表示分别如图(b)和(c)所示。 对于这类问题，只要掌握了图的概念和存储结构就可以做出正确的答案。通常情况下．对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵和邻接表表示时，只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不相同；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不相同。
0 1 1 1 0 0
1 0 0 0 0 1 0 0 1 0 0 1 1 2 4 0 0 0 0 0 1 3 0 0 0 0 1 1
0 0 0 0 0 0 6 5
(a) (b)
1 3 2 4 ∧ 2 5 ∧ 5 2 3 6 ∧ 4 6 ∧ 6 ∧ 5 6 ∧ (c)
图6-4 图及其存储结构