基本介紹
- 中文名：遍歷
- 外文名：Traversal
- 釋義：指沿著某條搜尋路線
- 出處：《戰國策》
古漢語詞語,基本意義,詳細釋義,示例,辨析,樹的遍歷,方法,程式代碼,編號性質,二叉樹,方案,命名,中序,先序,後序,中序算法,序列,注意,圖,深度優先,廣度優先,
古漢語詞語
基本意義
遍：全面，到處；如遍布、遍及、遍野、普遍。
歷：行、遊歷、週遊
伏軾撙銜，橫歷天下。——《戰國策》
歷聘（遊歷天下以求聘用）；歷國（遊歷各國）；歷行（遍行，走遍）；歷塊（穿過一國如過一小塊土地）；歷說（遊說）
詳細釋義
遍歷就是全部走遍，到處週遊的意思；
示例
遍歷名山，博採方術。——前蜀· 杜光庭《李筌》
宋 陸游 《舟中曉賦》詩：“高檣健席從今始，遍歷三湘與五湖。”
清 戴名世 《自序》：“自燕逾濟 ，游於渤海之濱，遍歷齊魯之境。”
釋玄奘，陳留人。貞觀三年出關西行，遍歷諸國；
（鄭和）自蘇州劉家河泛海至福建，復自福建五虎門揚帆，首達占域，以次遍歷諸國"。
辨析
古文中還有一種遍歷的用法：如：乃以是履棄之於道旁，即遍歷人家捕之，若有女履者，捕之以告。
這裡的遍是全面、到處的意思；而歷，在這裡應當作逐一、逐個地的來講。
所以這裡的遍歷的意思是全部逐一的；
樹的遍歷
樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的信息的訪問，即依次對樹中每個結點訪問一次且僅訪問一次。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和後序遍歷。以這3種方式遍歷一棵樹時，若按訪問結點的先後次序將結點排列起來，就可分別得到樹中所有結點的前序列表、中序列表和後序列表。相應的結點次序分別稱為結點的前序、中序和後序。
方法
樹的這3種遍歷方式可遞歸地定義如下：
如果T是一棵單結點樹，那么對T進行前序遍歷、中序遍歷和後序遍歷根，樹根的子樹從左到右依次為T1,T2,..,Tk，那么有：
對T進行前序遍歷是先訪問樹根n，然後依次前序遍歷T1,T2,..,Tk。
對T進行中序遍歷是先中序遍歷T1，然後訪問樹根n，接著依次對T2,T2,..,Tk進行中序遍歷。
對T進行後序遍歷是先依次對T1,T2,..,Tk進行後序遍歷，最後訪問樹根n。
n
/ | \
/|\
/ | \
/ ... | ... \
T1T2T3
程式代碼
前序遍歷和中序遍歷可形式地依次描述如下 ：
三種遍歷可以形式地描述如下，其中用到了樹的ADT操作：
Procedure Preorder_Traversal(v:NodeType); {前序遍歷算法}
begin
Visite(v); {訪問節點v}
i:=Leftmost_Child(v);
while i<>；∧ do
begin
Preorder_Traversal(i);{從左到右依次訪問v的每一個兒子節點i}
i:=Right_Sibling(i);
end;
end;
Procedure Inorder_Traversal(v:NodeType); {中序遍歷算法}
begin
if Leftmost_Child(v)=∧ {判斷v是否是葉節點}
then Visite(v)
else
begin
Inorder_Traversal(Leftmost_Child(v)); {中序遍歷v的左邊第一個兒子節點}
Visite(v); {訪問節點v}
i:=Right_Sibling(Leftmost_Child(v)); {i=v的左邊第二個兒子}
while i<>；∧ do
begin
Inorder_Traversal(i);
{從左邊第二個開始到最右邊一個為止依次訪問v的每一個兒子節點i}
i:=Right_Sibling(i);
end;
end;
end;
Procedure Postorder_Traversal(v:NodeType); {後序遍歷算法}
begin
i:=Leftmost_Child(v);
while i<>；∧ do
begin
Preorder_Traversal(i);{從左到右依次訪問v的每一個兒子節點i}
i:=Right_Sibling(i);
end;
Visite(v); {訪問節點v}
end;
為了將一棵樹中所有結點按某種次序列表，只須對樹根調用相應過程。例如對圖7中的樹進行前序遍歷、中序遍歷和後序遍歷將分別得到前序列表：A B E F I J C D G H；中序列表：E B I F J A CG D H；後序列表：E I J F B G H D C A。
下面介紹一種方法可以產生上述3種遍歷方式的結點列表。構想我們從樹根出發，依逆時針方向沿樹的外緣繞行（例如圍繞圖7中的樹繞行的路線如圖8所示）。繞行途中可能多次經過同一結點。如果我們按第一次經過的時間次序將各個結點列表，就可以得到前序列表；如果按最後一次經過的時間次序列表，也就是在即將離開某一結點走向其父親時將該結點列出，就得到後序列表。為了產生中序列表，要將葉結點與內部結點加以區別。葉結點在第一次經過時列出，而內部結點在第二次經過時列出。
在上述3種不同次序的列表方式中，各樹葉之間的相對次序是相同的，它們都按樹葉之間從左到右的次序排列。3種列表方式的差別僅在於內部結點之間以及內部結點與樹葉之間的次序有所不同。
一棵樹進行前序列表或後序列表有助於查詢結點間的祖先子孫關係。假設結點v在後序列表中的序號（整數）為postorder(v），我們稱這個整數為結點v的後序編號。例如在圖7中，結點E，I和J的後序編號分別為1，2和3。
編號性質
結點的後序編號具有這樣的特點：設結點v的真子孫個數為desc(v），那么在以v為根的子樹中的所有結點的後序編號恰好落在postorder(v)- desc(v）與postorder(v）之間。因此為了檢驗結點x是否為結點y的子孫，我們只要判斷它們的後序編號是否滿足：
postorder(y)-desc(y）≤postorder(x）≤postorder(y)
前序編號也具有類似的性質。
二叉樹
方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。
因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（N），
⑵遍歷該結點的左子樹（L），
⑶遍歷該結點的右子樹（R）。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。
命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱（先序遍歷））
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中（間）。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。
遍歷算法
中序
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵訪問根結點；
⑶遍歷右子樹。
先序
若二叉樹非空，則依次執行如下操作：
⑴ 訪問根結點；
⑵ 遍歷左子樹；
⑶ 遍歷右子樹。
後序
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵遍歷右子樹；
⑶訪問根結點。
中序算法
用二叉鍊表做為存儲結構，中序遍歷算法可描述為：
void InOrder(BinTree T)
{ //算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild）；
③ printf("%c"，T->data）； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
序列
1．遍歷二叉樹的執行蹤跡
三種遞歸遍歷算法的搜尋路線相同（如下圖虛線所示）。
具體線路為：
從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
2．遍歷序列
⑴ 中序序列
中序遍歷二叉樹時，對結點的訪問次序為中序序列
【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為：
D B A E C F
⑵ 先序序列
先序遍歷二叉樹時，對結點的訪問次序為先序序列
【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為：
A B D C E F
⑶ 後序序列
後序遍歷二叉樹時，對結點的訪問次序為後序序列
【例】後序遍歷上圖所示的二叉樹時，得到的後序序列為：
D B E F C A
注意
⑴ 在搜尋路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次（或第三次）經過結點時進行的，則是中序遍歷（或後序遍歷）。只要將搜尋路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
⑵ 上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前趨結點和一個後繼結點。為了區別於樹形結構中前趨（即雙親）結點和後繼（即孩子）結點的概念，對上述三種線性序列，要在某結點的前趨和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前趨結點是D，前序後繼結點是E；中序前趨結點是E，中序後繼結點是F；後序前趨結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前趨結點是A，後繼結點是E和F。
二叉鍊表的構造
1． 基本思想 基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮CE∮∮F∮∮。
2． 構造算法
假設虛結點輸入時以空格字元表示，相應的構造算法為：
void CreateBinTree (BinTree *T)
{ //構造二叉鍊表。T是指向根指針的指針，故修改*T就修改了實參（根指針）本身
char ch；
if((ch=getchar())=='') *T=NULL； //讀入空格，將相應指針置空
else{ //讀入非空格
*T=(BinTNode *)malloc(sizeof(BinTNode））； //生成結點
（*T)->data=ch；
CreateBinTree(&(*T)->lchild）； //構造左子樹
CreateBinTree(&(*T)->rchild）； //構造右子樹
}
}
注意：調用該算法時，應將待建立的二叉鍊表的根指針的地址作為實參。
圖
深度優先
（Depth-First Traversal)
圖的深度優先遍歷的遞歸定義：
假設給定圖G的初態是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發點（源點），則深度優先遍歷可定義如下：首先訪問出發點v，並將其標記為已訪問過；然後依次從v出發搜尋v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點（亦稱為從源點可達的頂點）均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重複上述過程，直至圖中所有頂點均已被訪問為止。
圖的深度優先遍歷類似於樹的前序遍歷。採用的搜尋方法的特點是儘可能先對縱深方向進行搜尋。這種搜尋方法稱為深度優先搜尋(Depth-First Search）。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。
深度優先搜尋的過程
設x是當前被訪問頂點，在對x做過訪問標記後，選擇一條從x出發的未檢測過的邊（x，y）。若發現頂點y已訪問過，則重新選擇另一條從x出發的未檢測過的邊，否則沿邊（x，y）到達未曾訪問過的y，對y訪問並將其標記為已訪問過；然後從y開始搜尋，直到搜尋完從y出發的所有路徑，即訪問完所有從y出發可達的頂點之後，才回溯到頂點x，並且再選擇一條從x出發的未檢測過的邊。上述過程直至從x出發的所有邊都已檢測過為止。此時，若x不是源點，則回溯到在x之前被訪問過的頂點；否則圖中所有和源點有路徑相通的頂點（即從源點可達的所有頂點）都已被訪問過，若圖G是連通圖，則遍歷過程結束，否則繼續選擇一個尚未被訪問的頂點作為新源點，進行新的搜尋過程。
算法實現
plate<intmax_size>voidDigraph<max_size>::depth_first(void(*visit)(Vertex&))const/*Post:Thefunction*visithasbeenperformedateachvertexoftheDigraphindepth-firstorder.Uses:Methodtraversetoproducetherecursivedepth-firstorder.*/{boolvisited[max_size];Vertexv;for(allvinG)visited[v]=false;for(allvinG)if(!visited[v])traverse(v,visited,visit);}template<intmax_size>voidDigraph<max_size>::traverse(Vertex&v,boolvisited[],void(*visit)(Vertex&))const/*Pre:visavertexoftheDigraph.Post:Thedepth-firsttraversal,usingfunction*visit,hasbeencompletedforvandforallverticesthatcanbereachedfromv.Uses:traverserecursively.*/{Vertexw;visited[v]=true;（*visit)(v);for(allwadjacenttov)if(!visited[w])traverse(w,visited,visit);}廣度優先
（Breadth-First Traversal）
基本思想
1、從圖中某個頂點V0齣發，並訪問此頂點；
2、從V0齣發，訪問V0的各個未曾訪問的鄰接點W1，W2，…，Wk；然後，依次從W1,W2，…，Wk出發訪問各自未被訪問的鄰接點；
3、重複步驟2，直到全部頂點都被訪問為止。
廣度優先遍歷的性質
與深度優先遍歷類似，廣度優先遍歷也有許多有用的特性：
1、廣度優先生成樹
在廣度優先遍歷中，如果將每次“前進”（縱深）路過的（將被訪問的）結點和邊都記錄下來，就得到一個子圖，該子圖為以出發點為根的樹，稱為廣度優先生成樹。這種情況與深度優先遍歷類似。
類似地，也可以給廣度優先生成樹結點定義時間戳。
2、最短路徑
顯然，從v0齣發廣度優先遍歷圖，將得到v0到它的各個可達到的路徑。我們這裡定義路徑上的邊的數目為路徑長度。與深度優先遍歷不同，廣度優先遍歷得到的v0到各點的路徑是最短路徑（未考慮邊權）。
算法實現
template<intmax_size>voidDigraph<max_size>::breadth_first(void(*visit)(Vertex&))const/*Post:Thefunction*visithasbeenperformedateachvertexoftheDigraphinbreadth-firstorder.Uses:MethodsofclassQueue.*/{Queueq;boolvisited[max_size];Vertexv,w,x;for(allvinG)visited[v]=false;for(allvinG)if(!visited[v]){q.append(v);while(!q.empty()){q.retrieve(w);if(!visited[w]){visited[w]=true;(*visit)(w);for(allxadjacenttow)q.append(x);}q.serve();}}}與深度優先遍歷的比較
廣度優先遍歷與深度優先遍歷的區別在於：廣度優先遍歷是以層為順序，將某一層上的所有節點都搜尋到了之後才向下一層搜尋；而深度優先遍歷是將某一條枝椏上的所有節點都搜尋到了之後，才轉向搜尋另一條枝椏上的所有節點。
深度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出剛訪問這個結點的第一個未被訪問的鄰結點，然後再以此鄰結點為頂點，繼續找它的下一個新的頂點進行訪問，重複此步驟，直到所有結點都被訪問完為止。
廣度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出這個結點的所有未被訪問的鄰接點，訪問完後再訪問這些結點中第一個鄰接點的所有結點，重複此方法，直到所有結點都被訪問完為止。
可以看到兩種方法最大的區別在於前者從頂點的第一個鄰接點一直訪問下去再訪問頂點的第二個鄰接點；後者從頂點開始訪問該頂點的所有鄰接點再依次向下，一層一層的訪問。
