内容发布更新时间 : 2024/12/23 11:43:37星期一 下面是文章的全部内容请认真阅读。
（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 用图