1、二叉樹的前序、后序的遞歸、非遞歸遍歷算法學生姓名：賀天立 指導老師：湛新霞摘 要 本課程設計主要解決樹的前序、后序的遞歸、非遞歸遍歷算法，層次序 的非遞歸遍歷算法的實現。在課程設計中，系統開發平臺為 Windows 2000，程 序設計設計語言采用Visual C+，程序運行平臺為Windows 98/2000/XP。用除 遞歸算法前序，后續，中序遍歷樹外還通過非遞歸的算法遍歷樹。程序通過調試 運行，初步實現了設計目標，并且經過適當完善后，將可以應用在商業中解決實 際問題。關鍵詞程序設計；C+ ；樹的遍歷；非遞歸遍歷引 言本課程設計主要解決樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞 歸

2、遍歷算法的實現。課程設計的任務構造一棵樹并輸入數據，編寫三個函數，非別是樹的前序遞歸遍歷算法、樹的 后序遞歸遍歷算法、樹的非遞歸中序遍歷算法（這里的非遞歸以中序為例）。在 主程序中調用這三個函數進行樹的遍歷，觀察用不同的遍歷方法輸出的數據的順 序和驗證遞歸與非遞歸輸出的數據是否一樣。課程設計的性質由要求分析知，本設計主要要求解決樹的前序、后序的遞歸、非遞歸遍歷算 法，層次序的非遞歸遍歷算法的實現。所以設計一個良好的前序、后序的遞歸、 非遞歸遍歷算法非常重要。課程設計的目的在程序設計中，可以用兩種方法解決問題：一是傳統的結構化程序設計方法，二是更先進的面向對象程序設計方法1。利用數據結構課程的相

3、關知識完成一個具有一定難度的綜合設計題目， 利用C語言進行程序設計。鞏固和加深對線性表、棧、隊列、字符串、樹、圖、 查找、排序等理論知識的理解；掌握現實復雜問題的分析建模和解決方法（包括 問題描述、系統分析、設計建模、代碼實現、結果分析等）；提高利用計算機分 析解決綜合性實際問題的基本能力。樹的遍歷分為前序、中序和后序，可以用遞歸算法實現樹的三種遍歷。除了 遞歸外還可以構造棧，利用出棧和入棧來實現樹的前序遍歷、中序遍歷和后序遍 歷。需求分析（1）根據給定二叉樹的先序遍歷結果，構造出該二叉樹； 按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹。（2）給出該二叉樹的遞歸前序和后序遍歷結

4、果還有非遞歸中序遍歷結果。二叉樹非遞歸遍歷是用顯示棧來存儲二叉樹的結點指針。前序遍歷時,按二叉樹前序 遍歷的順序訪問結點并將結點的指針入棧,直到棧頂指針指向的結點的左指針域為空時取出 棧頂指針并刪除棧頂指針,訪問剛取出的指針指向的結點的右指針指向的結點并將其指針入 棧,如此反復執行且在有標志的情況下實現前序非遞歸算法。前序遍歷二叉樹的遞歸遍歷為 若二叉樹為空，則算法結束，否則（1）訪問根結點，（2）前序遍歷左子樹，（3）前序遍歷 右子樹。后序遍歷得遞歸為若二叉樹非空，則依次執行如下操作：（1）遍歷左子樹；（2）遍歷 右子樹；（3）訪問根結點。概要設計3.1 數據存儲結構二叉樹的存儲結構type

5、def char DataType;struct BitreeNodeDataTypedata;BitreeNode*lchild;BitreeNode*rchild;3.2 基本操作T=CreateBitree();/創建樹Preorder(T) ;/輸出樹的前序遍歷Postorder(T);/輸出樹的后序遍歷Inorder2(T)；/輸出樹的非遞歸中序遍歷以下為流程圖：詳細設計4.1 數據類型定義二叉樹的定義：二叉樹的存儲結構typedef char DataType;struct BitreeNodeDataType data;/二叉樹的數據BitreeNode*lchild;/指向左孩

6、子的指針BitreeNode*rchild;/指向右孩子的指針;4.2 系統主要子程序詳細設計主程序模塊設計及用戶工作區模塊設計： void main()struct BitreeNode*T=0;/定義T為指向BitreeNode類型的指針T=CreateBitree();/ 用前序輸入法創建二叉樹prin tf( n 前序遍歷n);Preorder(T) ;/用前序遞歸輸入法輸出二叉樹prin tf( n 后序遍歷n);Postorder(T); /用后序遞歸輸入法輸出二叉樹 prin tf( n中序遍歷(非遞歸)n);Inorder2(T);/用中序非遞歸輸入法輸出二叉樹coutdata

7、=ch;T-lchild=CreateBitree();T-rchild=CreateBitree();return T;先序遞歸遍歷二叉樹：void Preorder(struct BitreeNode *p) if (p!=NULL)printf(%c,p-data);Preorder( p-lchild );Preorder(p-rchild );后序遞歸遍歷二叉樹void Postorder(struct BitreeNode *p) if (p!=NULL)Postorder( p-lchild ); Postorder(p-rchild ) ; printf(%c,p-data);

8、中序非遞歸遍歷二叉樹void Inorder2(BitreeNode *T)/ 中序遍歷二叉樹的非遞歸算法BitreeNode *p;BitreeNode * stack100;/定義了一個棧的對象sint top=0;stacktop+=T; /根結點的指針進棧while (top0)p= stacktop-1;while (p)stacktop+= p-lchild/往左下走到底p= stacktop-1;p= stack-top;/ 空指針退棧if (top0 )p=stack-top; coutdata; stacktop+= p-rchild;/訪問結點后向右下一步 釋放存儲空間：v

9、oid DeleteTree(struct BitreeNode *p) if (p!=NULL)DeleteTree( p-lchild ); DeleteTree(p-rchild ) ; free(p);調試分析系統運行主界面如圖 5.1 所示：caw乩已（亡請輸入一顆二叉樹在主菜單下，用戶輸入數據，按回車鍵。屏幕顯示如下圖所示S3血 CAWi nd Dws5ystem32cmd .exeS3晴輸入顆二叉樹孔皿F刪9丼丼網序遍歷abedefg 辰序遍歷 edbfgea 用序遍歷（非遞歸 cbdafeg請按任意鍵繼續 總結“ 數據結構 ” 是計算機類各專業的核心課程，也是其他諸多類專業的重

10、 要選修課。我通過學習這門課，可以為理解、應用和開發程序提供技術和方法支 持，為后續課程的學習提供重要思想和方法基礎。同時對于我的邏輯思維培養和 程序設計思想體系的建立有著重要的影響。在調試過程中，碰到諸多問題，比如定義表長過小，處理記錄數量錯誤時 程序的異常，記錄沖突次數等等。處理這些問題異常麻煩，有時連續錯誤，摸不 清頭緒，在不斷調試，詢問老師,和同學探討之后，終于解決，運行成功。參考文獻李文軍，李師賢，周曉聰.C+作為計算機專業程序設計入門語言的實踐與探討.計算機科學，1999, 26 （4）： 8083唐浩強 C程序設計（第三版）清華大學出版社，2005嚴蔚敏，吳偉民數據結構（C語言版

11、）清華大學出版社，1997F. Brokken and K. Kubat.C+ Annotations. Version 4.4.0m， ICCE，University of Groningen， Netherlands, 1990. 250280附錄：#includeiostream using namespace std; typedef char DataType; struct BitreeNodeDataTypedata;BitreeNode*lchild;BitreeNode*rchild;void Preorder(struct BitreeNode *p) / 先序遍歷二叉樹i

12、f (p!=NULL) printf(%c,p-data); Preorder( p-lchild ); Preorder(p-rchild );void Postorder(struct BitreeNode *p) / 后序遍歷二叉樹if (p!=NULL)Postorder( p-lchild ); Postorder(p-rchild ) ; printf(%c,p-data);/ a=&b;/PostorderBitreeNode *CreateBitree() /按先序次序輸入二叉樹 char ch;scanf(%c,&ch);BitreeNode* T=NULL;if(ch!=#

13、)T= (struct BitreeNode*)(malloc(sizeof(struct BitreeNode); T-data=ch;T-lchild=CreateBitree();T-rchild=CreateBitree();return T;void DeleteTree(struct BitreeNode *p)/ 釋放存儲空間if (p!=NULL)DeleteTree( p-lchild );DeleteTree(p-rchild ) ; free(p);/Postordervoid Inorder2(BitreeNode *T)/ 中序遍歷二叉樹的非遞歸算法BitreeNode *p;BitreeNode * stack100;/定義了一個棧的對象sint top=0; stacktop+=T;/根結點的指針進棧while (top0)p= stacktop-1;while (p)stacktop+= p-lchild ;/往左下走到底p= stacktop-1;p= stack-top;/ 空指針退棧if (top0 )p=stack-top; coutdata; stacktop+= p-rchild;/訪問結點后向右下一步/if/wh