3.树的周游 )树的子树顺序 无序有序 2)森林F的周游 (1)树的先根次序周游 A.若F为空，则返回 B.访问F的第一棵树的根 C.按树先根次序周游F的第一棵树的子树 D.按树先根次序周游F的其它树 (2)树的中根次序周游 (3)树的后根次序周游
3. 树的周游 1) 树的子树顺序 无序→有序 2)森林F的周游 ⑴ 树的先根次序周游 A.若F为空，则返回 B.访问F的第一棵树的根 C.按树先根次序周游F的第一棵树的子树 D.按树先根次序周游F的其它树 ⑵ 树的中根次序周游 ⑶ 树的后根次序周游
树转换成二元树方法： 设有一棵树T(它的根是T),人为安排它的子树有序且设为 T11,T12,T1K。用T1做二元树的根，T11做T1的左子树，然后 T1做T11的右子树，2≤i≤k。 人从 设T是由森林F转换成的二元树，则： T的先根次序周游相当于按树先根次序周 游访问F T1K T的中根次序周游相当于按树中根次序周 游访问F 对T的后根次序周游无类似的自然对应
树转换成二元树方法： 设有一棵树T(它的根是T1 )，人为安排它的子树有序且设为 T11,T12,…,T1K。用T1做二元树的根，T11做T1的左子树，然后 T1i做T1i-1的右子树，2≤i≤k。 T1 T11 T12 … T1K T1 T11 T12 T1K 设T是由森林F转换成的二元树,则： … T的先根次序周游相当于按树先根次序周 游访问F T的中根次序周游相当于按树中根次序周 游访问F 对T的后根次序周游无类似的自然对应
4.图的检索和周游 4.1宽度优先检索和周游 )宽度优先检索 ①从结点V开始，给V标上已到达（或访问)标记一 此时称结点V还没有被检测，而当算法访问了邻接于某结点 V的所有结点时，称该结点被检测了。 ②访问邻接于V且尚未被访问的所有结点一这些结 点是新的未被检测的结点。将这些结点依次放置到一未检 测结点表（队列Q)中（末端插入） ③ 标记v已被检测。 ④ 若未检测结点表为空，则算法终止；否则 ⑤ 从未检测结点表的表头取一结点作为下一个待检测 结点， 重复上述过程
4. 图的检索和周游 4.1 宽度优先检索和周游 1) 宽度优先检索 ① 从结点v开始，给v标上已到达（或访问）标记—— 此时称结点v还没有被检测，而当算法访问了邻接于某结点 v的所有结点时，称该结点被检测了。 ② 访问邻接于v且尚未被访问的所有结点——这些结 点是新的未被检测的结点。将这些结点依次放置到一未检 测结点表(队列Q)中（末端插入） 。 ③ 标记v已被检测。 ④ 若未检测结点表为空，则算法终止；否则 ⑤ 从未检测结点表的表头取一结点作为下一个待检测 结点， 重复上述过程
算法6.6宽度优先检索算法 procedure BFS(v) /宽度优先检索G,它从结点v开始。所有已访问结点被标记为VISITED()=1。 川 VISITED(V)←-1；u←-V VISITED(n)是一个标示数组，初始值 VISITED(0=0,1≤i≤nW 将Q初始化为空 Q是未检测结点的队列川 loop for邻接于u的所有结点wdo if VISITED(w)=0 then w未被检测W call ADDQ(W,Q) /ADDQ将w加入到队列Q的末端∥ VISITED(w)←-1 川同时标示w已被访问川 endif repeat ifQ为空then return endif call DELETEQ(u,Q) DELETEQ取出队列Q的表头，并赋给变量uM repeat end BFS
算法6.6 宽度优先检索算法 procedure BFS(v) //宽度优先检索G，它从结点v开始。所有已访问结点被标记为VISITED(i)=1。 // VISITED(v)←1;u←v //VISITED(n)是一个标示数组，初始值 VISITED(i)=0, 1≤i≤n // 将Q初始化为空 //Q是未检测结点的队列// loop for 邻接于u的所有结点w do if VISITED(w)=0 then //w未被检测// call ADDQ(w,Q) //ADDQ将w加入到队列Q的末端// VISITED(w)←1 //同时标示w已被访问// endif repeat if Q 为空 then return endif call DELETEQ(u,Q) //DELETEQ取出队列Q的表头，并赋给变量u// repeat end BFS