基本介紹
- 中文名：遍歷
- 外文名：Traversal
- 定義：指沿著某條搜尋路線
- 領域：數據結構
- 套用：二叉樹、圖
- 類型：前序、中序、後序等
樹的遍歷,簡介,命名,中序,先序,後序,中序算法,序列,注意,圖的遍歷,簡介,深度優先,廣度優先,古漢語詞語釋義,
樹的遍歷
簡介
樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的信息的訪問，即依次對樹中每個結點訪問一次且僅訪問一次。與那些基本上都有標準遍歷方式（通常是按線性順序）的線性數據結構（如鍊表、一維數組）所不同的是，樹結構有多種不同的遍歷方式。從二叉樹的根節點出發，節點的遍歷分為三個主要步驟：對當前節點進行操作（稱為“訪問”節點）、遍歷左邊子節點、遍歷右邊子節點。這三個步驟的先後順序也是不同遍歷方式的根本區別。
由於從給定的某個節點出發，有多個可以前往的下一個節點（樹不是線性數據結構），所以在順序計算（即非並行計算）的情況下，只能推遲對某些節點的訪問——即以某種方式保存起來以便稍後再訪問。常見的做法是採用棧（LIFO）或佇列（FIFO）。由於樹本身是一種自我引用（即遞歸定義）的數據結構，因此很自然也可以用遞歸方式，或者更準確地說，用corecursion，來實現延遲節點的保存。這時（採用遞歸的情況）這些節點被保存在call stack中。
樹的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），
⑵遍歷該結點的左子樹（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）； //構造右子樹
}
}
注意：調用該算法時，應將待建立的二叉鍊表的根指針的地址作為實參。
圖的遍歷
簡介
遍歷算法是計算機領域中的一個重要的研究方向，一個問題的求解就是從最開始的狀態，利用已經存在的規則和條件改變當前狀態，直到把當前狀態變為最終目的狀態，把中間出現的狀態全部連線起來，變成一條遍歷路徑的過程。通過圖的遍歷，我們可以找到這條徑。圖的遍歷算法主要有兩種，一種是按照深度優先的順序展開遍歷的算法，也就是深度優先遍歷；另一種是按照寬度優先的順序展開遍歷的算法，也就是寬度優先遍歷。寬度優先遍歷是沿著圖的深度遍歷圖的所有節點，每次遍歷都會沿著當前節點的鄰接點遍歷，直到所有點全部遍歷完成。如果當前節點的所有鄰接點都遍歷過了，則回溯到上一個節點，重複這一過程一直到已訪問從源節點可達的所有節點為止。如果還存在沒有被訪問的節點，則選擇其中一個節點作為源節點並重複以上過程，直到所有節點都被訪問為止。利用圖的深度優先搜尋可以獲得很多額外的信息，也可以解決很多圖論的問題。寬度優先遍歷又名廣度優先遍歷。通過沿著圖的寬度遍歷圖的節點，如果所有節點均被訪問，算法隨即終止。寬度優先遍歷的實現一般需要一個佇列來輔助完成。 寬度優先遍歷和深度優先遍歷一樣也是一種盲目的遍歷方法。也就是說，寬度遍歷算法並不使用經驗法則算法， 並不考慮結果的可能地址，只是徹底地遍歷整張圖，直到找到結果為止。圖的遍歷問題分為四類：
遍歷完所有的邊而不能有重複，即所謂“歐拉路徑問題”（又名一筆畫問題）；
遍歷完所有的頂點而沒有重複，即所謂“哈密頓路徑問題”。
遍歷完所有的邊而可以有重複，即所謂“中國郵遞員問題”；
遍歷完所有的頂點而可以重複，即所謂“旅行推銷員問題”。
對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。
深度優先
圖的深度優先遍歷的遞歸定義：
假設給定圖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);}廣度優先
基本思想
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();}}}與深度優先遍歷的比較
廣度優先遍歷與深度優先遍歷的區別在於：廣度優先遍歷是以層為順序，將某一層上的所有節點都搜尋到了之後才向下一層搜尋；而深度優先遍歷是將某一條枝椏上的所有節點都搜尋到了之後，才轉向搜尋另一條枝椏上的所有節點。
深度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出剛訪問這個結點的第一個未被訪問的鄰結點，然後再以此鄰結點為頂點，繼續找它的下一個新的頂點進行訪問，重複此步驟，直到所有結點都被訪問完為止。
廣度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出這個結點的所有未被訪問的鄰接點，訪問完後再訪問這些結點中第一個鄰接點的所有結點，重複此方法，直到所有結點都被訪問完為止。
可以看到兩種方法最大的區別在於前者從頂點的第一個鄰接點一直訪問下去再訪問頂點的第二個鄰接點；後者從頂點開始訪問該頂點的所有鄰接點再依次向下，一層一層的訪問。
古漢語詞語釋義
遍：全面，到處；如遍布、遍及、遍野、普遍。歷：行、遊歷、週遊伏軾撙銜，橫歷天下，出自《戰國策》。歷聘（遊歷天下以求聘用）；歷國（遊歷各國）；歷行（遍行，走遍）；歷塊（穿過一國如過一小塊土地）；歷說（遊說）。
遍歷就是全部走遍，到處週遊的意思；古文中還有一種遍歷的用法：如：乃以是履棄之於道旁，即遍歷人家捕之，若有女履者，捕之以告。這裡的遍是全面、到處的意思；而歷，在這裡應當作逐一、逐個地的來講。所以這裡的遍歷的意思是全部逐一的。
遍歷名山，博採方術。——前蜀· 杜光庭《李筌》
宋 陸游 《舟中曉賦》詩：“高檣健席從今始，遍歷三湘與五湖。”
清 戴名世 《自序》：“自燕逾濟 ，游於渤海之濱，遍歷齊魯之境。”
釋玄奘，陳留人。貞觀三年出關西行，遍歷諸國；
（鄭和）自蘇州劉家河泛海至福建，復自福建五虎門揚帆，首達占域，以次遍歷諸國"。
