摘針對現(xiàn)實世界中許多關(guān)系復(fù)雜的數(shù)據(jù)人類社會的家譜種社會組織機構(gòu),博弈交通等復(fù)雜事物或過程以及客觀世界中廣泛存在的具有分支關(guān)系或?qū)哟翁匦缘膶ο蟛僮飨到y(tǒng)的文件構(gòu)成工智能和算法分析的模型表示以及數(shù)據(jù)庫系統(tǒng)的信息組織形式等線性結(jié)構(gòu)難以把其中的邏輯關(guān)系表達出來須借助于數(shù)和圖這樣的非線性結(jié)構(gòu)此在以模擬客觀世界問題決客觀世界問題為主要任務(wù)的計算機領(lǐng)域中樹型結(jié)構(gòu)是信息的一種重要組織形式著廣泛應(yīng)用。在樹型結(jié)構(gòu)的應(yīng)用中又以二叉樹最為常用。二叉樹是一種非常重要的非線性結(jié)構(gòu)描述的數(shù)據(jù)有明顯的層次關(guān)系中的每個元素只有一個前驅(qū)叉樹是最為常用的數(shù)據(jù)結(jié)構(gòu)的實際應(yīng)用非常廣泛，二叉樹的遍歷方式有三種，前序遍歷，中序遍歷，后序遍歷，先序遍歷的順序為NLR先結(jié)點后左子樹子樹序遍歷順序為LNR左子樹，然后根結(jié)點，右子樹；后序遍歷順序為：LRN先左子樹，然后右子樹，根結(jié)點。由前序和中序遍歷中序和后序遍歷序列可以唯一確定一棵二叉樹于給幾個數(shù)據(jù)的排序或在已知的幾個數(shù)據(jù)中進行查找樹均能提供一種十分有效的方法，比如在查找問題上，任何借助于比較法查找長度為Ⅳ的一個序表的算法，都可以表示成一株二叉樹之何二叉樹都對應(yīng)一個查找有序表的有效方法根據(jù)樹的數(shù)學(xué)理論于算法分析的某些最有啟發(fā)性的應(yīng)用與給出用于計算各種類型中不同樹的數(shù)目的公式有關(guān)的。本文對二叉樹以及二叉樹的各種功能做介紹以及寫出一些基本的程序們對二叉樹的理解有更好的效果。關(guān)鍵詞：二叉樹的遍歷；左子樹；右子樹；遞歸

目錄1.問概述1.1題描述1.2求分析1.3計內(nèi)容和要求1.4程圖及結(jié)構(gòu)圖2.概設(shè)計2.1據(jù)結(jié)構(gòu)設(shè)計：52.2程序代碼3.調(diào)分析133.1試中的問題134.測結(jié)果14總結(jié)17參考文獻18

1.問概述1.1問題述創(chuàng)建二叉樹并遍歷基本要求：該程序集成了如下功能：）二叉樹的建立）遞歸和非遞歸先序，中序和后序遍歷二叉樹）按層次遍歷二叉樹）交換二叉樹的左右子樹）輸出葉子結(jié)點）遞歸和非遞歸計算葉子結(jié)點的數(shù)目1.2需求析分先序遍歷，中序遍歷和后序遍歷三種情況考慮。1.先序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否則結(jié)束操作：①②③

訪問根結(jié)點；按先序遍歷規(guī)則遍歷左子樹；按先序遍歷規(guī)則遍歷右子樹；2.中序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否則結(jié)束操作：①②③

按中序遍歷規(guī)則遍歷左子樹；訪問根結(jié)點；按中序遍歷規(guī)3歷右子樹。3.后序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否則結(jié)束操作：①②③

按后序遍歷規(guī)則遍歷左子樹；按后序遍歷規(guī)則遍歷右子樹；訪問根結(jié)點。

1.3設(shè)計容要對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存貯結(jié)構(gòu)，并利用棧的五種基本運算（清空堆棧、壓棧、彈出、取棧頂元素、判棧空）實現(xiàn)二叉樹的先序、中序、后序三種周游，輸出三種周游的結(jié)果。1.4流程及構(gòu)i=0NOYES

i<n

NO

YESroot=newNodeMultiplexi++returnroot圖流程圖

a

c

ef圖1.2二叉鏈表存儲結(jié)構(gòu)模擬圖2.概設(shè)計2.1數(shù)據(jù)構(gòu)計二叉樹結(jié)點數(shù)據(jù)類型定義為：template<typenameT>structBiNode{BiNode<T>*rchild,*lchild;//指向左孩子的指針data;//結(jié)點數(shù)據(jù)信息};二叉樹數(shù)據(jù)類型定義為：template<typenameT>class{template<typenameT>friend&operator<<(ostream&osBiTree();//參構(gòu)造函數(shù)BiTree(intm){};//參空構(gòu)造函數(shù)BiTree(Tnum,Tnone);//有參構(gòu)造函數(shù)

&bt);publi

BiTree();//構(gòu)函數(shù)遞歸前序遍歷inorder();//遞歸中序遍歷postorder();//歸后續(xù)遍歷levelorder();//序遍歷intcount();//計算二叉樹的結(jié)點數(shù)&os);//打印二叉樹，有層次計算一層結(jié)點數(shù)PreOrder();//非遞歸前序遍歷遞歸后序遍歷創(chuàng)建二叉樹protected://下函數(shù)供上面函數(shù)調(diào)用應(yīng)相同功能建刪除BiNode<T>Build(Tnum,Tnone,int數(shù)樹PreOrder(BiNode<T>*root);//前序遍歷root);//后續(xù)遍歷root);//層序遍歷root);//遞歸前序遍歷inorder(BiNode<T>*root);//遞歸中序遍歷postorder(BiNode<T>*root);//遞歸后續(xù)遍歷序遍歷intcount(BiNode<T>*root);//計算結(jié)點數(shù)display(ostream&root,int印staticboolvb,private:BiNode<T>};

2.2源程代<iostream>usingnamespacestd;叉樹結(jié)點類的定義T>{*Lchild,*Rchild;BTNode(TT(),BTNode<T>*leftNodeNULL,BTNode<T>*rightNode=NULL可選擇參數(shù)的默認構(gòu)造函數(shù)};叉樹的建立template<classT>*&root){p=root;{

}{BTNode<T>();=createBinTree(root->Lchild);createBinTree(root->Rchild);}}叉樹的先序遍歷template<classT>*&{if(p){cout<<p->data<<"preOrder(p->Rchild);}}叉樹的中序遍歷template<classT>*&{if(p){

cout<<p->data<<"}}叉樹的后序遍歷template<classT>*&p){if(p){levelOrder(p->Rchild);cout<<p->data<<"}}計二叉樹中結(jié)點的個數(shù)T>intcountNode(BTNode<T>*&{if(preturnreturn}二叉樹的深度T>

int*&{if(preturninth1=depth(p->Lchild);inth2=depth(p->Rchild);(h1+1);return}叉樹的消毀操作T>p)消毀函數(shù)，用來消毀二叉樹中的各個結(jié)點{if(p){returnreturndestroy(p->Rchild);deletep;}}函數(shù)的設(shè)計int{rootNodeintchoiced0;while(true){

system("cls");cout<<"\n\n\n---主界面-、創(chuàng)建二叉樹2先序遍歷二叉樹\n";、中序遍歷二叉樹4后序遍歷二叉樹\n";、統(tǒng)計結(jié)點總數(shù)6查看樹深度、消毀二叉樹0退出\n\n";if(choiced0)return0;if(choiced1){

請選擇操作：";system("cls");請輸入每個結(jié)點，回車確認，并以束：createBinTree(rootNode);}if(choiced2){system("cls");先序遍歷二叉樹結(jié)果：\n";preOrder(rootNode);}if(choiced3){system("cls");中序遍歷二叉樹結(jié)果：\n";

}if(choiced4){system("cls");后序遍歷二叉樹結(jié)果：\n";}if(choiced5){system("cls");intcount=二叉樹中結(jié)點總數(shù)為"}if(choiced6){system("cls");此二叉樹的深度為"}if(choiced7){system("cls");二叉樹已被消毀！\n";}

{system("cls");cout<<"\n\n\n\n\n\t錯誤選擇！\n";}}}3.調(diào)分析3.1調(diào)試的題創(chuàng)建二叉樹：依次輸入二叉樹前序遍歷序列，構(gòu)建相應(yīng)的二叉樹。二叉樹遍歷：遞歸算法、非遞歸算法測試，調(diào)用相應(yīng)函數(shù)進行測試，結(jié)果正確。求二叉樹深度和結(jié)點數(shù)一個二叉樹相關(guān)函數(shù)結(jié)果正確計算每層結(jié)點數(shù)：調(diào)用函數(shù)，測試結(jié)果正確。調(diào)試時遇到諸多問題，其中最主要的問題是死循環(huán)問題，在非遞歸遍歷時，容易進入死循環(huán)，經(jīng)過查找資料、分步調(diào)試最終找到循環(huán)結(jié)束條件，順利解決各個難題。

4.測結(jié)果（1）初始界面主界面所包含的內(nèi)容圖4.1始界面圖）運行結(jié)果：進行操作1輸入每個結(jié)點，顯示結(jié)果如下

圖4.2建二叉樹進行操作2執(zhí)行結(jié)果如下：圖4.3叉樹先序遍歷進行操作3執(zhí)行結(jié)果如下：

圖4.4叉樹中序遍歷進行操作4執(zhí)行結(jié)果如下：圖4.5二叉樹后序遍進行操作5執(zhí)行結(jié)果如下：

圖4.6計二叉樹節(jié)點進行操作6執(zhí)行結(jié)果如下：圖4.7看樹深度總結(jié)要能很好的掌握編,僅僅通過幾個簡單的程序的編寫時無法達成,更要大量積累和深入才可能通過本次課程設(shè)計個課題的所有知識不僅僅是在課本上閱一些資料能夠更好的完成課題需要一種能力學(xué)能力。本次課程設(shè)計還讓我認識到自己的缺點次選的課題是二叉樹的遍歷為本學(xué)期所學(xué)的就是二叉樹等數(shù)據(jù)結(jié)構(gòu)，所以認為