遍歷的演算法

① 二叉樹遍歷演算法

執行完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);
}
}