《樹地綜合操作 大數(shù)據(jù)結構課程設計》由會員分享，可在線閱讀，更多相關《樹地綜合操作 大數(shù)據(jù)結構課程設計（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word 數(shù)據(jù)結構 課程設計(論文) 樹的綜合操作 院〔系〕名稱 專業(yè)班級 學號 學生 指導教師 — 課程設計〔論文〕任務與評語 院〔系〕：電子與信息工程學院 教研室：軟件工程 學號 學生 專業(yè)班級 課程設計〔論文〕題目 樹的綜合操作 課程設計〔論文〕任務 任務要求： 樹的綜合操作實現(xiàn)以下幾個功能：〔1〕創(chuàng)建二叉樹的存儲結構并保存；〔2〕非遞歸實現(xiàn)中序遍歷二叉樹〔3〕非遞歸實現(xiàn)先序遍歷二叉樹?！?〕遞歸實現(xiàn)層次遍歷二叉樹；〔5〕求出二叉樹的葉子結點數(shù)和層次數(shù)。 技術要求： 1、數(shù)據(jù)的邏輯結

2、構采用樹形結構，物理結構采用鏈式存儲結構〔二叉鏈表〕。 2、軟件能正常運行，界面清晰，操作要簡單。 3、系統(tǒng)要有主界面設計，調用各個功能項。 4、采用Viscal C++編寫代碼，可讀性強。 5、數(shù)據(jù)類型用typedef 定義。 指導教師評語與成績 平時成績：辯論成績：論文成績： 總成績：指導教師簽字： 年月日 注：平時成績占20%，辯論成績占40%，論文成績占40%。 19 / 23 摘 要 這次的課題主要是創(chuàng)建二叉樹的存儲結構并保存，通過這一過程了解并掌握數(shù)據(jù)結構與算法的設計方法，具備初步的獨立分析和設計能力并提高綜合運用所學

3、的理論知識和方法獨立分析和解決問題的能力 主要解決以下問題 ①創(chuàng)建二叉樹的存儲結構并保存； ②非遞歸實現(xiàn)中序遍歷二叉樹； ③非遞歸實現(xiàn)先序遍歷二叉樹； ④遞歸實現(xiàn)層次遍歷二叉樹； ⑤求出二叉樹的葉子節(jié)點數(shù)和層次樹； 關鍵詞：存儲結構；二叉樹；C++ 目 錄 第1章緒論1 系統(tǒng)的開發(fā)背景1 開發(fā)工具與語言1 第2章概要設計1 模塊劃分1 2.2 數(shù)據(jù)結構的選擇1 第3章系統(tǒng)詳細設計與編碼2 完整的源程序2 程序的輸入和輸出3 調試程序中遇到的問題與解決方案4 第4章思考題解析5 4.1 思考題的選擇5 類C算法5 程序分

4、析5 第5章總結6 參考文獻7 附錄8 第1章 緒論 系統(tǒng)的開發(fā)背景 二叉樹結構是C語言中的難點，但是近年來二叉樹的應用越發(fā)的廣泛，實用性越來越強。為了應對日新月異的時代變化，我參與了這個課題來提高自己對二叉樹的掌握 與語言 本系統(tǒng)使用Viscal C++語言開發(fā)，主界面清晰顯示所有功能項，使用簡單。各個功能項均定義一個函數(shù)來實現(xiàn)，在主函數(shù)中調用各個子函數(shù)實現(xiàn)不同的功能。 第2章 概要設計 模塊劃分 1〕題目應實現(xiàn)的具體功能； ①創(chuàng)建二叉樹的存儲結構并保存； ②非遞

5、歸實現(xiàn)中序遍歷二叉樹； ③非遞歸實現(xiàn)先序遍歷二叉樹； ④遞歸實現(xiàn)層次遍歷二叉樹； ⑤求出二叉樹的葉子節(jié)點數(shù)和層次樹； 2.2 數(shù)據(jù)結構的選擇 系統(tǒng)數(shù)據(jù)的邏輯結構采用樹形結構，物理結構采用鏈式存儲結構〔二叉鏈表〕。 存儲結構定義如下： typedef struct lnode {char data; struct lnode *lchild,*rchild; }lnode,*tree; 第3章 系統(tǒng)詳細設計與編碼 完整的源程序 #include #include #i

6、nclude #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MaxSize 100 typedef char TElemType; typedef int Status; //二叉樹的鏈式存儲結構 typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //棧的鏈式存儲結構 typedef struct LNode { BiTree data; str

7、uct LNode *next; }LNode,*LinkList; //進棧 Status Push(LinkList& S,BiTree T) { LinkList stack; stack=(LinkList)malloc(sizeof(LNode)); //分配空間 stack->data=T; stack->next=S->next; //進棧 S->next=stack; return OK; }//Push //出棧 Status Pop(LinkList &S,BiTree &T) { LinkList stack; stac

8、k=S->next; //出棧 S->next=stack->next; //棧頂指向下個元素 T=stack->data; return OK; }//Pop //是否為空棧 Status StackEmpty(LinkList S) { if(S->next==NULL) return OK; else return ERROR; } //以先序次序建立二叉樹 Status CreatBiTree(BiTree &T) { TElemType ch; cin>>ch; if(ch=='#') T=NULL; else{

9、 if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW); //分配存儲空間 T->data=ch; //生成根節(jié)點 CreatBiTree(T->lchild); //生成左子樹 CreatBiTree(T->rchild); //生成右子樹 } return OK; //創(chuàng)建成功 }//CreatBiTree //非遞歸中序訪問二叉樹 BiTree GoFarLeft(BiTree T,LinkList &

10、S) //指到二叉樹最左邊結點 { if(!T) return NULL; while(T->lchild) { Push(S,T); //結點進棧 T=T->lchild; } return T; //返回樹頭結點 } void Inorder_I(BiTree T) { BiTree t; LinkList S; S=(LinkList)malloc(sizeof(LNode)); S->next=NULL; t=GoFarLeft(T,S); //找到最左下的結點 while (t) {

11、 cout<data<<" "; if(t->rchild) t=GoFarLeft(t->rchild,S); else if(!StackEmpty(S)) //?？彰鞔_遍歷完畢 Pop(S,t); else t=NULL; }//while cout<

12、>0) { while(p!=NULL) { cout<data<<" "; //輸出結點data Stack[top]=p; //左樹進棧 top++; p=p->lchild; } if(top>0) { top--; p=Stack[top]; p=p->rchild; } } cout<

13、p; p=(BiTree)malloc(sizeof(BiTree)); stack=(LinkList)malloc(sizeof(LinkList)); stack->next=NULL; Push(stack,b); //二叉樹頭結點進棧 while(!StackEmpty(stack)) //是否為空 { Pop(stack,p); //出棧 while (p) { cout<data<<" "; //輸出當前指向結點 if(p->rchild)Push(stack,p->rchild); //訪

14、問右指點 p=p->lchild; } } cout<lchild; } while (top>0&&stack[top]->rchild==p) { p=stack[top--]; //棧頂結點出棧

15、 cout<data<<" "; //訪問p所指向的結點 } if (top>0) p=stack[top]->rchild; //開始遍歷右子樹 }while(top>0); cout<lchild)&&(!T->rchild)) count++; CountLeaf(T->lchild,count); //左子樹葉子個數(shù) CountLeaf(T

16、->rchild,count); //右子樹葉子個數(shù) } }//CountLeaf //計算雙結點個數(shù) void CountParent(BiTree T,int &count) { if(T) { if(T->lchild&&T->rchild) count++; CountParent(T->lchild,count); //左子樹雙結點個數(shù) CountParent(T->rchild,count); //右子樹雙結點個數(shù) } } //計算二叉樹結點個數(shù) void Count(BiTree T,int &count) { if(T) {

17、 Count(T->lchild,count); Count(T->rchild,count); count++; //結點個數(shù) } } //單結點個數(shù) void CountChild(BiTree T,int &count) { if(T) { if((T->lchild&&(!T->rchild))||(T->rchild&&(!T->lchild))) count++; CountChild(T->lchild,count); //左子樹單結點個數(shù) CountChild(T->rchild,count);

18、 //右子樹單結點個數(shù) } } //計算樹的高度 int Depth(BiTree T) { int depthval,depthLeft,depthRight; if(!T) depthval=0; else {depthLeft=Depth(T->lchild); //左子樹高度 depthRight=Depth(T->rchild); //右子樹高度 depthval=1+(depthLeft>depthRight ?depthLeft:depthRight); //取高度最高 } return depthval; //返回

19、} //計算任意結點所在的層次 int NodeLevel(BiTree T,TElemType &p,int &count) { if(T==NULL) return 0; if(T->data==p) return 1; if(NodeLevel(T->lchild,p,count)||(NodeLevel(T->rchild,p,count))) { count++; return 1; } return 0; } //主函數(shù) void main() { char flag; cout<<"操作選項"<

20、t<<"1,非遞歸打印二叉樹(前序，中序，后序)"<>item; switch (item) { case 1 : { BiTree T; cout<<"請輸入要建立的二叉樹,以'#'表示空樹"<

21、; CreatBiTree(T); cout<<"先序非遞歸輸出二叉樹(兩種算法)"<

22、)"<>flag; break; } case 2: { BiTree T; int nodeCount=0,leafCount=0,childCount=0,parentCount=0; cout<<"請輸入要建立的二叉樹,以'#'表示空樹"<

23、 CountLeaf(T,leafCount); cout<<"結點總數(shù)目為:"<>flag; break; } case 3: { BiTree T;

24、 cout<<"請輸入要建立的二叉樹,以'#'表示空樹"<>flag; break; } case 4: { BiTree T; int n=0; char ch; cout<<"請輸入要建立的二叉樹,以'#'表示空樹"<

25、T); cout<<"請輸入要查詢的結點:"; cin>>ch; if(T==NULL) cout<<"空樹"<>flag; break; } default : cout<<"無此選項請確定后再輸入!"<

26、 } } while (flag=='y'||flag=='Y'); } 問題： 首先要按照提示輸入，在創(chuàng)建二叉樹的時候，要注意二叉樹的輸入，要用“#〞代替空，否如此程序不能正確運行；每次執(zhí)行新的任務的時候都要重新輸入新的二叉樹。 解決方案：按照先序遍歷輸入二叉樹，如果結點左孩子或右孩子為空如此用“#〞代替；求葉子結點數(shù)和求層次時，所先用的子函數(shù)中的參數(shù)初始賦值為零，再從頭結點出發(fā)開始計數(shù)，直到所求結點。 第4章 思考題解析 4.1 思考題

27、的選擇 所選擇的思考題：編寫一個算法，求一顆二叉樹中每個結點平衡因子 類C算法 int btheight(BitTNode *BT) { int lh,rh,t; if(BT==NULL) return 0; else { lh=btheight(BT->lchild);/*計算左子數(shù)的高度*/ rh=btheight(BT->rchild);/*計算右子數(shù)的高度*/ if(lh<=rh) t=rh; else t=lh; BT->num=lh-rh;/*計算結點的平衡因子*/ return t+1 } } 結點的平衡因子等于其左子樹結點層次減去

28、其右子樹結點層次，因此要想求得每個結點的平衡因子，就得在遍歷每個結點的時候，算出其左，右子樹的層次，程序中用到了遞歸調用子函數(shù) btheight(bitnode *bt) 第5章 總結 這是一門純屬于設計的科目，它需用把理論變?yōu)樯蠙C調試。剛開始學的時候確實有很多地方我很不理解，每次上課時教師都會給我們出不同的設計題目，對于我們一個初學者來說，無疑是一個具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細去寫程序。教師會給我們需要編程的容一些講解，順著教師的思路，來完成自己的設計，我們可以開始運行自己的程序。?

29、 剛開始學的時候確實有很多地方我很不理解，每次上上機課時教師都會給我們出不同的設計題目，對于我們一個初學者來說，無疑是一個具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細去寫程序。教師會給我們需要編程的容一些講解，順著教師的思路，來完成自己的設計，我們可以開始運行自己的程序，可是好多處的錯誤讓人看的可怕，還看不出到底是哪里出現(xiàn)了錯誤，但是程序還是得繼續(xù)下去，我屢次請教了教師和同學，逐漸能自己找出錯誤，并加以改正。TC里檢查錯誤都是用英文來顯示出來的，經(jīng)過了這次課程設計，現(xiàn)在已經(jīng)可以了解很多錯誤在英文里的提示，這對我來說是一個突破性的進步，眼看著一個個錯誤通過自己的努力在我眼前消失，覺得很是開心

30、。此次的程序設計能夠成功，是我和我的同學三個人共同努力作用的結果。在這一段努力學習的過程中，我們的編程設計有了明顯的提高。? 其實現(xiàn)在想起來，收獲還真是不少，雖然說以前非常不懂這門語言，在它上面花費了好多心血，覺得它很難，是需用花費了大量的時間編寫出來的?，F(xiàn)在真正的明白了一些代碼的應用，每個程序都有一些共同點，通用的結構，相似的格式。只要努力去學習，就會靈活的去應用它。 本人簽字： 參考文獻 [1] 徐孝凱編著. 數(shù)據(jù)結構[M]第一版 [2] 文博編著.數(shù)據(jù)結構[M]第二版 [3] 許卓群編著.數(shù)據(jù)結構[M]第一版 [4] 廉治編著.數(shù)據(jù)結構教程[M]第一版 [5] 晉良潁編著.數(shù)據(jù)結構簡明教程[M]第三版