top=0;
while ((t!=null || top!=0)
{ while (t!=null) { s[++top]=t; t=t->lchild }
if (top!=0) { t=s[top--]; visit(*t); t=t->rchild; } } 算法结束
void postorder (bitree *t); (后序非递归遍历) {typedef struct node { bitree *t; tag:0..1 } stack; stack s[n+1] ; top=0;
while (t || top)
{ while (t) { s[++top].t=t; s[top].tag=0; t=t->lchild; } while (top && s[top].tag==1) { printf(s[top--].t->data:3);} if (top) { s[top].tag=1; t=s[top].t->rchild ;} }
} 算法结束 6.13
bitree *dissect(bitree **t,ElemType x)
二叉树t至多有一个结点的数据域为x，本算法拆去以x为根的子树 拆开后的第一棵树用t表示，成功拆开后返回第二棵二叉树 {bitree *p,*find; if (*t!=null)
{ if ((*t)->data==x) 根结点数据域为x {p=*t; *t=null; return(p); }
else {find=(dissect(&(*t)->lchild),x); 在左子树中查找并拆开 若在左子树中未找到，就到右子树中查找并拆开 if (!find) find=(dissect(&(*t)->rchild),x); return(find); } }
else return(null); 空二叉树 } 算法结束 6.14
int search(bitree t,ElemType x)
设二叉树t中，值为x的结点至多一个，本算法打印x的所有祖先 算法思想是，借助后序非递归遍历，用栈装遍历过程的结点，当查到 值为x的结点时，栈中元素都是x的祖先 { typedef struct { bitree p; int tag; }snode;
16 snode s[]; int top=0;
while (t && t->data !=x || top)
{ while (t && t->data !=x) 沿左分支向下 { s[++top].p=t; s[top].tag=0; t=t->lchild; } if (t->data==x)
{for (i=1;i<=top;++i) printf(“%c\\n”,s[i].p->data); 输出，设元素为字符
return(1); } else
while (top>0 && s[top].tag==1) top--;退出右子树已访问的结点
if (top>0) 置访问标志1，访问右子树 {s[top].tag=1;t=s[top].p; t=t->rchild; }
}
return(0); 没有值为x的结点 } 算法结束
6.15 中序序列BDCEAFHG 后序序列DECBHGFA A
B F
C G
D
E H
前序序列 ABCDEFGH 6.16 后序线索树： A
B C D E F E null
17 H
只有空指针处才能加线索。 线索链表： 0 A 0
0 C 0 0 B 1 1 0 0 1 E 1 0 F 1 ^ 1 G 1 1 H 1 6.17
bitree *search(bitree *p)
查找前序线索二叉树上给定结点p的前序后继
{ if (p->ltag==1) return(p->rchild)； 左标记为1时，若p的右子树非空，p的右子树的根p->rchild为p的后继；若右子树为空，p->rchild指向后继
else return(p->lchild); 左标记为0时，p的左子女p->lchild为p的后继 . } 算法结束
6.18 bitree *search（b：tree *p）
在后序线索二叉树中查找给定结点的后序前驱的算法
{ if(p->rtag==0) return(p->rchild); p有右子女时，其右子女p->rchild是p的后序前驱 else return(p->lchild);
p的左标记为0，左子女p->lchild是后序前驱, 否则，线索p->lchild指向p的后序前驱 } 6.19
A
G
B
L
H
C
M I
D
N
P
J E 18 Q F K
前序序列：ABCDEFGHIJKLMPQRNO 后序序列：BDEFCAIJKHGQRPMNOL 6.21
6.22
7,19,2,6,32,3,21,10其对应字母分别为a,b,c,e,f,g,,i<>j. { visited[1..n]=0;found=0; scanf (&i,&j); dfs (i);
if (found) printf （” 顶点”,i,”和顶点 ”,j,”有路径 ”）；
else printf （” 顶点”,i,”和顶点 ”,j,”无路径 ”）； } void connect_DFS (2)宽度优先遍历
全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。 void bfs(vtxptr x)
{ initqueue(q);enqueue(q,x); while (!empty(q));
{ y=delqueue(q); if (y= =j)
{ found=1;exit(0);}有通路，退出 else {p=g[x].firstarc;第一邻接点 while (p!=null) {k=p->adjvex;
if (! Visted[k]) enqueue(q,k); p=p->nextarc }
} if(y= =j)
}while(!empty(q))
7．5。假定该有向图以邻接表存储，各顶点的邻接点按增序排列
19 O R
DFS序列：V1,V3,V6,V7,V4,V2,V5,V8 BFS序列：V1,V3,V4,V6,V7,V2,V5,V8
DFS森林 BFS森林 V1 V2 V1 V2 V3 V4 V3 V4 V5 V5 V6 V7 V6 V8 V8 V7
7．6简单回路指起点和终点相同的简单路径。算法基本思想是利用图的遍历，以顶点VK开始，若遍历中再通到VK，则存在简单回路，否则不存在简单回路。 Adjlisttp g ; visited[1..n]=0; Int found =0;全程变量 Int dfs(btxptr x)
从k顶点深度优先遍历图g，看是否存在k的简单回路 { visited[x]=1; p=g[x].firstarc; while(p!=null) { w=p->adjvex; if(w= =k)
{ found=1;exit(0);}有简单回路，退出 if (!visited[k] ) dfs(w ); p=p->nextarc; }while(p!=null) } dfs
7．7 （1）PRIM算法的最小生成树
b b b b e 2 2
2 a a d a 1 c c 2 2 d a d 2 b 2 a 2 2 d 1 c e b 2 2 2 d 1 c 20 b e 2 2 e g 1 a 1 2 d 1 1 a 1 1 a h f