《数据结构 - C语言描述》习题及答案 耿国华

（2）找结点的中序后继结点

BiTNode *InSucc (BiTNode *p)

/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/ { if (p->Rtag= =1) succ = p->RChild; /*直接利用线索*/ else

{/*在p的右子树中查找“最左下端”结点*/ for ( q=p->RChild; q->Ltag= =0; q=q->LChild); succ= q; }

return (succ); }

(3) 找结点的先序后继结点

BiTNode *PreSucc (BiTNode *p)

/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/ { if (p->Ltag= =0) succ = p->LChild; else succ= p->RChild; return (succ); }

(4) 找结点的后序前驱结点

BiTNode *SuccPre (BiTNode *p)

/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/ { if (p->Ltag= =1) pre = p->LChild; else pre= p->RChild; return (pre); }

6.21已知二叉树按照二叉链表方式存储，试利用栈的基本操作写出先序遍历非递归形式的算法。 【解答】

Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法*/ {

InitStack(&S); p=root;

while(p!=NULL || !IsEmpty(S) )

{ if(p!=NULL) {

Visit(p->data); push(&S,p); p=p->Lchild;

}

else {

Pop(&S,&p); p=p->RChild; } } }

6.24已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。 【解答】 算法(一)

Void exchange ( BiTree root ) {

p=root;

if ( p->LChild != NULL || p->RChild != NULL ) {

temp = p->LChild; p->LChild = p->RChild;

算法(二)

Void exchange ( BiTree root ) {

p=root; }

}

p->RChild = temp; exchange ( p->LChild ); exchange ( p->RChild );

if ( p->LChild != NULL || p->RChild != NULL ) {

exchange ( p->LChild ); exchange ( p->RChild );

temp = p->LChild;

p->LChild = p->RChild;

p->RChild = temp;

}

}

第七章 图

习 题

7.1

已知如图所示的有向图，请给出该图的： （1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 十字链表； （6） 强连通分量。

题1图

题2图

3 6 3 2 4 6 5 4 2 1 5 1

7.2 已知如图所示的无向图，请给出该图的：

（1） 邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点

的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。）

（2） 从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜

索树）

（3） 从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜

索树）

7.3 7.4

5 1 3 4 3 4 6 3 1 2 3 4 4 7 5 5 6 4 0 6 2 8 2 9

图7.31 题7.3 用图

已知如图7.31所示的AOE-网，试求：

（1） 每个事件的最早发生时间和最晚发生时间； （2） 每个活动的最早开始时间和最晚开始时间； （3） 给出关键路径。

7.5 7.6 7.7

15 4 10 2 2 20 6 20 10 30 4 15 5 10 3 1

图7.30 题7.4 用图