Chapter二叉樹(shù)的遍歷

會(huì)計(jì)學(xué)1Chapter二叉樹(shù)的遍歷28.6二叉樹(shù)遍歷

8.6.1遍歷二叉樹(shù)的定義

二叉樹(shù)遍歷是指按照某種順序訪問(wèn)二叉樹(shù)中的每個(gè)節(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)被訪問(wèn)一次，且只被訪問(wèn)一次?！霸L問(wèn)”的含義：是指對(duì)節(jié)點(diǎn)施行某種操作，操作可以是輸出節(jié)點(diǎn)信息，修改節(jié)點(diǎn)的數(shù)據(jù)值等，但要求這種訪問(wèn)不破壞它原來(lái)的數(shù)據(jù)結(jié)構(gòu)。以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。第1頁(yè)/共61頁(yè)3例假設(shè)一棵二叉樹(shù)存儲(chǔ)著有關(guān)人事方面的信息，每個(gè)節(jié)點(diǎn)含有姓名、工資等信息。管理和使用這些信息時(shí)可能需要作這樣一些工作：（1）將每個(gè)人的工資提高20%；（2）打印每個(gè)人的姓名和工資；（3）求最低工資數(shù)額和領(lǐng)取最低工資的人數(shù)。對(duì)于（1），訪問(wèn)是對(duì)工資值進(jìn)行修改的操作；對(duì)于（2），訪問(wèn)的含義是打印該節(jié)點(diǎn)的信息；對(duì)于（3），訪問(wèn)只是檢查和統(tǒng)計(jì)。不管訪問(wèn)的具體操作是什么，都必須做到既無(wú)重復(fù)，又無(wú)遺漏。第2頁(yè)/共61頁(yè)4線性結(jié)構(gòu)的遍歷非線性結(jié)構(gòu)的遍歷只要按照結(jié)構(gòu)原有的線性順序，從第一個(gè)元素起依次訪問(wèn)各元素即可。每個(gè)節(jié)點(diǎn)可能有一個(gè)以上的直接后繼；必須規(guī)定遍歷的規(guī)則，并按此規(guī)則遍歷二叉樹(shù)；最后得到二叉樹(shù)所有節(jié)點(diǎn)的一個(gè)線性序列。線性結(jié)構(gòu)與非線性結(jié)構(gòu)遍歷的區(qū)別第3頁(yè)/共61頁(yè)58.6.2遍歷二叉樹(shù)的方式

深度優(yōu)先遍歷：是盡可能地沿分支節(jié)點(diǎn)向深度方向進(jìn)行周游。節(jié)點(diǎn)既可以在向下遍歷之前訪問(wèn)，也可以在從子樹(shù)返回之前訪問(wèn)。

廣度優(yōu)先遍歷：是按照從上到下、從左到右的順序進(jìn)行層次訪問(wèn)節(jié)點(diǎn)。ABEHJDLIKCGFM第4頁(yè)/共61頁(yè)6深度優(yōu)先遍歷1、一棵二叉樹(shù)由三部分組成：根節(jié)點(diǎn)（V）；左子樹(shù)（L）；右子樹(shù)（R）。VLR2、若規(guī)定：L：遍歷根節(jié)點(diǎn)的左子樹(shù);R：遍歷根節(jié)點(diǎn)的右子樹(shù)；V：訪問(wèn)根節(jié)點(diǎn)。則遍歷二叉樹(shù)有6種方式：

VLRLVRLRVVRLRVLRLV若規(guī)定按先左子樹(shù)后右子樹(shù)的順序進(jìn)行遍歷，則有：VLR：前序遍歷（先根遍歷）LVR：中序遍歷（中根遍歷）LRV：后序遍歷（后根遍歷）演示8-1第5頁(yè)/共61頁(yè)7

8.6.3前序遍歷1、前序遍歷的遞歸定義若二叉樹(shù)為空，遍歷結(jié)束；否則（1）訪問(wèn)根節(jié)點(diǎn)；（V）（2）前序遍歷根節(jié)點(diǎn)的左子樹(shù)；（L）（3）前序遍歷根節(jié)點(diǎn)的右子樹(shù)。（R）ABDEFCHIG前序遍歷的序列：ABDGHCEIF演示8-2前序序列的第一個(gè)元素必為二叉樹(shù)的根節(jié)點(diǎn)第6頁(yè)/共61頁(yè)82、前序遍歷的遞歸算法template<classT>voidPreOrder(BinaryTreeNode<T>*t){if(t!=NULL){Visit(t);

PreOrder(t->LeftChild);

PreOrder(t->RightChild);}}第7頁(yè)/共61頁(yè)9

8.6.4中序遍歷1、中序遍歷的遞歸定義若二叉樹(shù)為空，遍歷結(jié)束；否則：（1）中序遍歷根節(jié)點(diǎn)的左子樹(shù)；（L）（2）訪問(wèn)根節(jié)點(diǎn)；（V）（3）中序遍歷根節(jié)點(diǎn)的右子樹(shù)。（R）ABDEFCHIG中序遍歷的序列：GDHBAEICF演示8-3中序序列的根節(jié)點(diǎn)恰為左右子樹(shù)的中序序列的分界點(diǎn)第8頁(yè)/共61頁(yè)102、中序遍歷的遞歸算法template<classT>voidInOrder(BinaryTreeNode<T>*t){if(t!=NULL){

InOrder(t->LeftChild); Visit(t);

InOrder(t->RightChild);}}第9頁(yè)/共61頁(yè)11

8.6.5后序遍歷1、后序遍歷的遞歸定義若二叉樹(shù)為空，遍歷結(jié)束；否則：（1）后序遍歷根節(jié)點(diǎn)的左子樹(shù)；（L）（2）后序遍歷根節(jié)點(diǎn)的右子樹(shù)。（R）（3）訪問(wèn)根節(jié)點(diǎn)；（V）ABDEFCHIG后序遍歷的序列：GHDBIEFCA演示8-4后序序列的最后一個(gè)元素必為二叉樹(shù)的根節(jié)點(diǎn)第10頁(yè)/共61頁(yè)123、后序遍歷的遞歸算法template<classT>voidPostOrder(BinaryTreeNode<T>*t){if(t!=NULL){

PostOrder(t->LeftChild);

PostOrder(t->RightChild); Visit(t); }}第11頁(yè)/共61頁(yè)13

8.6.6遍歷表達(dá)式二叉樹(shù)1、可以把任意一個(gè)算術(shù)表達(dá)式用一棵二叉樹(shù)表示表達(dá)式的形式：根節(jié)點(diǎn)為操作符；第一操作數(shù)為左子樹(shù)；第二操作數(shù)為右子樹(shù)。例如：表達(dá)式a/(b-c)*d+e的二叉樹(shù)表示為：+*/dce-ab第12頁(yè)/共61頁(yè)142、對(duì)該二叉樹(shù)分別進(jìn)行前序、中序和后序遍歷，得到以下三種不同形式：（1）前序遍歷：+*/a-bcde（前綴表達(dá)式，波蘭式）（2）中序遍歷：a/b-c*d+e（中綴表達(dá)式）（3）后序遍歷：abc-/d*e+（后綴表達(dá)式，逆波蘭式）3、前綴表達(dá)式和后綴表達(dá)式在編譯程序中有著非常重要的作用。+*/dce-ab表達(dá)式為a/(b-c)*d+e第13頁(yè)/共61頁(yè)15例:表達(dá)式Exp=a*b+(c-d/e)*f前綴式：+*ab*-c/def中綴式：a*b+c-d/e*f后綴式：ab*cde/-f*+結(jié)論：三種表達(dá)方式VS.原始表達(dá)式（1）操作數(shù)之間的相對(duì)次序不變；（2）運(yùn)算符的相對(duì)次序不同；（3）中綴式丟失了括號(hào)信息，致使運(yùn)算的次序不確定、無(wú)意義。第14頁(yè)/共61頁(yè)16例:表達(dá)式Exp=a*b+(c-d/e)*f前綴式：+*ab*-c/def（4）前綴式的運(yùn)算規(guī)則為：連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和它們之前緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式；后綴式：ab*cde/-f*+（5）后綴式的運(yùn)算規(guī)則為：運(yùn)算符在式中的順序恰好為表達(dá)式的運(yùn)算順序；每個(gè)運(yùn)算符和它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式。演示8-5第15頁(yè)/共61頁(yè)17

后綴表達(dá)式的特點(diǎn)：后綴表達(dá)式與表達(dá)式的操作數(shù)的先后次序相同，只是運(yùn)算符的先后次序有所改變，后綴表達(dá)式的運(yùn)算符次序就是其執(zhí)行次序；后綴表達(dá)式中沒(méi)有括號(hào)（因?yàn)槔ㄌ?hào)的作用就是改變運(yùn)算次序，既然后綴表達(dá)式中已經(jīng)考慮了運(yùn)算規(guī)則，所以就不需要括號(hào)了）。如何從后綴式求值？例:表達(dá)式Exp=a*b+(c-d/e)*f，后綴式：ab*cde/-f*+第16頁(yè)/共61頁(yè)18后綴表達(dá)式的計(jì)算方法：從左自右依次掃描表達(dá)式的各單詞：（1）如果是操作數(shù)，存入棧中；（2）如果是運(yùn)算符，就取其前面的兩個(gè)操作數(shù)（從棧中彈出的兩個(gè)數(shù)）進(jìn)行運(yùn)算，中間結(jié)果同樣存入棧中，作為下一個(gè)運(yùn)算的操作數(shù)；（3）如此反復(fù)直到表達(dá)式處理完畢?！咀⒁狻康谝淮螐棗５玫降牟僮鲾?shù)為運(yùn)算符后的操作數(shù)；第二次彈棧得到的操作數(shù)為運(yùn)算符前的操作數(shù)。

ab*cde/-f*+第17頁(yè)/共61頁(yè)19例：表達(dá)式A/(B+C*D)-E的后綴式ABCD*+/E-toptopT1BAtopT2A讀入*C*D->T1讀入+B+T1->T2topT3topET3topT4讀入E讀入-T3-E->T4讀入/A/T2->T3BCDA第18頁(yè)/共61頁(yè)20

8.6.7層序遍歷：廣度優(yōu)先遍歷1、層序遍歷的定義層序遍歷是指從二叉樹(shù)的第1層（根節(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左至右的順序逐個(gè)訪問(wèn)。ABDEFCHIG層序遍歷的序列：ABCDEFGHI第19頁(yè)/共61頁(yè)212、層序遍歷的算法思想【思路】在進(jìn)行層序遍歷時(shí)，對(duì)第i層節(jié)點(diǎn)訪問(wèn)后，緊接著對(duì)第i+1層節(jié)點(diǎn)進(jìn)行訪問(wèn)，訪問(wèn)的順序是按照第i層的訪問(wèn)順序依次訪問(wèn)各節(jié)點(diǎn)的左孩子和右孩子。即：先訪問(wèn)的節(jié)點(diǎn)，其左右孩子先訪問(wèn)；后訪問(wèn)的節(jié)點(diǎn)，其左右孩子后訪問(wèn)?！O(shè)置一個(gè)隊(duì)列結(jié)構(gòu)第20頁(yè)/共61頁(yè)22層序遍歷從二叉樹(shù)的根節(jié)點(diǎn)開(kāi)始，首先將根節(jié)點(diǎn)指針入隊(duì)，然后從隊(duì)頭取出一個(gè)元素，每取出一個(gè)元素，執(zhí)行兩個(gè)操作：（1）訪問(wèn)該元素所指節(jié)點(diǎn)；（2）若該元素所指節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)非空，則將該元素所指節(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。重復(fù)以上步驟，直到隊(duì)列為空。層序遍歷的算法思想第21頁(yè)/共61頁(yè)23ABDEFCHIGABCDEFGHI層序遍歷結(jié)果：AIBCDEFGH層序遍歷的演示第22頁(yè)/共61頁(yè)24第23頁(yè)/共61頁(yè)25例：已知一棵二叉樹(shù)的前序序列和中序序列分別為ABDEGCFH和DBGEACHF，則該二叉樹(shù)的后序序列為

，層序序列為

。ABDEFCGHDGEBHFCAABCDEFGH8.6.8

由前序（后序）序列和中序序列建立二叉樹(shù)ABDEGCFHDBGEACHFBDEGDBGEEGGECFHCHFFHHF左子樹(shù)：右子樹(shù)：第24頁(yè)/共61頁(yè)26

解答：若二叉樹(shù)的任意兩個(gè)節(jié)點(diǎn)的值都不相同，則二叉樹(shù)的前序序列和中序序列可唯一確定一棵二叉樹(shù)，確定方法如下：（1）根據(jù)前序遍歷的定義：前序序列的第一個(gè)元素必為二叉樹(shù)的根節(jié)點(diǎn)；

根據(jù)中序遍歷的定義：中序序列的根節(jié)點(diǎn)恰為左右子樹(shù)的中序序列的分界點(diǎn)；根節(jié)點(diǎn)前的子序列為左子樹(shù)的中序序列；根節(jié)點(diǎn)后的子序列為右子樹(shù)的中序序列；（2）根據(jù)左子樹(shù)的中序序列的節(jié)點(diǎn)個(gè)數(shù)，在前序序列中找出左子樹(shù)的前序序列，剩下的即為右子樹(shù)的前序序列；（3）然后用相同的辦法分別找出左、右子樹(shù)的根及其左右子樹(shù)的前序序列和中序序列；（4）依此類(lèi)推，直至待構(gòu)造的二叉樹(shù)的前序序列僅剩一個(gè)字母為止。第25頁(yè)/共61頁(yè)27結(jié)論由二叉樹(shù)的前序序列和中序序列或者中序序列和后序序列可以唯一確定一棵二叉樹(shù)第26頁(yè)/共61頁(yè)28

2000年南開(kāi)大學(xué)考研題一棵非空的二叉樹(shù)的前序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿(mǎn)足：

A、所有的節(jié)點(diǎn)均無(wú)左孩子B、所有的節(jié)點(diǎn)均無(wú)右孩子

C、只有一個(gè)葉子節(jié)點(diǎn)D、是任意一棵二叉樹(shù)C課堂練習(xí)1第27頁(yè)/共61頁(yè)29

2000年西電考研題一棵二叉樹(shù)的前序、中序和后序序列分別如下，其中一部分未顯示出來(lái)，試求出空格處的內(nèi)容，并畫(huà)出該二叉樹(shù)。前序序列：

B

F

ICEH

G；中序序列：D

KFIA

EJC

；

后序序列：

K

FBHJ

G

A。ADKJBHGDIEC課堂練習(xí)2第28頁(yè)/共61頁(yè)30ABCDEFKIJHGABDFKICEHJGDBKFIAHEJCGDKIFBHJEGCA前序遍歷序列：中序遍歷序列：后序遍歷序列：第29頁(yè)/共61頁(yè)31課后作業(yè)

P252-練習(xí)4：繪制表達(dá)式的二叉樹(shù)

P259-練習(xí)9：采用數(shù)組存儲(chǔ)二叉樹(shù)，實(shí)現(xiàn)中序遍歷（提示：遞歸算法）P259-練習(xí)17：使用鏈?zhǔn)蕉褩７椒?，?lái)實(shí)現(xiàn)二叉樹(shù)的前序遍歷

（提示：非遞歸算法；在向左子樹(shù)遍歷之前，先把當(dāng)前右子樹(shù)節(jié)點(diǎn)壓入棧中，以便后面遍歷）第30頁(yè)/共61頁(yè)328.7抽象數(shù)據(jù)類(lèi)型BinaryTreeADTBinaryTree{實(shí)例元素集合；如果不空，則被劃分為根節(jié)點(diǎn)、左子樹(shù)和右子樹(shù)；每棵子樹(shù)仍是一棵二叉樹(shù)操作

Create()：創(chuàng)建一棵空二叉樹(shù)

IsEmpty()：如果二叉樹(shù)為空，returntrue；否則returnfalse；

Root(x)：取根節(jié)點(diǎn)x；操作失敗，returnfalse，否則returntrue；

MakeTree(root,left,right)：創(chuàng)建一棵二叉樹(shù)，根節(jié)點(diǎn)為root

BreakTree(root,left,right)：拆分二叉樹(shù)

PreOrder：前序遍歷

InOrder：中序遍歷

PostOrder：后序遍歷

LevelOrder：層次遍歷}第31頁(yè)/共61頁(yè)33函數(shù)指針作為函數(shù)的參數(shù)intfa(inta){returna+1;}intfb(intb){returnb+2;}intAddFunc(int(*f1)(int),int(*f2)(int),inta,intb){return(*f1)(a)+(*f2)(b);}intmain(){inta=5,b=3;a=AddFunc(fa,fb,a,b);return0;

}returnfa(a)+fb(b);第32頁(yè)/共61頁(yè)348.8類(lèi)BinaryTreetemplate<classT>classBinaryTree{public:BinaryTree(){root=0;};~BinaryTree(){};boolIsEmpty()const{return((root)?false:true);}boolRoot(T&x)const;voidMakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right);voidBreakTree(T&element,BinaryTree<T>&left,BinaryTree<T>&right);第33頁(yè)/共61頁(yè)35voidPreOrder(void(*Visit)(BinaryTreeNode<T>*u)){PreOrder(Visit,root);}voidInOrder(void(*Visit)(BinaryTreeNode<T>*u)){InOrder(Visit,root);}voidPostOrder(void(*Visit)(BinaryTreeNode<T>*u)){PostOrder(Visit,root);}voidLevelOrder(void(*Visit)(BinaryTreeNode<T>*u));private:BinaryTreeNode<T>*root;//根節(jié)點(diǎn)指針voidPreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);voidInOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);voidPostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);};第34頁(yè)/共61頁(yè)36template<classT>boolBinaryTree<T>::Root(T&x)const{if(root){x=root->data;returntrue;}elsereturnfalse;}成員函數(shù)Root（取根節(jié)點(diǎn)）第35頁(yè)/共61頁(yè)37template<classT>voidBinaryTree<T>::MakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right){//將兩顆已有子樹(shù)合并成一棵新樹(shù)！root=newBinaryTreeNode<T>(element,left.root,right.root);

//子樹(shù)已經(jīng)被合并，將其根節(jié)點(diǎn)置空！left.root=right.root=0;}成員函數(shù)MakeTree（創(chuàng)建樹(shù)）第36頁(yè)/共61頁(yè)38template<classT>voidBinaryTree<T>::BreakTree(T&element,BinaryTree<T>&left,BinaryTree<T>&right){if(!root)throwBadInput();//treeempty

//breakthetreeelement=root->data;left.root=root->LeftChild;right.root=root->RightChild;deleteroot;root=0;}成員函數(shù)BreakTree（分解樹(shù)）第37頁(yè)/共61頁(yè)39template<classT>voidBinaryTree<int>::PreOrder(

void(*Visit)(BinaryTreeNode<int>*u),BinaryTreeNode<int>*t){if(t){Visit(t); PreOrder(Visit,t->LeftChild); PreOrder(Visit,t->RightChild);}}

前序遍歷PreOrder（private成員函數(shù)）時(shí)間復(fù)雜度Θ(n)第38頁(yè)/共61頁(yè)40template<classT>voidBinaryTree<int>::InOrder(

void(*Visit)(BinaryTreeNode<int>*u),BinaryTreeNode<int>*t){if(t){InOrder(Visit,t->LeftChild);Visit(t);InOrder(Visit,t->RightChild);}}

中序遍歷InOrder（private成員函數(shù)）時(shí)間復(fù)雜度Θ(n)第39頁(yè)/共61頁(yè)41template<classT>voidBinaryTree<int>::PostOrder(

void(*Visit)(BinaryTreeNode<int>*u),BinaryTreeNode<int>*t){if(t){PostOrder(Visit,t->LeftChild);PostOrder(Visit,t->RightChild);Visit(t);}}

后序遍歷PostOrder（private成員函數(shù)）時(shí)間復(fù)雜度Θ(n)第40頁(yè)/共61頁(yè)42template<classT>voidBinaryTree<int>::LevelOrder(

void(*Visit)(BinaryTreeNode<int>*u)

){LinkedQueue<BinaryTreeNode<int>*>Q;BinaryTreeNode<int>*t;

t=root;while(t){Visit(t);if(t->LeftChild)Q.Add(t->LeftChild);if(t->RightChild)Q.Add(t->RightChild);try{Q.Delete(t);}catch(OutOfBounds){return;}}}

逐層遍歷LevelOrder（private成員函數(shù)）時(shí)間復(fù)雜度Θ(n)第41頁(yè)/共61頁(yè)43調(diào)用示例BinaryTree<int>a,x,y,z;intmain(){y.MakeTree(1,a,a);z.MakeTree(2,a,a);x.MakeTree(3,y,z);y.MakeTree(4,x,a);}1234第42頁(yè)/共61頁(yè)448.9抽象數(shù)據(jù)類(lèi)型及類(lèi)的擴(kuò)充增加二叉樹(shù)的操作：

PreOutput();//按前序方式輸出數(shù)據(jù)域

InOutput();//按中序方式輸出數(shù)據(jù)域

PostOutput();//按后序方式輸出數(shù)據(jù)域

LevelOutput();//逐層輸出數(shù)據(jù)域

Delete();//刪除一棵二叉樹(shù)，釋放其節(jié)點(diǎn)

Height();//返回樹(shù)的高度

Size();//返回樹(shù)中節(jié)點(diǎn)數(shù)第43頁(yè)/共61頁(yè)45private:staticvoidOuput(BinaryTreeNode<T>*t){cout<<t->data<<‘’;}

8.9.1輸出Outputpublic:voidPreOuput(){PreOrder(Output,root);

cout<<endl;}第44頁(yè)/共61頁(yè)46public:voidInOuput(){InOrder(Output,root);

cout<<endl;}voidPostOuput(){InOrder(Output,root);

cout<<endl;}voidLevelOuput(){LevelOrder(Output,root);

cout<<endl;}時(shí)間復(fù)雜度Θ(n)第45頁(yè)/共61頁(yè)47public：voidDelete(){PostOrder(Free,root);root=0;}

8.9.2刪除Delete通過(guò)后序遍歷在訪問(wèn)一個(gè)節(jié)點(diǎn)時(shí)，將其刪除。private：staticvoidFree(BinaryTreeNode<T>*t){deletet;}時(shí)間復(fù)雜度Θ(n)第46頁(yè)/共61頁(yè)48template<classT>intBinaryTree<T>::Height(BinaryTree<T>*t)const{if(!t)return0;inthl=Height(t->LefChild);inthr=Height(t->RightChild);if(hl>hr)return++hl;elsereturn++hr;}

8.9.3計(jì)算高度Height：類(lèi)似后序遍歷樹(shù)的高度：max{hl,hr}+1時(shí)間復(fù)雜度Θ(n)第47頁(yè)/共61頁(yè)49template<classT>intBinaryTree<T>::Size(BinaryTree<T>*t)const{if(!t)return0;intsl=Size(t->LefChild);intsr=Size(t->RightChild);return(1+sl+sr);}

8.9.4統(tǒng)計(jì)節(jié)點(diǎn)數(shù)Size：類(lèi)似后序遍歷時(shí)間復(fù)雜度Θ(n)第48頁(yè)/共61頁(yè)50int_count=0;//類(lèi)外定義private:staticvoidAdd1(BinaryTreeNode<T>*t){_count++;}統(tǒng)計(jì)節(jié)點(diǎn)數(shù)另一種方法：在過(guò)程中完成第49頁(yè)/共61頁(yè)51public:intSize(){_count=0;PreOrder(Add1,root);return_count;}將統(tǒng)計(jì)函數(shù)作為函數(shù)參數(shù)傳入第50頁(yè)/共61頁(yè)52類(lèi)BinaryTree：調(diào)用示例#include<iostream.h>#include"binary.h"http://globalsintcount=0;BinaryTree<int>a,x,y,z;template<classT>voidct(BinaryTreeNode<T>*t){count++;}第51頁(yè)/共61頁(yè)53intmain(){y.MakeTree(1,a,a);z.MakeTree(2,a,a);x.MakeTree(3,y,z);y.MakeTree(4,x,a);cout<<"Preordersequenceis";y.PreOutput();cout<<"Inordersequenceis";y.InOutput();cout<<"Postordersequenceis";y.PostOutput();cout<<"Levelordersequenceis";y.LevelOutput();cout<<"Numberofnodes=";cout<<y.Size()<<endl;cout<<"Height=";cout<<y.Height()<<endl;y.PreOrder(ct);cout<<"Countofnodesis"<<count<<endl;return0;}Preordersequenceis4312Inordersequenceis1324Postordersequenceis1234Levelordersequenceis4312Numberofnodes=4Height=3Countofnodesis41234第52頁(yè)/共61頁(yè)54二叉樹(shù)遍歷的非遞歸算法

遞歸算法轉(zhuǎn)換為等價(jià)的非遞歸算法，使用“?！?/p>

以前序?yàn)槔焊?左-右，左下降abcde思考：如果能在左下降的過(guò)程中，記錄留待以后訪問(wèn)的右子樹(shù)的根結(jié)點(diǎn)，以便在遍歷完一個(gè)結(jié)點(diǎn)的左子樹(shù)后能轉(zhuǎn)移到這個(gè)結(jié)點(diǎn)的右子樹(shù)，即可實(shí)現(xiàn)！第53頁(yè)/共61頁(yè)55非遞歸前序遍歷二叉樹(shù)主要思想：每遇到一個(gè)結(jié)點(diǎn)，先訪問(wèn)該結(jié)點(diǎn)，并把該結(jié)點(diǎn)的非空右子結(jié)點(diǎn)壓入棧中，然后遍歷其左子樹(shù)；當(dāng)左子樹(shù)為空時(shí)，從棧頂彈出待訪問(wèn)的結(jié)點(diǎn)，繼續(xù)遍歷。abcde訪問(wèn)a進(jìn)棧c左進(jìn)b訪問(wèn)b進(jìn)棧d左進(jìn)空退棧d訪問(wèn)d左進(jìn)空退棧c訪問(wèn)c左進(jìn)e訪問(wèn)e左進(jìn)空退棧cdcc結(jié)束第54頁(yè)/共61頁(yè)56算法描述voidPreOrder(BinTreeT){stackS;InitStack(&S);//遞歸工作棧

BinTreeNode*p=T;

Push(&S,NULL);while(p!=NULL){cout<<p->data<<endl;if