數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--二叉樹的遍歷

1、精選優(yōu)質(zhì)文檔-傾情為你奉上摘要針對現(xiàn)實(shí)世界中許多關(guān)系復(fù)雜的數(shù)據(jù)，如人類社會的家譜，各種社會組織機(jī)構(gòu),博弈交通等復(fù)雜事物或過程以及客觀世界中廣泛存在的具有分支關(guān)系或?qū)哟翁匦缘膶ο笕绮僮飨到y(tǒng)的文件構(gòu)成、人工智能和算法分析的模型表示以及數(shù)據(jù)庫系統(tǒng)的信息組織形式等，用線性結(jié)構(gòu)難以把其中的邏輯關(guān)系表達(dá)出來，必須借助于數(shù)和圖這樣的非線性結(jié)構(gòu)，因此在以模擬客觀世界問題，解決客觀世界問題為主要任務(wù)的計算機(jī)領(lǐng)域中樹型結(jié)構(gòu)是信息的一種重要組織形式，樹有著廣泛應(yīng)用。在樹型結(jié)構(gòu)的應(yīng)用中又以二叉樹最為常用。二叉樹是一種非常重要的非線性結(jié)構(gòu)，所描述的數(shù)據(jù)有明顯的層次關(guān)系，其中的每個元素只有一個前驅(qū)，二叉樹是最為常用的數(shù)據(jù)

2、結(jié)構(gòu)，它的實(shí)際應(yīng)用非常廣泛，二叉樹的遍歷方式有三種，前序遍歷，中序遍歷，后序遍歷，先序遍歷的順序?yàn)椋篘LR先根結(jié)點(diǎn)，然后左子樹，右子樹；中序遍歷順序?yàn)椋籐NR先左子樹，然后根結(jié)點(diǎn)，右子樹；后序遍歷順序?yàn)椋篖RN先左子樹，然后右子樹，根結(jié)點(diǎn)。由前序和中序遍歷，有中序和后序遍歷序列可以唯一確定一棵二叉樹。對于給幾個數(shù)據(jù)的排序或在已知的幾個數(shù)據(jù)中進(jìn)行查找，二叉樹均能提供一種十分有效的方法，比如在查找問題上，任何借助于比較法查找長度為的一個序表的算法，都可以表示成一株二叉樹。反之，任何二叉樹都對應(yīng)一個查找有序表的有效方法根據(jù)樹的數(shù)學(xué)理論，對于算法分析的某些最有啟發(fā)性的應(yīng)用，是與給出用于計算各種類型中不

3、同樹的數(shù)目的公式有關(guān)的。本文對二叉樹以及二叉樹的各種功能做介紹以及寫出一些基本的程序，讓我們對二叉樹的理解有更好的效果。關(guān)鍵詞：二叉樹的遍歷；左子樹；右子樹；遞歸專心-專注-專業(yè)目錄1.問題概述1.1問題描述創(chuàng)建二叉樹并遍歷基本要求：該程序集成了如下功能：（1）二叉樹的建立（2）遞歸和非遞歸先序，中序和后序遍歷二叉樹（3）按層次遍歷二叉樹（4）交換二叉樹的左右子樹（5）輸出葉子結(jié)點(diǎn)（6）遞歸和非遞歸計算葉子結(jié)點(diǎn)的數(shù)目1.2需求分析分先序遍歷，中序遍歷和后序遍歷三種情況考慮。1. 先序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否則結(jié)束操作：1 訪問根結(jié)點(diǎn)；2 按先序遍歷規(guī)則遍歷左子樹；3 按先序遍歷規(guī)

4、則遍歷右子樹；2. 中序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否則結(jié)束操作：1 按中序遍歷規(guī)則遍歷左子樹；2 訪問根結(jié)點(diǎn)；3 按中序遍歷規(guī)3遍歷右子樹。3. 后序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否則結(jié)束操作：1 按后序遍歷規(guī)則遍歷左子樹；2 按后序遍歷規(guī)則遍歷右子樹；3 訪問根結(jié)點(diǎn)。1.3設(shè)計內(nèi)容和要求對任意給定的二叉樹（頂點(diǎn)數(shù)自定）建立它的二叉鏈表存貯結(jié)構(gòu)，并利用棧的五種基本運(yùn)算（清空堆棧、壓棧、彈出、取棧頂元素、判?？眨?shí)現(xiàn)二叉樹的先序、中序、后序三種周游，輸出三種周游的結(jié)果。1.4流程圖及結(jié)構(gòu)圖YESYESNONO開始i=0inbtreetypenewNodeMultiplexroot

5、=newNodei+結(jié)束是否為空returnroot圖1.1 流程圖 b c d e f a圖1.2二叉鏈表存儲結(jié)構(gòu)模擬圖2.概要設(shè)計2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計：1二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義為：templatestructBiNodeBiNode*rchild,*lchild;/指向左孩子的指針Tdata;/結(jié)點(diǎn)數(shù)據(jù)信息;2二叉樹數(shù)據(jù)類型定義為：templateclassBiTreetemplatefriendostream&operator(ostream&os,BiTree&bt);public:BiTree();/無參構(gòu)造函數(shù)BiTree(intm);/有參空構(gòu)造函數(shù)BiTree(Tary,intn

6、um,Tnone);/有參構(gòu)造函數(shù)BiTree();/析構(gòu)函數(shù)voidpreorder();/遞歸前序遍歷voidinorder();/遞歸中序遍歷voidpostorder();/遞歸后續(xù)遍歷voidlevelorder();/層序遍歷intcount();/計算二叉樹的結(jié)點(diǎn)數(shù)voiddisplay(ostream&os);/打印二叉樹，有層次voidLevelNum();/計算每一層結(jié)點(diǎn)數(shù)voidPreOrder();/非遞歸前序遍歷voidPostOrder();/非遞歸后序遍歷voidcreat();/創(chuàng)建二叉樹protected:/以下函數(shù)供上面函數(shù)調(diào)用/對應(yīng)相同功能Voidcrea

7、t(BiNode*&root);/創(chuàng)建voidrelease(BiNode*&root);/刪除BiNode*Build(Tary,intnum,Tnone,intidx);/用數(shù)組創(chuàng)建二叉樹voidPreOrder(BiNode*root);/前序遍歷voidPostOrder(BiNode*root);/后續(xù)遍歷voidLevelNum(BiNode*root);/層序遍歷voidpreorder(BiNode*root);/遞歸前序遍歷voidinorder(BiNode*root);/遞歸中序遍歷voidpostorder(BiNode*root);/遞歸后續(xù)遍歷voidlevelor

8、der(BiNode*root);/層序遍歷intcount(BiNode*root);/計算結(jié)點(diǎn)數(shù)voiddisplay(ostream&os,BiNode*root,intdep);/打印staticboolleastCommanAncestor(BiNode*root,Tva,Tvb,BiNodeprivate:BiNode*rootptr;2.2源程序代碼#include using namespace std;/*/二叉樹結(jié)點(diǎn)類的定義templatestruct BTNodeT data; BTNode * Lchild,*Rchild; BTNode(T nodeValue = T

9、(),BTNode* leftNode = NULL,BTNode* rightNode = NULL ) :data(nodeValue),Lchild(leftNode),Rchild(rightNode) /可選擇參數(shù)的默認(rèn)構(gòu)造函數(shù);/*/二叉樹的建立template void createBinTree(BTNode * &root ) BTNode* p = root; BTNode* k; T nodeValue ; cinnodeValue; if(nodeValue=-1) root=NULL; else root=new BTNode(); root-data = nodeV

10、alue; createBinTree(root-Lchild); createBinTree(root-Rchild); /*/二叉樹的先序遍歷template void preOrder( BTNode * & p) if(p) coutdataLchild); preOrder(p-Rchild); /*/二叉樹的中序遍歷template void inOrder(BTNode * & p) if(p) inOrder(p-Lchild); coutdataRchild); /*/二叉樹的后序遍歷template void levelOrder(BTNode *& p) if(p) le

11、velOrder(p-Lchild); levelOrder(p-Rchild); coutdata ; /*/統(tǒng)計二叉樹中結(jié)點(diǎn)的個數(shù)templateint countNode(BTNode * & p) if(p = NULL) return 0; return 1+countNode(p-Lchild)+countNode(p-Rchild);/*/求二叉樹的深度templateint depth(BTNode *& p) if(p = NULL) return -1; int h1 = depth(p-Lchild); int h2 = depth(p-Rchild); if(h1h2)

12、return (h1+1); return h2+1;/*/二叉樹的消毀操作templateBTNode* destroy(BTNode* p) /消毀函數(shù)，用來消毀二叉樹中的各個結(jié)點(diǎn) if(p) return destroy(p-Lchild); return destroy(p-Rchild); delete p; /*/主函數(shù)的設(shè)計 int main () BTNode * rootNode = NULL; int choiced = 0; while(true) system(cls); coutnnn -主界面-nnn; cout 1、創(chuàng)建二叉樹 2、先序遍歷二叉樹n; cout 3

13、、中序遍歷二叉樹 4、后序遍歷二叉樹n; cout 5、統(tǒng)計結(jié)點(diǎn)總數(shù) 6、查看樹深度 n; cout 7、消毀二叉樹 0、退出nn; coutchoiced; if(choiced = 0) return 0; else if(choiced = 1) system(cls); cout請輸入每個結(jié)點(diǎn)，回車確認(rèn)，并以-1結(jié)束：n; createBinTree(rootNode ); else if(choiced = 2) system(cls); cout先序遍歷二叉樹結(jié)果：n; preOrder(rootNode); coutendl; system(pause); else if(cho

14、iced = 3) system(cls); cout中序遍歷二叉樹結(jié)果：n; inOrder(rootNode); coutendl; system(pause); else if(choiced = 4) system(cls); cout后序遍歷二叉樹結(jié)果：n; levelOrder(rootNode); coutendl; system(pause); else if(choiced = 5) system(cls); int count = countNode(rootNode); cout二叉樹中結(jié)點(diǎn)總數(shù)為countendl; system(pause); else if(choi

15、ced = 6) system(cls); int dep = depth(rootNode); cout此二叉樹的深度為dependl; system(pause); else if(choiced = 7) system(cls); cout二叉樹已被消毀！n; destroy(rootNode); coutendl; system(pause); else system(cls); coutnnnnnt錯誤選擇！n; 3.調(diào)試分析3.1調(diào)試中的問題創(chuàng)建二叉樹：依次輸入二叉樹前序遍歷序列，構(gòu)建相應(yīng)的二叉樹。二叉樹遍歷：遞歸算法、非遞歸算法測試，調(diào)用相應(yīng)函數(shù)進(jìn)行測試，結(jié)果正確。求二叉樹深度和

16、結(jié)點(diǎn)數(shù)：創(chuàng)建一個二叉樹，調(diào)用相關(guān)函數(shù)，測試結(jié)果正確。計算每層結(jié)點(diǎn)數(shù)：調(diào)用levelNum()函數(shù)，測試結(jié)果正確。調(diào)試時遇到諸多問題，其中最主要的問題是死循環(huán)問題，在非遞歸遍歷時，容易進(jìn)入死循環(huán)，經(jīng)過查找資料、分步調(diào)試最終找到循環(huán)結(jié)束條件，順利解決各個難題。4.測試結(jié)果（1）初始界面:主界面所包含的內(nèi)容圖4.1初始界面圖（2）運(yùn)行結(jié)果：進(jìn)行操作1，輸入每個結(jié)點(diǎn)，顯示結(jié)果如下圖4.2創(chuàng)建二叉樹進(jìn)行操作2，執(zhí)行結(jié)果如下：圖4.3二叉樹先序遍歷進(jìn)行操作3，執(zhí)行結(jié)果如下：圖4.4二叉樹中序遍歷進(jìn)行操作4，執(zhí)行結(jié)果如下：圖4.5二叉樹后序遍歷:進(jìn)行操作5，執(zhí)行結(jié)果如下：圖4.6統(tǒng)計二叉樹節(jié)點(diǎn)進(jìn)行操作6，執(zhí)行結(jié)果如下：圖4.7查看樹深度總結(jié)要能很好的掌握編程,僅僅通過幾個簡單的程序的編寫時無法達(dá)成的,更需要大量積累和深入才可能通過本次課程設(shè)計。有關(guān)一個課題的所有知識不僅僅是在課本上，多查閱一些資料能夠更好的完成課題，這就需要一種能力，即自學(xué)能力。本次課程設(shè)計還讓我認(rèn)識到自己的缺點(diǎn)。本