二叉樹遍歷

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：

⑴訪問結點本身（N），

⑵遍歷該結點的左子樹（L），

⑶遍歷該結點的右子樹（R）。

以上三種操作有六種執行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

注意：

前三種次序與后三種次序對稱，故只討論先左後右的前三種次序。

根據訪問結點操作發生位置命名：

① NLR：前序遍歷(Preorder Traversal 亦稱（先序遍歷））

——訪問根結點的操作發生在遍歷其左右子樹之前。

② LNR：中序遍歷(Inorder Traversal)

——訪問根結點的操作發生在遍歷其左右子樹之中（間）。

③ LRN：後序遍歷(Postorder Traversal)

——訪問根結點的操作發生在遍歷其左右子樹之後。

注意：

由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

1．先（根）序遍歷的遞歸演演算法定義：

若二叉樹非空，則依次執行如下操作：

⑴ 訪問根結點；

⑵ 遍歷左子樹；

⑶ 遍歷右子樹。

2．中（根）序遍歷的遞歸演演算法定義：

若二叉樹非空，則依次執行如下操作：

⑴遍歷左子樹；

⑵訪問根結點；

⑶遍歷右子樹。

3．后（根）序遍歷得遞歸演演算法定義：

若二叉樹非空，則依次執行如下操作：

⑴遍歷左子樹；

⑵遍歷右子樹；

⑶訪問根結點。

用二叉鏈表做為存儲結構，中序遍歷演演算法可描述為：

void InOrder(BinTree T)

{ //演演算法里①~⑥是為了說明執行過程加入的標號

① if(T) { // 如果二叉樹非空

② InOrder(T->lchild）；

③ printf("%c"，T->data）； // 訪問結點

④ InOrder(T->rchild);

⑤ }

⑥ } // InOrder

計算中序遍歷擁有比較簡單直觀的投影法，如圖

除了先序遍歷、中序遍歷、後序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然後從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。

在這裡，所有的二叉樹都以數組的形式儲存。

⑴在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次（或第三次）經過結點時進行的，則是中序遍歷（或後序遍歷）。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。

⑵上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前驅結點和一個後繼結點。為了區別於樹形結構中前驅（即雙親）結點和後繼（即孩子）結點的概念，對上述三種線性序列，要在某結點的前驅和後繼之前冠以其遍歷次序名稱。

【例】上圖所示的二叉樹中結點C，其前序前驅結點是D，前序後繼結點是E；中序前驅結點是E，中序後繼結點是F；後序前驅結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前驅結點是A，後繼結點是E和F。

二叉鏈表基本思想

基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。

注意：

先序序列中必須加入虛結點以示空指針的位置。

【例】

建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。

構造演演算法

假設虛結點輸入時以空格字元表示，相應的構造演演算法為：

注意：

調用該演演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。

示例

設root是一根指針（即它的類型是BinTree），則調用CreateBinTree(&root）后root就指向了已構造好的二叉鏈表的根結點。

二叉樹建立過程見

下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼（遞歸演演算法）：