第C++超詳細實現(xiàn)二叉樹的遍歷目錄二叉樹的遍歷前序遍歷中序遍歷后序遍歷層序遍歷

二叉樹的遍歷

Q：什么是二叉樹的遍歷？

A：二叉樹的遍歷是指從根結點出發(fā)，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問一次，且僅被訪問一次。

Q：二叉樹有幾種遍歷方法？

A：二叉樹的遍歷方法可以有很多種，如果限制了從左到右的習慣方式，那么主要分為以下四種：先序遍歷，中序遍歷，后序遍歷，層序遍歷。

前序遍歷

Q：什么是先序遍歷

A：先序遍歷就是先訪問樹的根節(jié)點，再訪問樹的左子節(jié)點，再訪問右子節(jié)點?？梢韵胂鬄?，從一棵二叉樹根節(jié)點為起點，沿著二叉樹外沿，逆時針走一圈回到根節(jié)點，路上遇到的元素順序，就是先序遍歷的結果。

如圖：遍歷的順序為ABDGHCEIF

操作定義

若二叉樹為空，則空操作返回，否則：

訪問根節(jié)點先序遍歷左子樹先序遍歷右子樹

代碼演示

voidPreOrderTraversal(BiTreeBT)

if(BT！=NULL)

printf(“%d\n”,BT-Data);//對節(jié)點的數(shù)據(jù)進行打印

PreOrderTraversal(BT-Left);//訪問左子樹

PreOrderTraversal(BT-Right);//訪問右子樹

}

中序遍歷

Q：什么是中序遍歷

A：中序遍歷就是訪問完所有左子數(shù)后再訪問根節(jié)點，最后訪問右子樹，即左子樹-根節(jié)點-右子樹。中序遍歷可以看成，二叉樹每個節(jié)點，垂直方向投影下來，然后從左往右數(shù)，得出的結果便是中序遍歷的結果。

如圖：遍歷的順序為GDHBAECF

操作定義

若二叉樹為空，則空操作返回，否則：

中序遍歷左子樹訪問根節(jié)點中序遍歷右子樹

代碼演示

voidInOrderTraversal(BiTreeBT)

if(BT)

InOrderTraversal(BT-Left);

printf("%d\n",BT-Data);

InOrderTraversal(BT-Right);

}

后序遍歷

Q：什么后序遍歷

A：后序遍歷就是先訪問左子樹和右子樹，最后訪問節(jié)點，即左子樹-右子樹-根節(jié)點。后序遍歷可以看成圍著樹的外圍繞一圈，若下面只有一個結點就摘下來，得出的結果便是后序遍歷的結果。

如圖：遍歷的順序為GHDBIEFCA

操作定義

若二叉樹為空，則空操作返回，否則：

后序遍歷左子樹后序遍歷右子樹訪問根節(jié)點

代碼演示

voidPostOrderTraversal(BiTreeBT)

if(BT)

PostOrderTraversal(BT-Left);

PostOrderTraversal(BT-Right);

printf("%d\n",BT-Data);

}

層序遍歷

Q：什么層序遍歷

A：層次遍歷就是從根節(jié)點開始，一層一層，從上到下，每層從左到右，依次取值。

如圖：遍歷的順序為ABCDEFGHL

代碼演示

voidLevelOrder(BiTreeT){

InitQueue(Q);//初始化輔助隊列

BiTreep;

EnQueue(Q,T);//將根結點入隊

while(!IsEmpty(Q))

{//隊列不空則循環(huán)

DeQueue(Q,p);//隊頭結點出隊

visit(p);//訪問出隊結點

if(p-1child!=NULL)

EnQueue(Q,p-lchild);/