Chapter8-2二叉樹(shù)的遍歷課件

1、12022/10/10中國(guó)地質(zhì)大學(xué)信息工程學(xué)院Chapter8 二叉樹(shù)和樹(shù)12022/10/9中國(guó)地質(zhì)大學(xué)信息工程學(xué)院Chapter82內(nèi)容提要8.1 樹(shù)8.2 二叉樹(shù)8.3 二叉樹(shù)的特性8.4 二叉樹(shù)的描述8.5 二叉樹(shù)常用操作8.6 二叉樹(shù)遍歷8.7 抽象數(shù)據(jù)類型BinaryTree8.8 類BinaryTree8.9 抽象數(shù)據(jù)類型及類的擴(kuò)充8.10 應(yīng)用2內(nèi)容提要8.1 樹(shù)38.6 二叉樹(shù)遍歷 8.6.1 遍歷二叉樹(shù)的定義 二叉樹(shù)遍歷是指按照某種順序訪問(wèn)二叉樹(shù)中的每個(gè)節(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)被訪問(wèn)一次，且只被訪問(wèn)一次。 “訪問(wèn)”的含義：是指對(duì)節(jié)點(diǎn)施行某種操作，操作可以是輸出節(jié)點(diǎn)信息，修改節(jié)點(diǎn)的數(shù)

2、據(jù)值等，但要求這種訪問(wèn)不破壞它原來(lái)的數(shù)據(jù)結(jié)構(gòu)。 以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。38.6 二叉樹(shù)遍歷 8.6.1 遍歷二叉樹(shù)的定義 二叉4 例 假設(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ú)遺漏。4 例 假設(shè)一棵二叉樹(shù)存儲(chǔ)著有關(guān)人事方面的信息，每個(gè)節(jié)5線性結(jié)構(gòu)

3、的遍歷非線性結(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ū)別5線性結(jié)構(gòu)的遍歷非線性結(jié)構(gòu)的遍歷只要按照結(jié)構(gòu)原有的線性順序，6 8.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)。ABEHJDLIKCGFM6 8.6.2 遍歷二叉樹(shù)的方式 深度優(yōu)先遍歷：是盡可能地7深度優(yōu)先遍歷1、

4、一棵二叉樹(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種方式： VLR LVR LRV VRL RVL RLV 若規(guī)定按先左子樹(shù)后右子樹(shù)的順序進(jìn)行遍歷，則有：VLR：前序遍歷（先根遍歷）LVR：中序遍歷（中根遍歷） LRV：后序遍歷（后根遍歷）演示8-17深度優(yōu)先遍歷1、一棵二叉樹(shù)由三部分組成：VLR2、若規(guī)定：8 8.6.3 前序遍歷1、前序遍歷的遞歸定義若二叉樹(shù)為空，遍歷結(jié)束；否則（1）訪問(wèn)根節(jié)點(diǎn)；（V）（2）前序遍歷根節(jié)點(diǎn)的左子樹(shù)；（L）（3）前序遍歷根節(jié)點(diǎn)的右子樹(shù)。

5、（R）ABDEFCHIG前序遍歷的序列：A B D G H C E I F演示8-2前序序列的第一個(gè)元素必為二叉樹(shù)的根節(jié)點(diǎn)8 8.6.3 前序遍歷1、前序遍歷的遞歸定義若二叉樹(shù)為空92、前序遍歷的遞歸算法template void PreOrder ( BinaryTreeNode *t ) if ( t != NULL ) Visit(t); PreOrder ( t-LeftChild ); PreOrder ( t-RightChild ); 92、前序遍歷的遞歸算法template 10 8.6.4 中序遍歷1、中序遍歷的遞歸定義若二叉樹(shù)為空，遍歷結(jié)束；否則：（1）中序遍歷根節(jié)點(diǎn)的左子

6、樹(shù)；（L）（2）訪問(wèn)根節(jié)點(diǎn)；（V）（3）中序遍歷根節(jié)點(diǎn)的右子樹(shù)。（R）ABDEFCHIG中序遍歷的序列：G D H B A E I C F演示8-3中序序列的根節(jié)點(diǎn)恰為左右子樹(shù)的中序序列的分界點(diǎn)10 8.6.4 中序遍歷1、中序遍歷的遞歸定義若二叉樹(shù)為112、中序遍歷的遞歸算法template void InOrder ( BinaryTreeNode *t ) if ( t != NULL ) InOrder ( t-LeftChild ); Visit(t); InOrder ( t-RightChild ); 112、中序遍歷的遞歸算法template class T12 8.6.5 后

7、序遍歷1、后序遍歷的遞歸定義若二叉樹(shù)為空，遍歷結(jié)束；否則：（1）后序遍歷根節(jié)點(diǎn)的左子樹(shù)；（L）（2）后序遍歷根節(jié)點(diǎn)的右子樹(shù)。（R）（3）訪問(wèn)根節(jié)點(diǎn)；（V）ABDEFCHIG后序遍歷的序列：G H D B I E F C A演示 8-4后序序列的最后一個(gè)元素必為二叉樹(shù)的根節(jié)點(diǎn)12 8.6.5 后序遍歷1、后序遍歷的遞歸定義若二叉樹(shù)為133、后序遍歷的遞歸算法template void PostOrder ( BinaryTreeNode *t ) if ( t != NULL ) PostOrder ( t-LeftChild ); PostOrder ( t-RightChild ); Vis

8、it(t); 133、后序遍歷的遞歸算法template T1讀入+B+T1-T2topT3topET3topT4讀入E讀入-T3-E-T4讀入/A/T2-T3BCDA20例：表達(dá)式A/(B+C*D)-E的后綴式ABCD*+/E21 8.6.7 層序遍歷：廣度優(yōu)先遍歷1、層序遍歷的定義 層序遍歷是指從二叉樹(shù)的第1層（根節(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左至右的順序逐個(gè)訪問(wèn)。ABDEFCHIG層序遍歷的序列：A B C D E F G H I21 8.6.7 層序遍歷：廣度優(yōu)先遍歷1、層序遍歷的定義222、層序遍歷的算法思想【思路】在進(jìn)行層序遍歷時(shí)，對(duì)第i層節(jié)點(diǎn)訪問(wèn)后，緊接著對(duì)第i

9、+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)。 設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)222、層序遍歷的算法思想【思路】在進(jìn)行層序遍歷時(shí)，對(duì)第i層23 層序遍歷從二叉樹(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ì)列為空。層序遍歷的算法思想23 層序遍歷從二叉樹(shù)的根節(jié)點(diǎn)開(kāi)始，（1）訪問(wèn)該元素所指節(jié)點(diǎn)24ABDEFCHIG

10、ABCDEFGHI層序遍歷結(jié)果：AIBCDEFGH層序遍歷的演示24ABDEFCHIGABCDEFGHI層序遍歷結(jié)果：AIB252526 例：已知一棵二叉樹(shù)的前序序列和中序序列分別為ABDEGCFH和DBGEACHF，則該二叉樹(shù)的后序序列為 ，層序序列為 。ABDEFCGHDGEBHFCAABCDEFGH8.6.8 由前序（后序）序列和中序序列建立二叉樹(shù)ABDEGCFHDBGEACHFBDEGDBGEEGGECFHCHFFHHF左子樹(shù)：右子樹(shù)：26 例：已知一棵二叉樹(shù)的前序序列和中序序列分別為ABDEG27 解答：若二叉樹(shù)的任意兩個(gè)節(jié)點(diǎn)的值都不相同，則二叉樹(shù)的前序序列和中序序列可唯一確定一棵二

11、叉樹(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）依此類推，直至待構(gòu)造的二叉樹(shù)的前序序列僅剩一個(gè)字母為止。27 解答：若二叉樹(shù)的任意兩個(gè)節(jié)點(diǎn)的值都不相同，則二叉樹(shù)的28結(jié)論由二叉樹(shù)的前序序列和中序序列或者中序序列和后序序列可以唯一確定一棵

12、二叉樹(shù)28結(jié)論由二叉樹(shù)的前序序列和中序序列或者中序序列和后序序列可29 2000年南開(kāi)大學(xué)考研題 一棵非空的二叉樹(shù)的前序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足： A、所有的節(jié)點(diǎn)均無(wú)左孩子 B、所有的節(jié)點(diǎn)均無(wú)右孩子 C、只有一個(gè)葉子節(jié)點(diǎn) D、是任意一棵二叉樹(shù)C課堂練習(xí)129 2000年南開(kāi)大學(xué)考研題 一棵非空的二叉樹(shù)的30 2000年西電考研題 一棵二叉樹(shù)的前序、中序和后序序列分別如下，其中一部分未顯示出來(lái)，試求出空格處的內(nèi)容，并畫出該二叉樹(shù)。前序序列： B F ICEH G；中序序列：D KFIA EJC ； 后序序列： K FBHJ G A。ADKJBHGDIEC課堂練習(xí)230

13、2000年西電考研題 一棵二叉樹(shù)的前序、中序31ABCDEFKIJHGABDFKICEHJGDBKFIAHEJCGDKIFBHJEGCA 前序遍歷序列： 中序遍歷序列： 后序遍歷序列：31ABCDEFKIJHGABDFKICEHJGDBKFIA32課后作業(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)壓入棧中，以便后面遍歷）32課后作業(yè) P252-練習(xí)4：繪制表達(dá)式的二叉樹(shù)338.7 抽象數(shù)據(jù)類型BinaryTr

14、eeADT BinaryTree實(shí)例 元素集合；如果不空，則被劃分為根節(jié)點(diǎn)、左子樹(shù)和右子樹(shù)； 每棵子樹(shù)仍是一棵二叉樹(shù)操作 Create( )：創(chuàng)建一棵空二叉樹(shù) IsEmpty( )：如果二叉樹(shù)為空，return true；否則return false； Root(x)：取根節(jié)點(diǎn)x；操作失敗，return false，否則return true； MakeTree(root,left,right)：創(chuàng)建一棵二叉樹(shù)，根節(jié)點(diǎn)為root BreakTree(root,left,right)：拆分二叉樹(shù) PreOrder： 前序遍歷 InOrder： 中序遍歷 PostOrder： 后序遍歷 Level

15、Order： 層次遍歷338.7 抽象數(shù)據(jù)類型BinaryTreeADT Bina34函數(shù)指針作為函數(shù)的參數(shù)int fa(int a) return a+1; int fb(int b) return b+2; int AddFunc( int (*f1)(int), int (*f2)(int) , int a, int b) return (*f1)(a) + (*f2)(b); int main( ) int a=5, b=3; a= AddFunc(fa, fb, a, b); return 0; return fa(a)+fb(b);34函數(shù)指針作為函數(shù)的參數(shù)int fa(int a

16、) r358.8 類BinaryTreetemplateclass BinaryTree public: BinaryTree( ) root = 0; BinaryTree( ); bool IsEmpty( ) const return (root) ? false : true); bool Root(T& x) const; void MakeTree(const T& element, BinaryTree& left, BinaryTree& right); void BreakTree(T& element, BinaryTree& left, BinaryTree& right

17、);358.8 類BinaryTreetemplateclas36 void PreOrder (void(*Visit)(BinaryTreeNode *u) PreOrder(Visit, root); void InOrder (void(*Visit)(BinaryTreeNode *u) InOrder(Visit, root); void PostOrder (void(*Visit)(BinaryTreeNode *u) PostOrder(Visit, root); void LevelOrder (void(*Visit)(BinaryTreeNode *u);private

18、: BinaryTreeNode *root; / 根節(jié)點(diǎn)指針 void PreOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void InOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void PostOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); ; 36 void PreOrder (void(*Vi37templatebool BinaryTree:Root(T& x)

19、 const if (root) x = root-data; return true; else return false; 成員函數(shù)Root（取根節(jié)點(diǎn)）37template 成員函數(shù)Root（取38templatevoid BinaryTree:MakeTree(const T& element, BinaryTree& left, BinaryTree& right) / 將兩顆已有子樹(shù)合并成一棵新樹(shù)！ root = new BinaryTreeNode (element, left.root, right.root); /子樹(shù)已經(jīng)被合并，將其根節(jié)點(diǎn)置空！ left.root = rig

20、ht.root = 0; 成員函數(shù)MakeTree（創(chuàng)建樹(shù)）38template 成員函數(shù)MakeTr39templatevoid BinaryTree:BreakTree(T& element, BinaryTree& left, BinaryTree& right) if (!root) throw BadInput( ); / tree empty / break the tree element = root-data; left.root = root-LeftChild; right.root = root-RightChild; delete root; root = 0; 成員

21、函數(shù)BreakTree（分解樹(shù)）39template 成員函數(shù)BreakT40templatevoid BinaryTree:PreOrder( void(*Visit)(BinaryTreeNode *u), BinaryTreeNode *t) if (t) Visit(t); PreOrder(Visit, t-LeftChild); PreOrder(Visit, t-RightChild); 前序遍歷PreOrder（private成員函數(shù)）時(shí)間復(fù)雜度(n)40template 前序遍歷PreOrd41template void BinaryTree:InOrder( void(*V

22、isit)(BinaryTreeNode *u), BinaryTreeNode *t) if (t) InOrder(Visit, t-LeftChild); Visit(t); InOrder(Visit, t-RightChild); 中序遍歷InOrder（private成員函數(shù)）時(shí)間復(fù)雜度(n)41template 中序遍歷InOrd42template void BinaryTree:PostOrder( void(*Visit)(BinaryTreeNode *u), BinaryTreeNode *t) if (t) PostOrder(Visit, t-LeftChild);

23、 PostOrder(Visit, t-RightChild); Visit(t); 后序遍歷PostOrder（private成員函數(shù)）時(shí)間復(fù)雜度(n)42template 后序遍歷PostO43template void BinaryTree:LevelOrder( void(*Visit)(BinaryTreeNode *u) ) LinkedQueueBinaryTreeNode* Q; BinaryTreeNode *t; t = root; while (t) Visit(t); if (t-LeftChild) Q.Add(t-LeftChild); if (t-RightChi

24、ld) Q.Add(t-RightChild); try Q.Delete(t); catch (OutOfBounds) return; 逐層遍歷LevelOrder（private成員函數(shù)）時(shí)間復(fù)雜度(n)43template 逐層遍歷Level44調(diào)用示例BinaryTree a, x, y, z;int main() y.MakeTree(1, a, a); z.MakeTree(2, a, a); x.MakeTree(3, y, z); y.MakeTree(4, x, a);123444調(diào)用示例BinaryTree a, x, y,458.9 抽象數(shù)據(jù)類型及類的擴(kuò)充增加二叉樹(shù)的操

25、作： 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ù)458.9 抽象數(shù)據(jù)類型及類的擴(kuò)充增加二叉樹(shù)的操作：46private: static void Ouput(BinaryTreeNode *t) coutdata ; 8.9.1 輸出Outputpublic: void PreOuput( ) PreOrder

26、(Output, root); coutendl; 46private: 8.9.1 輸出Outputpubli47public: void InOuput( ) InOrder(Output, root); coutendl; void PostOuput( ) InOrder(Output, root); coutendl; void LevelOuput( ) LevelOrder(Output, root); coutendl; 時(shí)間復(fù)雜度(n)47public:時(shí)間復(fù)雜度(n)48public： void Delete( ) PostOrder(Free, root); root=0

27、; 8.9.2 刪除Delete 通過(guò)后序遍歷在訪問(wèn)一個(gè)節(jié)點(diǎn)時(shí)，將其刪除。private： static void Free(BinaryTreeNode *t ) delete t; 時(shí)間復(fù)雜度(n)48public： 8.9.2 刪除Delete 通過(guò)后序遍49templateint BinaryTree:Height(BinaryTree *t) const if(!t) return 0; int hl = Height(t-LefChild); int hr= Height(t-RightChild); if(hlhr) return +hl; else return +hr; 8.

28、9.3 計(jì)算高度 Height：類似后序遍歷 樹(shù)的高度： maxhl, hr+1時(shí)間復(fù)雜度(n)49template 8.9.3 計(jì)算高度50templateint BinaryTree:Size(BinaryTree *t) const if(!t) return 0; int sl = Size(t-LefChild); int sr= Size(t-RightChild); return (1+sl+sr); 8.9.4 統(tǒng)計(jì)節(jié)點(diǎn)數(shù)Size ：類似后序遍歷時(shí)間復(fù)雜度(n)50template 8.9.4 統(tǒng)計(jì)節(jié)點(diǎn)51int _count=0; / 類外定義private: static

29、void Add1(BinaryTreeNode *t) _count+; 統(tǒng)計(jì)節(jié)點(diǎn)數(shù)另一種方法：在過(guò)程中完成51int _count=0; / 類外定義 統(tǒng)計(jì)節(jié)點(diǎn)52public:int Size( ) _count=0; PreOrder(Add1, root); return _count; 將統(tǒng)計(jì)函數(shù)作為函數(shù)參數(shù)傳入52public: 將統(tǒng)計(jì)函數(shù)作為函數(shù)參數(shù)傳入53類BinaryTree：調(diào)用示例#include #include binary.h/ globalsint count = 0;BinaryTree a,x,y,z;templatevoid ct(BinaryTreeNo

30、de *t) count+; 53類BinaryTree：調(diào)用示例#include io54int main() y.MakeTree(1,a,a); z.MakeTree(2,a,a); x.MakeTree(3,y,z); y.MakeTree(4,x,a); cout Preorder sequence is ; y.PreOutput(); cout Inorder sequence is ; y.InOutput(); cout Postorder sequence is ; y.PostOutput(); cout Level order sequence is ; y.Level

31、Output(); cout Number of nodes = ; cout y.Size() endl; cout Height = ; cout y.Height() endl; y.PreOrder(ct); cout Count of nodes is count endl; return 0;Preorder sequence is 4 3 1 2Inorder sequence is 1 3 2 4Postorder sequence is 1 2 3 4Level order sequence is 4 3 1 2Number of nodes = 4Height = 3Cou

32、nt of nodes is 4123454int main()Preorder sequence 55二叉樹(shù)遍歷的非遞歸算法 遞歸算法轉(zhuǎn)換為等價(jià)的非遞歸算法，使用“?！?以前序?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)！55二叉樹(shù)遍歷的非遞歸算法 遞歸算法轉(zhuǎn)換為等價(jià)的非遞歸算法，56非遞歸前序遍歷二叉樹(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é)束56非遞歸前序遍歷二叉樹(shù)主要思想：每遇到一個(gè)結(jié)點(diǎn)，先訪問(wèn)該結(jié)57算法描述void PreOrder( BinTree T ) stack S; InitStack(&S); /遞歸工作棧 BinTreeNode * p = T; Push (&S, NULL); while ( p != NULL ) cout data rightChild != NULL ) Push ( &S, p-rightChild ); if ( p-leftChild != NULL ) p = p-leftChild; /進(jìn)左