樹 - 二叉樹的遍歷 （一）

　　遍歷概念

　　所謂 遍歷(Traversal) 是指沿著某條搜索路線依次對樹中每個結點均做一次且僅做一次訪問訪問結點所做的操作依賴於

　　具體的應用問題

　　遍歷是二叉樹上最重要的運算之一是二叉樹上進行其它運算之基礎

　　遍歷方案

　　遍歷方案

　　從二叉樹的遞歸定義可知一棵非空的二叉樹由根結點及左右子樹這三個基本部分組成因此在任一給定結點上可以按某

　　種次序執行三個操作

　　()訪問結點本身(N)

　　()遍歷該結點的左子樹(L)

　　()遍歷該結點的右子樹(R)

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

　　NLRLNRLRNNRLRNLRLN

　　注意

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

　　三種遍歷的命名

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

　　① NLR前序遍歷(PreorderTraversal亦稱(先序遍歷))

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

　　② LNR中序遍歷(InorderTraversal)

　　——訪問結點的操作發生在遍歷其左右子樹之中(間)

　　③ LRN後序遍歷(PostorderTraversal)

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

　　注意

　　由於被訪問的結點必是某子樹的根所以N(Node)L(Left subtlee)和R(Right subtree)又可解釋為根根的左子樹和根的右子

　　樹NLRLNR和LRN分別又稱為先根遍歷中根遍歷和後根遍歷

　　遍歷算法

　　中序遍歷的遞歸算法定義

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

　　()遍歷左子樹;

　　()訪問根結點;

　　()遍歷右子樹

　　先序遍歷的遞歸算法定義

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

　　() 訪問根結點;

　　() 遍歷左子樹;

　　() 遍歷右子樹

　　後序遍歷得遞歸算法定義

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

　　()遍歷左子樹;

　　()遍歷右子樹;

　　()訪問根結點

　　中序遍歷的算法實現

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

　　void InOrder(BinTree T)

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

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

　　② InOrder(T>lchild);

　　③ printf(%cT>data); // 訪問結點

　　④ InOrder(T>rchild);

　　⑤ }

　　⑥ } // InOrder

From:http://tw.wingwit.com/Article/program/sjjg/201311/23884.html