數(shù)據(jù)結(jié)構(gòu)與算法課程設計-二叉樹仿真指針儲存結(jié)構(gòu)操作設計說明書

1、數(shù)學與計算機學院課程設計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法課程設計 課 程 代 碼: 題 目:二叉樹的仿真指針儲存結(jié)構(gòu)操作年級/專業(yè)/班: 學 生 姓 名: 學 號: 開 始 時 間: 2011 年 12 月 08 日完 成 時 間: 2011 年 12 月 20 日課程設計成績：學習態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5） 說明書（計算書、圖紙、分析報告）撰寫質(zhì)量（45）總 分（100）指導教師簽名： 年 月 日 二叉樹的仿真指針存儲結(jié)構(gòu)操作目 錄引 言- 1 -1 需求分析- 1 -1.1任務與分析- 1 -1.2測試數(shù)據(jù)- 2 -1.2.1二叉樹1- 2 -1.2.

2、2二叉樹2- 3 -1.2.3二叉樹3- 3 -2 概要設計- 4 -2.1 adt描述- 4 -2.2 程序模塊結(jié)構(gòu)- 5 -2.3 各功能模塊- 5 -3詳細設計- 6 -3.1結(jié)構(gòu)體定義- 6 -3.2 棧模板定義- 6 -3.3 類定義- 7 -3.4 初始化- 8 -3.5 創(chuàng)建二叉樹操作- 9 -3.6 輸出二叉樹操作- 9 -3.7 先序遍歷操作- 10 -3.8 中序遍歷操作- 11 -3.9 后序遍歷操作- 13 -3.10 撤銷二叉樹操作- 15 -3.11 查找操作- 15 -3.12 求各節(jié)點度操作- 16 -3.13 求二叉樹深度操作- 16 -3.14 判斷操作-

3、17 -3.15 菜單函數(shù)- 19 -4 調(diào)試分析- 21 -4.1問題分析- 21 -4.2時間復雜度分析- 21 -4.3經(jīng)驗和體會- 22 -5用戶使用說明- 22 -6測試結(jié)果- 23 -6.1菜單函數(shù)- 23 -6.2創(chuàng)建二叉樹函數(shù)- 23 -6.3輸出二叉樹函數(shù)- 24 -6.4先序遍歷二叉樹- 25 -6.5中序遍歷二叉樹- 26 -6.6后序遍歷二叉樹- 26 -6.7撤銷二叉樹函數(shù)- 27 -6.8查找函數(shù)- 27 -6.8.1基于二叉樹1的查找成功- 27 -6.8.2基于二叉樹1查找失敗- 28 -6.9求各節(jié)點度函數(shù)- 28 -6.10求二叉樹深度函數(shù)- 29 -6.1

4、1判斷函數(shù)- 29 -結(jié) 論- 31 -致 謝- 32 -參考文獻- 33 - 1 - 二叉樹的仿真指針存儲結(jié)構(gòu)操作- 31 -摘 要隨著計算機的應用以驚人的速度普及，計算機的應用早已不局限于科學計算，而更多的應用在現(xiàn)實生活中。數(shù)據(jù)的儲存結(jié)構(gòu)多種多樣，其中樹型結(jié)構(gòu)是以分支關系定義的層次結(jié)構(gòu)，是一種重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)在客觀世界中廣泛存在，例如在計算機文件管理和信息組織方面用樹型結(jié)構(gòu)來表示，又如人類的家庭族譜以及各種社會組織機構(gòu)也都可以用樹型結(jié)構(gòu)來表示。而二叉樹是一種有著重要用途的樹型結(jié)構(gòu)。研究二叉樹的基本概念、儲存結(jié)構(gòu)以及相關運算，對研究一般樹的儲存和運算有著重要意義。本文研究二叉樹的仿

5、真指針儲存結(jié)構(gòu)的實現(xiàn)以及一般操作。關鍵詞：儲存結(jié)構(gòu)；二叉樹；仿真指針儲存；一般操作。引 言數(shù)據(jù)結(jié)構(gòu)就是反映數(shù)據(jù)在內(nèi)存中的存儲方式以及對數(shù)據(jù)進行的一系列操作。數(shù)據(jù)結(jié)構(gòu)可以和生活實際相聯(lián)系，用于解決生活中實際問題。課程設計正是基于這個目的，通過課程設計，鍛煉我們發(fā)現(xiàn)問題，解決問題的能力。該次課程設計任務是實現(xiàn)有向圖的鄰接矩陣存儲方式及其相關操作，采用vs2010編程環(huán)境。1 需求分析1.1任務與分析dcgefba二叉樹的仿真指針存儲結(jié)構(gòu)是用數(shù)組存儲二叉樹中的結(jié)點，數(shù)組中每個結(jié)點除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結(jié)點之間的關系。如右圖所示，二叉樹按仿真指針存儲為：數(shù)組下標d

6、atalchildrchild0a121b342c563d-1-14e-1-15f-1-16g-1-1編寫程序?qū)崿F(xiàn)二叉樹仿真指針存儲結(jié)構(gòu)，并實現(xiàn)如下操作：1)輸出該二叉樹；2)寫出三種遍歷算法，輸出遍歷序列；3)二叉樹的撤銷操作4)查找數(shù)據(jù)元素操作5)求各結(jié)點度的操作6)求出該二叉樹的深度7)判斷該二叉樹是否是完全二叉樹？1.2測試數(shù)據(jù)1.2.1二叉樹1數(shù)組下標datalchildrchild0a121b342c5-13d-1-14e-1-15f-1-11.2.2二叉樹2數(shù)組下標datalchildrchild0a121b342c5-13d-1-14e6-15f-1-16g-1-11.2.3二

7、叉樹3數(shù)組下標datalchildrchild0a-1-12 概要設計2.1 adt描述 adt binarytree數(shù)據(jù)對象：d=具有相同特性的數(shù)據(jù)元素的有限集合；數(shù)據(jù)關系：r=順序儲存基本操作：初始化一棵空樹；建立一顆二叉樹；輸出一顆二叉樹；二叉樹的先序遍歷；二叉樹的中序遍歷；二叉樹的后序遍歷；二叉樹中數(shù)據(jù)元素的查找；求二叉樹深度；求二叉樹各結(jié)點度；判斷二叉樹是否是完全二叉樹；銷毀二叉樹；等等；adt binarytree；2.2 程序模塊結(jié)構(gòu)2.3 各功能模塊bitree(); /構(gòu)造函數(shù)bitree() ; /析構(gòu)函數(shù)void menu(); /菜單函數(shù)void creat(); /建

8、立二叉樹void display(); /輸出二叉樹void preorder(); /先序遍歷void inorder(); /中序遍歷void postorder(); /后序遍歷void destroy () /撤銷二叉樹void search(); /查找數(shù)據(jù)元素void predegree(); /求各結(jié)點度int predepth(nodetype bt); /求二叉樹的深度void predepth_bt(); /調(diào)用predepth(nodetype bt)int max(int x,int y); /比較函數(shù)void isfull_bt(); /調(diào)用is_full(nodet

9、ype m)bool is_full(nodetype m); /7)判斷二叉樹是否是完全二叉樹3詳細設計3.1結(jié)構(gòu)體定義struct nodetypeelemtype data; /存放結(jié)點值int lchild,rchild; /存放左、右孩子的數(shù)組元素的下標;3.2 棧模板定義#include stdafx.htemplate class sqstackprivate:type *stackspace;int maxsize;int top;public:sqstack(int m=30);int isempty() return top=-1; int isfull() return

10、top=maxsize-1; void push(type p);type pop();type gettop();template sqstack :sqstack(int m)top=-1; maxsize=m; stackspace =new typemaxsize;template void sqstack :push(type p)if(!isfull() top+; stackspacetop=p; template type sqstack :pop()type p;if(!isempty() p=stackspacetop; top-; return p;template ty

11、pe sqstack :gettop()if(!isempty() return stackspacetop;3.3 類定義class bitreeprivate:int length;nodetype *bt;public:bitree();bitree() ;void menu();void creat(); /建立二叉樹void display(); /1)輸出二叉樹void preorder(); /2)先序遍歷void inorder(); /2)中序遍歷void postorder(); /2)后序遍歷void destroy () /3)撤銷二叉樹void search(); /

12、4)查找數(shù)據(jù)元素void predegree(); /5)求各結(jié)點度int predepth(nodetype bt); /6)求二叉樹的深度void predepth_bt();int max(int x,int y);void isfull_bt();bool is_full(nodetype m);/7)判斷二叉樹是否是完全二叉樹;3.4 初始化bitree:bitree()bt=new nodetype maxsize; length=0;for(int i=0;ilength;i+) bti.data= ; bti.lchild=-1; bti.rchild=-1; 3.5 創(chuàng)建二叉

13、樹操作void bitree:creat()int l;coutl; length=l;if(length!=0)cout按層序遍歷輸入二叉樹數(shù)據(jù)（數(shù)據(jù)，左孩子下標，右孩子下標）：n;for(int i=0;ibti.data; cinbti.lchild; cinbti.rchild;3.6 輸出二叉樹操作void bitree:display() /1)輸出二叉樹if(length=0)cout二叉樹為空！n;elsecout按層序遍歷輸出二叉樹數(shù)據(jù)：n;cout數(shù)組下標 數(shù)據(jù)(data) 左孩子(lchild) 右孩子(rchild)n;for(int i=0;ilength;i+) c

14、outisetw(8)bti.datasetw(8)bti.lchildsetw(8)bti.rchildendl; 3.7 先序遍歷操作void bitree:preorder() /2)先序遍歷輸出if(length=0)cout二叉樹為空！n;elsecout按先序遍歷輸出二叉樹數(shù)據(jù)：n;cout數(shù)組下標 數(shù)據(jù)(data) 左孩子(lchild) 右孩子(rchild)n;nodetype m; m=bt0;int i=0,bool=1;sqstack s;sqstack t;while(bool)while(i!=-1)coutisetw(8)bti.datasetw(8)bti.lc

15、hildsetw(8)bti.rchildendl;s.push(m); t.push(i);i=bti.lchild;if(i=-1) break;else m=bti;if(s.isempty() & t.isempty() bool=0;elsei=t.pop() ; m=s.pop();while(m.rchild=-1 & !s.isempty() & !t.isempty() i=t.pop() ; m=s.pop(); i=bti.rchild;if(i=-1) ;else m=bti;3.8 中序遍歷操作void bitree:inorder() /2)中序遍歷輸出if(len

16、gth=0)cout二叉樹為空！n;elsecout按中序遍歷輸出二叉樹數(shù)據(jù)：n;cout數(shù)組下標 數(shù)據(jù)(data) 左孩子(lchild) 右孩子(rchild)n;nodetype m; m=bt0;int i=0,bool=1;sqstack s;sqstack t;while(bool)while(i!=-1)s.push(m); t.push(i);i=bti.lchild;if(i=-1) break;else m=bti; if(s.isempty() & t.isempty() bool=0;elsei=t.pop() ; m=s.pop();while(m.rchild=-1

17、 & !s.isempty() & !t.isempty()coutisetw(8)bti.datasetw(8)bti.lchildsetw(8)bti.rchildendl;i=t.pop() ; m=s.pop();coutisetw(8)bti.datasetw(8)bti.lchildsetw(8)bti.rchildendl;i=bti.rchild;if(i=-1) ;else m=bti;3.9 后序遍歷操作void bitree:postorder() /2)后序遍歷輸出if(length=0)cout二叉樹為空！n;elsecout按后序遍歷輸出二叉樹數(shù)據(jù)：n;cout數(shù)組

18、下標 數(shù)據(jù)(data) 左孩子(lchild) 右孩子(rchild)n;nodetype m; m=bt0;int i=0,bool=1,printedmaxsize;for(int j=0;jmaxsize;j+) printedj=0;sqstack s;sqstack t,j;while(bool)while(i!=-1)s.push(m); t.push(i); j.push(1);i=bti.lchild;if(i=-1) break;else m=bti; if(s.isempty() & t.isempty() bool=0;elseif(j.gettop()=1)j.pop(

19、); j.push(2); i=t.gettop(); m=s.gettop();i=bti.rchild; if(i=-1) ;else m=bti;elsei=t.pop() ; m=s.pop(); j.pop();coutisetw(8)bti.datasetw(8)bti.lchildsetw(8)bti.rchildendl;printedi=1;i=bti.rchild;if(i=-1) ;elseif(printedi=1) i=-1;else m=bti;3.10 撤銷二叉樹操作void destroy () /3)撤銷二叉樹 length=0; delete bt; cou

20、t撤銷二叉樹成功！n; 3.11 查找操作void bitree:search() /4)查找數(shù)據(jù)元素if(length=0)cout二叉樹為空！n;elseelemtype elem; int i;coutelem;for(i=0;imaxsize;i+)if(elem=bti.data) cout查找的結(jié)點如下：n;cout數(shù)組下標：i 結(jié)點值：bti.data;cout 左孩子下標：bti.lchild 右孩子下標：bti.rchild=maxsize) cout查找的結(jié)點不存在！n; 3.12 求各節(jié)點度操作void bitree:predegree() /5)求各結(jié)點度if(leng

21、th=0)cout二叉樹為空！n;elseint dg;for(int i=0;ilength;i+)dg=0;if(bti.lchild!=-1) dg+;if(bti.rchild!=-1) dg+;cout數(shù)組下標：i 結(jié)點值：bti.data 結(jié)點度：dgendl;3.13 求二叉樹深度操作void bitree:predepth_bt()if(length=0)cout二叉樹為空,樹的深度為！n;elsenodetype bt=bt0;cout樹的深度為：predepth(bt)=y?x:y);3.14 判斷操作void bitree:isfull_bt() /7)判斷二叉樹是否是完

22、全二叉樹if(length=0)cout二叉樹為空！n;elsenodetype bt=bt0;if(is_full(bt) /調(diào)用is_fullbt(bt)函數(shù)判斷是否是完全二叉樹，是則返回真，否則返回假cout該二叉樹是完全二叉樹！n;elsecout該二叉樹不是完全二叉樹！n;bool bitree:is_full(nodetype bt)int num1=1,num2=2,j=0;if(bt.lchild=-1 & bt.rchild=-1) /判斷二叉樹是否只有根節(jié)點，若只有根節(jié)點，則是完全二叉樹，返回真。return true;elsefor(int i=1;i=length |

23、num2-12(predepth(bt)-1)-1，=(2predepth(bt)-1,若不是，返回假return false;elsewhile(2*j=length-1) /2*j=length-1時，節(jié)點j有下標為*j+1的左孩子，否則沒有。若有左孩子但下標不為*j+1，則返回假if(btj.lchild!=-1 & btj.lchild!=2*j+1)return false;else j+;j=0;while(2*j+1=length-1) /2*j=length-1時，節(jié)點j有且只有下標為*j+1+1的右孩子，否則沒有。若有右孩子但下標不為*j+1，則返回假if(btj.rchil

24、d!=-1 & btj.rchild!=2*j+1+1)return false;else j+;return true;3.15 菜單函數(shù)void bitree:menu()int choice;cout*二叉樹的仿真指針存儲結(jié)構(gòu)操作*n;cout* 1.建立二叉樹 *n;cout* 2.輸出二叉樹 *n;cout* 3.先序遍歷二叉樹 *n;cout* 4.中序遍歷二叉樹 *n;cout* 5.后序遍歷二叉樹 *n;cout* 6.撤銷二叉樹 *n;cout* 7.查找數(shù)據(jù)元素 *n;cout* 8.求各結(jié)點度 *n;cout* 9.求二叉樹的深度 *n;cout* 10.判斷二叉樹是否是

25、完全二叉樹 *n;cout* 0.退出 *n;cout*謝謝使用！*n;coutchoice;switch(choice)case 1: creat(); menu(); coutendl; break; case 2: display(); coutendl; menu(); break; case 3: preorder(); coutendl; menu(); break; case 4: inorder(); coutendl; menu(); break; case 5: postorder(); coutendl; menu(); break; case 6: destroy();

26、 coutendl; menu(); break; case 7: search(); coutendl; menu(); break; case 8: predegree(); coutendl; menu(); break; case 9: predepth_bt(); coutendl; menu(); break; case 10: isfull_bt(); coutendl; menu(); break; case 0: cout退出程序！n; coutendl; break;default: cout輸入選擇錯誤！n; coutendl; menu(); 4 調(diào)試分析4.1問題分析

27、該次試驗中，認識到了二叉樹的仿真指針存儲結(jié)構(gòu)，用數(shù)組存儲二叉樹中的結(jié)點，數(shù)組中每個結(jié)點除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結(jié)點之間的關系，以及通過仿真指針儲存對二叉樹的一些基本操作，結(jié)合二叉樹的鏈表儲存及仿真指針儲存，加深了對二叉樹的理解。在后序遍歷二叉樹和判斷二叉樹是否是完全二叉樹時，通過網(wǎng)上查閱資料及書籍的幫助下成功完成算法。4.2時間復雜度分析void creat()：假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，對每個節(jié)點都要輸入一次。所以時間復雜度t(n)=o(n)。void display()：假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，對每個節(jié)點

28、都要輸入一次。所以時間復雜度t(n)=o(n)。void preorder()：假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，對每個節(jié)點都要進行一次出棧和進棧，即入棧和出棧各執(zhí)行n次，對結(jié)點訪問n次記作o(n)；伴隨遍歷每個結(jié)點都要涉及兩次入棧和兩次出棧操作，也記作o(n)。所以時間復雜度t(n)=o(n)。void inorder()：假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，對每個節(jié)點都要進行一次出棧和進棧，即入棧和出棧各執(zhí)行n次，對結(jié)點訪問n次，記作o(n)；伴隨遍歷每個結(jié)點都要涉及兩次入棧和兩次出棧操作，也記作o(n)。所以時間復雜度t(n)=o(n)。void posto

29、rder()：假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，對每個節(jié)點都要進行一次出棧和進棧，即入棧和出棧各執(zhí)行n次，對結(jié)點訪問n次，記作o(n)；伴隨遍歷每個結(jié)點都要涉及三次入棧和三次次出棧操作，也記作o(n)。所以時間復雜度t(n)=o(n)。void search()：假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，需查找的結(jié)點下標為i，則需對你i個結(jié)點進行比較。所以時間復雜度t(n)=o(n)。void predegree():假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，對每個節(jié)點都要進行一次統(tǒng)計結(jié)點度。所以時間復雜度t(n)=o(n)。int predepth(nodet

30、ype bt)：假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，對每個節(jié)點都要遍歷一次。所以時間復雜度t(n)=o(n)。bool is_full(nodetype m)：假設二叉樹的結(jié)點個數(shù)為n，即表長length=n，對每個節(jié)點都要遍歷一次。所以時間復雜度t(n)=o(n)。4.3經(jīng)驗和體會此次課程設計中，體會到了到編寫程序時，必須要理清思路，認識到完成算法需要創(chuàng)建什么，需要什么循環(huán)語句，該在什么情況是退出循環(huán)，并且不能只想不動，有新的想法時需要動手實現(xiàn)并通過測試判斷算法是否真確實現(xiàn)。5用戶使用說明用戶需安裝microsoft visual studio 2008，microsoft visual studio 2010編程軟件，并按照提示輸入。6測試結(jié)果6.1菜單函數(shù)圖6-1 菜單函數(shù)圖6.2創(chuàng)建二叉樹函數(shù)圖6-2.1 創(chuàng)建二叉樹1圖圖6-2.1 創(chuàng)建二叉樹2圖圖6-2.