遍历的算法

① 二叉树遍历算法

执行完InOrder(b->lchiled)不是有cout吗‘

② 求高手给个遍历算法

图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一顶点仅被访问一次。这一过程叫做图的遍历。
遍历图的基本方法有两种：深度优先搜索和广度优先搜索。这两种方法都适用于有向图和无向图。
和树的遍历类似，图的遍历也是从某个顶点出发，沿着，某条边搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任意顶点出发顺着边可以访问到该图中所有的顶点，然而，图的遍历比树的遍历复杂得多，这是因为图中的任一点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个布尔向量visited[1..n],它的初值为false，一旦访问了顶点vi，便将visited[i]置为ture。

一、连通图的深度优先搜索
连通图深度优先搜索的基本思想如下：假定图中某个顶点v1为出发点，首先访问出发点v1，然后任选一个v1的访问过的邻接点v2，以v2为新的出发点继续进行深度优先搜索，直至图中所有顶点被访问过。
显然，图的深度优先搜索是一个递归过程，类似于树的前序遍历，它的特点是尽可能先对纵深方向进行搜索，故称之深度优先搜索。
现以图5-10中G为例说明深度优搜索过程。假定v1是出发点，首先访问v1。因v1有两个邻接点v2、v3均未被访问，选择v2作为新的出发点。访问v2之后，再找v2的未访问过的邻接点。同v2邻接的有v1、v4、v5，其中v1以被访问过，而v4、v5未被访问。选择v4作为新的出发点。重复上述搜索过程继续依次访问v8、v5。访问v5之后，由于与v5相邻的顶点均以被访问，搜索退回到v8。由于v8、v4、v2都没有未被访问的邻接点，所以搜索过程连续地从v8退回到v4，再退回到v2最后退回到v1这时选择v1的未被访问过的邻接点v3，继续往下搜索，依次访问v3、v6、v7，从而遍历了图中全部顶点。在这个过程中得到的顶点的访问序列：

(a)无向图G

(b)G的深度优先搜索过程
图5-10a 深度优先搜索过程示例

v1→v2→v4→v8→v5→v3→v6→v7
这样的序列就称之为图的深度优先搜索遍历序列。
连通图的深度优先搜索的非形式算法如下:
procere dfs (g:graph;v1:integer);
//从v1出发深度优先遍历图g//
begin write(v1);
visited[v1]:=ture;
找出g中v1的第一邻接点w;
while w存在do
[ if w 未被访问 then dfs(g,w);
w:=g中v1的下一邻接点]
end;
上述非行式算法未涉及图的存储结构.图的遍历过程必然地包含对图中每个顶点查找其邻接点这一操作;而在图的不同存储结构上查找邻接点的方法是不同的.
若以邻接表为存储结构,查找邻接点操作实际上是顺序查找链表.邻接表上的深度优先算法如下:
procere dfs(g:adj_list;v1:integer);
//从v1出发深度优先遍历图g.g以邻接表为存储结构//
begin write(v1);
visited[v1]:=ture;//标志v1已访问//
p=g[v1].link;//找v1的第一个邻接点//
while p<>nil do
[ if not (visited[p↑.adjvex]);//书错写成vertex//
then dfs(g,p↑.adjvex);
p:=p↑.next]//回溯----找v1的下一个邻接点//
end;

二、连通图的广度优先搜索
连通图广度优先搜索的基本思想是：从图中某个顶点v1出发，访问了v1之后依次访问v1的所有邻接点；然后分别从这些邻接点出发按深度优先搜索遍历图的其它顶点，直至所有顶点都被访问到。它类似于树的按层次遍历，其特点是尽可能优先对横向搜索，故称之为广度优先搜索。
下面以图5-10中G为例说明广度优先搜索的过程。首先从起点v1出发，访问v1。v1有两个未曾访问的邻接点v2和v3。先访问v2，再访问v3。然后再先后访问v2的未曾访问过的邻接点v4、v5及v3的未曾访问过的邻接点v6、v7。最后访问v4的未曾访问过的邻接点v8。至此图中所有顶点均以被访问到。得到的顶点访问序列为：

(a)无向图G

(b)G的广度优先搜索过程
图5-10b 广度优先搜索过程示例

v1→v2→v3→v4→v5→v6→v7→v8
相应的，这样的序列就称之为图的广度优先搜索遍历序列。
在广度优先搜索中，若对x的访问先于y，则对x邻接点的访问也先于队y的邻接点的访问。因此，可采用队列来暂存那些刚访问过，但可能还有为访问过的邻接点的顶点。
连通图的广度优先搜索算法如下：
procere bfs(g:adj_list;v1:integer);//书错写成adjlist//
//以邻接表为存储结构的广度优先搜索。Q为队列，假定visited的各分量已只置 为false//
begin init_linkedque(Q);//设计一个空队Q//
visited[v1]:=ture;write(v1);
in_limkedque(Q,v1); //v1入队//
while not empty(Q) do
[ v:=out_linkedque(Q);
p:=adj_list[v].link;//书错写成adjlist//
while p<>nil do
[ if visited[p↑.adjvex]:=false;//书错写成vertex//
then
[visited[p↑.adjvex]:=ture;
with(p↑.adjvex);
in_linkedque(Q,p↑.adjvex);]
p:=p↑.next]]
end;

三、图的连通分量计算
如果要遍历一个非连通图，则需要多次调用dfs或bfs，每一次都要得到一个连通分量；调用dfs或bfs的次数就是连通分量的个数。因此很容易写出非连通图的遍历算法和计算一个图的连通分量得算法。下面给出的是以邻接表为存储结构，通过调用深度优先搜索算法实现的计算连通分量的算法。
procee conn_component (var g:graph;
var visited:array[1..vnum);
begin for v:=1 to vnum do
visited[v]:flase;
count:=0;
for v:=1 to vnum do
if not(visited[v])then
[count:=count+1;
write('component',count,':');
dfs(g,v);writeln;]
end;
对于图5-5中非连通图G3，用上述算法可求出3个连通分量，各连通分量所含顶点如下：
component1: 1 2 3
component2: 4 5 6 7
component3: 8 9
注意，若从上述算法中删去有关连通分量计数器的操作，就得到一个非连通图德遍历算法。

详细资料和图片请参看参考资料，那里的比较详细

③ 遍历的基本算法有几种

对二叉树树有前序遍历，中序遍历，后序遍历，分层遍历。
对图有深度优先遍历和广度优先遍历。

④ 二叉树的遍历算法

#include<iostream>#include<string>using namespace std;struct BiNode { char data; BiNode *lchild, *rchild;};class BiTree{public: BiTree( ); ~BiTree(void); BiNode* Getroot(); void PreOrder(BiNode *root); void InOrder(BiNode *root); void PostOrder(BiNode *root); private: BiNode *root; BiNode *Creat( ); void Release(BiNode *root); };BiTree::BiTree( ){ this->root = Creat( );}BiTree::~BiTree(void){ Release(root);}BiNode* BiTree::Getroot( ){ return root;}void BiTree::PreOrder(BiNode *root){ if(root==NULL) return; else{ cout<<root->data<<" "; PreOrder(root->lchild); PreOrder(root->rchild); }}void BiTree::InOrder (BiNode *root){ if (root==NULL) return; else{ InOrder(root->lchild); cout<<root->data<<" "; InOrder(root->rchild); }}void BiTree::PostOrder(BiNode *root){ if (root==NULL) return; else{ PostOrder(root->lchild); PostOrder(root->rchild); cout<<root->data<<" "; }}
BiNode* BiTree::Creat( ){ BiNode* root; char ch; cin>>ch; if (ch=='0') root = NULL; else{ root = new BiNode; root->data=ch; root->lchild = Creat( ); root->rchild = Creat( ); } return root;}void BiTree::Release(BiNode* root){ if (root != NULL){ Release(root->lchild); Release(root->rchild); delete root; } }int main(){ BiTree bt; BiNode* root = bt.Getroot( ); bt.PreOrder(root); cout<<endl; bt.InOrder(root); cout<<endl; bt.PostOrder(root); cout<<endl; return 0;}

⑤ c++二叉树的几种遍历算法

遍历二叉树的所有结点且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历（除此之外还有层次遍历，但不常用，此处不做解释）。

1.前序遍历：根节点->左子树->右子树（根节点在前面）。

2.中序遍历：左子树->根节点->右子树（根节点在中间）。

3.后序遍历：左子树->右子树->根节点（根节点在后边）。

例如：求下面树的三种遍历：

前序遍历：abdefgc；

中序遍历：debgfac；

后序遍历：edgfbca。

⑥ 图遍历的算法

图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。 深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //访问标志数组初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G
visited[v]=TRUE; VisitFunc(v); //访问第v个顶点
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
//若w是v的最后一个邻接点，则返回空（0）。
if(!visited[w])
DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS
} 图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空辅助队列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入队列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //队头元素出队并置为u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w为u的尚未访问的邻接顶点
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}

⑦ 什么叫遍历算法(最好有例子)

遍历算法：所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。当然遍历的概念也适合于多元素集合的情况，如数组。

遍历算法概念延伸：

图遍历：图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。

举例：

遍历二叉树搜索路线：

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：⑴访问结点本身（N），⑵遍历该结点的左子树（L），⑶遍历该结点的右子树（R）。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三种次序与后三种次序对称。

遍历二叉树的执行踪迹三种递归遍历算法的搜索路线相同（如下图虚线所示）。具体线路为：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。

⑧ 遍历算法

题目不够详细。
树的遍历？书上有啊。我这儿没有。

⑨ 二叉树遍历的算法

void PreOrder(BiTree t) { /* 二叉树的先序遍历算法 */
if(t!=NULL) {
putchar (t->data);
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}

void InOrder(BiTree t) { /* 二叉树的先中序遍历算法 */
if(t != NULL) {
InOrder(t->lchild);
putchar(t->data);
InOrder(t->rchild);
}
}

void PostOrder(BiTree t) { /* 二叉树的后序遍历算法 */
if(t != NULL) {
PostOrder(t->lchild);
PostOrder(t->rchild);
putchar(t->data);
}
}