C課程設計論文二叉樹的應用

1、課程設計報告書二叉樹的應用2010-10hunan normal universityelectronic & information engineering department課程設計題目二叉樹的應用指導教師姓名指導老師職稱學生姓名所屬班級任務要求二叉樹的中序、前序、后序的遞歸與非遞歸遍歷算法，按層次遍歷的非遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)，樹與二叉樹的轉換的實現(xiàn)主要實施步驟1、 構造二叉樹，樹以及相關的數(shù)據(jù)結構2、 建立二叉樹3、 二叉樹的不同遍歷4、 樹的遍歷5、 樹與二叉樹的轉換6、 屆面的設計結論通過這次的課程設計，進一步的加強了對二叉樹及樹的了解，嘗試了種新的建樹的方

2、法，通過類似于建查找二叉樹：大的是兄弟，小的孩子來建樹，這樣不會限制樹的維度，只根據(jù)于用戶輸入的數(shù)據(jù)來建，降低了用戶輸入的難度。另外，也發(fā)現(xiàn)將二叉樹用于其它的系統(tǒng)的數(shù)據(jù)存儲，查找時會比較容易，以后可試著研究把二叉樹作為一種有效的存儲手段。湖南師范大學工學院電子與信息工程系課程設計登記表注：此表格內容中的任務要求為指導教師提供的課程設計要求，主要實施步驟是指課程設計的時間安排，結論是指通過課程設計得出的有關結論及課程設計不足之處或進一步開發(fā)方向。目 錄1引言4 1.1 課程設計目標41.2編程工具（編程環(huán)境）介紹41.3實施時間及主要實施步驟42.需求分析43系統(tǒng)總體設計54數(shù)據(jù)結構設計55詳細

3、設計與實現(xiàn)6 5.1功能模塊1 65.1.1詳細設計6 5.1.2算法流程65.1.3界面設計及測試結果75.2功能模塊8 5.2.1詳細設計85.2.2算法流程85.2.3界面設計及測試結果105.3功能模塊12 5.3.1詳細設計125.3.2算法流程125.3.3界面設計及測試結果146算法分析157、測試結果158結論229參考文獻221 引言1.1 課程設計目標1、 建樹的實現(xiàn)2、 二叉樹的中序、前序、后序的遞歸與非遞歸遍歷算法的實現(xiàn)3、 按層次遍歷的非遞歸遍歷算法的實現(xiàn)4、 樹與二叉樹的轉換的實現(xiàn)1.2 編程工具（編程環(huán)境）介紹在windeow x p 下用的 dev-c+ 4.9

4、.9.2 編程工具c+是一種靜態(tài)數(shù)據(jù)類型檢查的，支持多重編程范式的通用程序設計語言。它支持過程化程序設計、數(shù)據(jù)抽象、面向對象程序設計、制作圖標等等泛型程序設計等多種程序設計風格。1.3 實施時間及主要實施步驟 實施時間：9月13號9月24號 主要實施步驟：1、構造二叉樹，樹以及相關的數(shù)據(jù)結構 2、建立二叉樹3、二叉樹的不同的遍歷 4、樹的遍歷 5、樹與二叉樹的轉換 6、屆面的設計2 需求分析本程序的功能是采用查找二叉樹的方法建樹，并對二叉樹進行遞歸前序遍歷、中序遍歷和后序遍歷，用棧實現(xiàn)非遞歸的前序、中序和后序遍歷，還有對二叉樹的層次遍歷，以及樹的建立，樹的廣度優(yōu)先和深度優(yōu)先遍歷，樹與二叉樹的轉

5、換。本程序要求用戶以字符輸入，以#結束輸入，采用查找二叉樹的方法建樹。本程序輸出結果以用戶要求為準，可打印出二叉樹的遞歸與非遞歸的先序、中序和后序遍歷以及層次遍歷，還有樹的廣度優(yōu)先和深度優(yōu)先遍歷以及樹轉換成二叉樹后的先序遍歷。演示程序以用戶與計算機對話的方式進行，即在計算機終端上顯示提示信息后，由用戶在鍵盤上輸入相應動作的序號和相應的輸入數(shù)據(jù)。測試數(shù)據(jù)：第一組：j ld e b a h i u x f d h n 第二組：7 4 3 2 8 9 0 第三組：* ） （ ？ < > % ! = + 3 系統(tǒng)總體設計系統(tǒng)共分為三個模塊：first,arytree,ntreefirst模

6、塊是作為與用戶交流的第一個接口，通過它將選擇是對樹或二叉樹進行操作。arytree模塊是對二叉樹的全部操作，它又分為建樹（maketree）模塊、先序遍歷（xianxu）模塊、中序遍歷（zhongxu）模塊、后序遍歷（houxu）模塊、層次遍歷（cenchi）模塊，它們分別完成二叉樹的建立，以及遞歸和非遞歸的先序遍歷、中序遍歷、后序遍歷和層次遍歷算法。ntree模塊是對樹的全部操作，它又分為建樹（makentree）模塊、深度優(yōu)先遍歷（shendu）模塊、廣度優(yōu)先遍歷（guangdu）模塊、樹轉換成二叉樹（change）模塊，它們分別完成樹的建立，以及深度優(yōu)先、廣度優(yōu)先和樹轉換成二叉樹算法。4

7、 數(shù)據(jù)結構設計二叉樹的數(shù)據(jù)結構：1、 二叉樹結點：jiedian:classdata:charleftchild:jiedian *rightchild:jiedian *2、 二叉樹結構：tree:structcurrent:jiedian *end:jiedian *houxu(jiedian *):intmaketree():intxianxu(jiedian *):intzhongxu(jiedian *):intcenchi():voidhouxu():voidxianxu():voidzhongxu():voidtree():constructor3、 二叉樹隊列：treequeu

8、e:structaddress:jiedian *next:treequeue *4、 二叉樹棧結點：stacknode:structtreeaddress:jiedian *next:stacknode *5、 二叉樹棧：stack:structhead:stacknode *tail:stacknode *pop():jiedian *push(jiedian *):voidstack():constructor6、 樹結點：ntreenode:structdata:charbrother:ntreenode *child:ntreenode *7、 樹結構：ntree:structcur

9、rentn:ntreenode *endn:ntreenode *change(tree *tree):intguangdu(ntreenode *):intmakentree():intshendu(ntreenode *):intntree():construdtor8、 樹棧結點：stacknodes:strudttreeaddress:ntreenode *next:stacknodes *9、 樹棧：stacks:structhead:stacknodes *tail:stacknodes *pop():ntreenode *push(ntreenode *):voidstacks(

10、):constructor10、樹隊列：ntreequeue:structaddress:ntreenode *next:stacknodes *5 詳細設計與實現(xiàn)5.1 功能模塊1詳細設計5.1.1 詳細設計 1) 模塊名稱first2) 功能說明調用one模塊輸出系統(tǒng)首界面提供給用戶選擇想要的操作對象：樹和二叉樹，選擇樹后會調用tree模塊或選擇二叉樹調用arytree模塊 3) 輸入?yún)?shù)的名稱、數(shù)據(jù)類型、順序位置、格式無輸入?yún)?shù)4) 輸出參數(shù)的名稱、數(shù)據(jù)類型、順序位置、格式無返回參數(shù)，打印輸出畫面為5) 所調用的其他功能構件one,ntree,arytree6) 被調用的其他功能構件nt

11、ree,arytree5.1.2 算法流程調用ntree模塊選擇序號輸入調用arytree模塊退出102void first()int i;one();while(1) cin>>i; if(i>=0&&i<=2) break; else cout<<"您輸入的數(shù)據(jù)有誤，請重新輸入:"continue; switch(i) case 1:arytree();break; case 2:ntree();break; case 0:system("pause");exit(0);break; 5.1.3 界

12、面設計及測試結果對本功能模塊的界面設計做詳細闡述，并給出測試的結果5.2 功能模塊2詳細設計5.2.1 詳細設計 1) 模塊名稱 arytree2) 功能說明調用各子模塊完成二叉樹的建樹及根據(jù)用戶的要求完成二叉樹的先序、中序和后序遍歷。3) 輸入?yún)?shù)的名稱、數(shù)據(jù)類型、順序位置、格式無輸入?yún)?shù)4) 輸出參數(shù)的名稱、數(shù)據(jù)類型、順序位置、格式各種遍歷的結果5) 所調用的其他功能構件two,tree,6) 被調用的其他功能構件first5.2.2 算法流程先用tree類型建立一個二叉樹后根據(jù)用戶輸入的操作選擇，對二叉樹進行相應的操作建一個二叉樹輸入對應操作的序號退出先序遍歷二叉樹后序遍歷二叉樹中序遍歷

13、二叉樹返回first模塊01294層次遍歷二叉樹3void arytree() tree tree; tree.maketree(); while(1) two(); int n; cin>>n; switch(n) case 1:cout<<"遞歸先序遍歷二叉樹：" tree.xianxu(tree.current); cout<<endl; cout<<"非遞歸先序遍歷二叉樹：" tree.xianxu(); break; case 2:cout<<"遞歸中序遍歷二叉樹："

14、; tree.zhongxu(tree.current); cout<<endl; cout<<"非遞歸中序遍歷二叉樹：" tree.zhongxu(); break; case 3:cout<<"遞歸后序遍歷二叉樹：" tree.houxu(tree.current); cout<<endl; cout<<"非遞歸后序遍歷二叉樹：" tree.houxu(); break; case 4:cout<<"層次遍歷二叉樹：" tree.cench

15、i(); break; case 9:first();break; case 0:system("pause");exit(0);break; if(n>=1&&n<=4) continue; else break; 5.2.3 界面設計及測試結果.5.3 功能模塊3詳細設計5.3.1 詳細設計1) 模塊名稱 ntree2) 功能說明調用各子模塊完成樹的建樹及根據(jù)用戶的要求完成樹的廣度優(yōu)先以及深度優(yōu)先遍歷，和樹轉換成二叉樹。3) 輸入?yún)?shù)的名稱、數(shù)據(jù)類型、順序位置、格式等無輸入?yún)?shù)4) 輸出參數(shù)的名稱、數(shù)據(jù)類型、順序位置、格式等、樹的廣度優(yōu)先遍歷

16、與深度優(yōu)先遍歷的結果及樹轉換成二叉樹后的先序遍歷結果5) 所調用的其他功能構件three,ntree6) 被調用的其他功能構件first5.3.2 算法流程建一個樹輸入對應操作的序號退出廣度優(yōu)先遍歷二叉樹樹轉換成二叉樹深度優(yōu)先遍歷二叉樹返回first模塊01293void ntree() ntree ntree; ntree.makentree(); tree *tree; while(1) int m; three(); cin>>m; switch(m) case 1:cout<<"樹的深度優(yōu)先遍歷：" ntree.shendu(ntree.cu

17、rrentn); break; case 2:cout<<"樹的廣度優(yōu)先遍歷：" ntree.guangdu(); break; case 3:ntree.change(tree); break; case 9:first();break; case 0:system("pause");exit(0);break; if(m>=1&&m<=3) continue; else break; 5.3.3 界面設計及測試結果6 算法分析創(chuàng)建二叉樹 , 時間復雜度 o(n) ， 空間復雜度 o(n)樹對二叉樹的轉換, 這里

18、不確定樹的維度因此時間復雜度o(m*m*n),空間復雜度 o(n),m是指樹的維度先序遍歷二叉樹（遞歸）, 時間復雜度 o(2 * n) ， 空間復雜度 o(1)n 是這里的總結點個數(shù),因為這里要訪問到每個葉子結點的子結點，所以是o(2*n)，但是這里的遞歸調用的時候還要很多保護場景操作所要的時間先序遍歷二叉樹（非遞歸）, 時間復雜度o(n*n) ， 空間復雜度 o(n)中序遍歷二叉樹（遞歸）, 時間復雜度 o(n) ， 空間復雜度 o(1)中序遍歷二叉樹（非遞歸）, 時間復雜度 o(n*n) ， 空間復雜度o(n)后序遍歷二叉樹（遞歸）, 時間復雜度o(n) ， 空間復雜度 o(1)后序遍歷二叉樹（非遞歸）, 時間復雜度 o(n*n) ， 空間復雜度o(n)層遍歷二叉樹（非遞歸）, 時間復雜度 o(n) ， 空間復雜度 o(n)7 。測試結果第一組測試數(shù)據(jù)：j l d e b a h i u x f d h n 第二組：7 4 3 2 8 9 0 第三組：* ） （ ？ < > % ! = + 8 結