word摘要針對(duì)現(xiàn)實(shí)世界中許多關(guān)系復(fù)雜的數(shù)據(jù)，如人類(lèi)社會(huì)的家譜，各種社會(huì)組織機(jī)構(gòu),博弈交通等復(fù)雜事物或過(guò)程以與客觀世界中廣泛存在的具有分支關(guān)系或?qū)哟翁匦缘膶?duì)象如操作系統(tǒng)的文件構(gòu)成、人工智能和算法分析的模型表示以與數(shù)據(jù)庫(kù)系統(tǒng)的信息組織形式等，用線性結(jié)構(gòu)難以把其中的邏輯關(guān)系表達(dá)出來(lái)，必須借助于數(shù)和圖這樣的非線性結(jié)構(gòu)，因此在以模擬客觀世界問(wèn)題，解決客觀世界問(wèn)題為主要任務(wù)的計(jì)算機(jī)領(lǐng)域中樹(shù)型結(jié)構(gòu)是信息的一種重要組織形式，樹(shù)有著廣泛應(yīng)用。在樹(shù)型結(jié)構(gòu)的應(yīng)用中又以二叉樹(shù)最為常用。二叉樹(shù)是一種非常重要的非線性結(jié)構(gòu)，所描述的數(shù)據(jù)有明顯的層次關(guān)系，其中的每個(gè)元素只有一個(gè)前驅(qū)，二叉樹(shù)是最為常用的數(shù)據(jù)結(jié)構(gòu)，它的實(shí)際應(yīng)用非常廣泛，二叉樹(shù)的遍歷方式有三種，前序遍歷，中序遍歷，后序遍歷，先序遍歷的順序?yàn)椋篘LR先根結(jié)點(diǎn)，然后左子樹(shù)，右子樹(shù)；中序遍歷順序?yàn)椋籐NR先左子樹(shù)，然后根結(jié)點(diǎn)，右子樹(shù)；后序遍歷順序?yàn)椋篖RN先左子樹(shù)，然后右子樹(shù)，根結(jié)點(diǎn)。由前序和中序遍歷，有中序和后序遍歷序列可以唯一確定一棵二叉樹(shù)。對(duì)于給幾個(gè)數(shù)據(jù)的排序或在的幾個(gè)數(shù)據(jù)中進(jìn)展查找，二叉樹(shù)均能提供一種十分有效的方法，比如在查找問(wèn)題上，任何借助于比擬法查找長(zhǎng)度為的一個(gè)序表的算法，都可以表示成一株二叉樹(shù)。反之，任何二叉樹(shù)都對(duì)應(yīng)一個(gè)查找有序表的有效方法根據(jù)樹(shù)的數(shù)學(xué)理論，對(duì)于算法分析的某些最有啟發(fā)性的應(yīng)用，是與給出用于計(jì)算各種類(lèi)型中不同樹(shù)的數(shù)目的公式有關(guān)的。本文對(duì)二叉樹(shù)以與二叉樹(shù)的各種功能做介紹以與寫(xiě)出一些根本的程序，讓我們對(duì)二叉樹(shù)的理解有更好的效果。關(guān)鍵詞：二叉樹(shù)的遍歷；左子樹(shù)；右子樹(shù)；遞歸文案大全目錄3333332.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：33333總結(jié)3參考文獻(xiàn)3文案大全創(chuàng)建二叉樹(shù)并遍歷 根本要求： 該程序集成了如下功能：1二叉樹(shù)的建立2遞歸和非遞歸先序，中序和后序遍歷二叉樹(shù)3按層次遍歷二叉樹(shù)4交換二叉樹(shù)的左右子樹(shù)5輸出葉子結(jié)點(diǎn)6遞歸和非遞歸計(jì)算葉子結(jié)點(diǎn)的數(shù)目分先序遍歷，中序遍歷和后序遍歷三種情況考慮。1. 先序遍歷，當(dāng)二叉樹(shù)非空時(shí)按以下順序遍歷，否如此完畢操作： 訪問(wèn)根結(jié)點(diǎn)； 按先序遍歷規(guī)如此遍歷左子樹(shù)； 按先序遍歷規(guī)如此遍歷右子樹(shù)；2. 中序遍歷，當(dāng)二叉樹(shù)非空時(shí)按以下順序遍歷，否如此完畢操作： 按中序遍歷規(guī)如此遍歷左子樹(shù)； 訪問(wèn)根結(jié)點(diǎn)； 按中序遍歷規(guī)3遍歷右子樹(shù)。3. 后序遍歷，當(dāng)二叉樹(shù)非空時(shí)按以下順序遍歷，否如此完畢操作： 按后序遍歷規(guī)如此遍歷左子樹(shù)； 按后序遍歷規(guī)如此遍歷右子樹(shù)； 訪問(wèn)根結(jié)點(diǎn)。對(duì)任意給定的二叉樹(shù)頂點(diǎn)數(shù)自定建立它的二叉鏈表存貯結(jié)構(gòu)，并利用棧的五種根本運(yùn)算清空堆棧、壓棧、彈出、取棧頂元素、判?？諏?shí)現(xiàn)二叉樹(shù)的先序、中序、后序三種周游，輸出三種周游的結(jié)果。流程圖與結(jié)構(gòu)圖YESYESNONO圖1.1 流程圖2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：1 二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)類(lèi)型定義為： template <typename T> struct BiNode  BiNode<T>*rchild,*lchild;/指向左孩子的指針T data;/結(jié)點(diǎn)數(shù)據(jù)信息  2 二叉樹(shù)數(shù)據(jù)類(lèi)型定義為： template <typename T> class BiTree  template <typename T> friend ostream & operator <<(ostream &os ,BiTree<T> &bt); public: BiTree();/無(wú)參構(gòu)造函數(shù) BiTree(int m);/有參空構(gòu)造函數(shù) BiTree(T ary,int num,T none);/有參構(gòu)造函數(shù)  BiTree();/析構(gòu)函數(shù) void preorder();/遞歸前序遍歷  void inorder();/遞歸中序遍歷  void postorder();/遞歸后續(xù)遍歷 void levelorder();/層序遍歷 int  count();/計(jì)算二叉樹(shù)的結(jié)點(diǎn)數(shù)  void display(ostream &os);/打印二叉樹(shù)，有層次  void LevelNum();/計(jì)算每一層結(jié)點(diǎn)數(shù)  void PreOrder();/非遞歸前序遍歷  void PostOrder();/非遞歸后序遍歷  void creat();/創(chuàng)建二叉樹(shù) protected: /以下函數(shù)供上面函數(shù)調(diào)用  /對(duì)應(yīng)一樣功能 Voidcreat(BiNode<T>*&root);/創(chuàng)建  void release(BiNode<T>* &root);/刪除 BiNode<T> * Build(T ary,int num,T none,int idx);/用數(shù)組創(chuàng)建二叉樹(shù)  void PreOrder(BiNode<T>* root);/前序遍歷  void PostOrder(BiNode<T>* root);/后續(xù)遍歷  void LevelNum(BiNode<T>* root);/層序遍歷  void preorder(BiNode<T>* root);/遞歸前序遍歷  void inorder(BiNode<T>* root);/遞歸中序遍歷  void postorder(BiNode<T>* root);/遞歸后續(xù)遍歷  void levelorder(BiNode<T>*root);/層序遍歷  int count(BiNode<T>* root);/計(jì)算結(jié)點(diǎn)數(shù)   void display(ostream& os,BiNode<T>* root,int dep);/打印 static bool leastmanAncestor(BiNode<T> *root, T va, T vb, BiNode<T>                       private:BiNode<T> *rootptr; #include <iostream>using namespace std;/*/二叉樹(shù)結(jié)點(diǎn)類(lèi)的定義template<class T>struct BTNodeT data; BTNode <T> * Lchild,*Rchild; BTNode(T nodeValue = T(),BTNode<T>* leftNode = NULL,BTNode<T>* rightNode = NULL ) :data(nodeValue),Lchild(leftNode),Rchild(rightNode) /可選擇參數(shù)的默認(rèn)構(gòu)造函數(shù);/*/二叉樹(shù)的建立template <class T>void createBinTree(BTNode<T> * &root ) BTNode<T>* p = root; BTNode<T>* k; T nodeValue ; cin>>nodeValue; if(nodeValue=-1) root=NULL; else root=new BTNode<T>(); root->data = nodeValue; createBinTree(root->Lchild); createBinTree(root->Rchild); /*/二叉樹(shù)的先序遍歷template <class T>void preOrder( BTNode<T> * & p) if(p) cout<<p->data<<" " preOrder(p->Lchild); preOrder(p->Rchild); /*/二叉樹(shù)的中序遍歷template <class T>void inOrder(BTNode<T> * & p) if(p) inOrder(p->Lchild); cout<<p->data<<" " inOrder(p->Rchild); /*/二叉樹(shù)的后序遍歷template <class T>void levelOrder(BTNode<T> *& p) if(p) levelOrder(p->Lchild); levelOrder(p->Rchild); cout<<p->data<<" " /*/統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)template<class T>int countNode(BTNode<T> * & p) if(p = NULL) return 0; return 1+countNode(p->Lchild)+countNode(p->Rchild);/*/求二叉樹(shù)的深度template<class T>int depth(BTNode<T> *& p) if(p = NULL) return -1; int h1 = depth(p->Lchild); int h2 = depth(p->Rchild); if(h1>h2)return (h1+1); return h2+1;/*/二叉樹(shù)的消毀操作template<class T>BTNode<T>* destroy(BTNode<T>* p) /消毀函數(shù)，用來(lái)消毀二叉樹(shù)中的各個(gè)結(jié)點(diǎn) if(p) return destroy(p->Lchild); return destroy(p->Rchild); delete p; /*/主函數(shù)的設(shè)計(jì)int main () BTNode<int> * rootNode = NULL; int choiced = 0; while(true) system("cls"); cout<<"nnn -主界面-nnn" cout<<" 1、創(chuàng)建二叉樹(shù) 2、先序遍歷二叉樹(shù)n" cout<<" 3、中序遍歷二叉樹(shù) 4、后序遍歷二叉樹(shù)n" cout<<" 5、統(tǒng)計(jì)結(jié)點(diǎn)總數(shù) 6、查看樹(shù)深度 n" cout<<" 7、消毀二叉樹(shù) 0、退出nn" cout<<" 請(qǐng)選擇操作：" cin>>choiced; if(choiced = 0) return 0; else if(choiced = 1) system("cls"); cout<<"請(qǐng)輸入每個(gè)結(jié)點(diǎn)，回車(chē)確認(rèn)，并以-1完畢：n" createBinTree(rootNode ); else if(choiced = 2) system("cls"); cout<<"先序遍歷二叉樹(shù)結(jié)果：n" preOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 3) system("cls"); cout<<"中序遍歷二叉樹(shù)結(jié)果：n" inOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 4) system("cls"); cout<<"后序遍歷二叉樹(shù)結(jié)果：n" levelOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 5) system("cls"); int count = countNode(rootNode); cout<<"二叉樹(shù)中結(jié)點(diǎn)總數(shù)為"<<count<<endl; system("pause"); else if(choiced = 6) system("cls"); int dep = depth(rootNode); cout<<"此二叉樹(shù)的深度為"<<dep<<endl; system("pause"); else if(choiced = 7) system("cls"); cout<<"二叉樹(shù)已被消毀！n" destroy(rootNode); cout<<endl; system("pause"); else system("cls"); cout<<"nnnnnt錯(cuò)誤選擇！n" 創(chuàng)建二叉樹(shù)：依次輸入二叉樹(shù)前序遍歷序列，構(gòu)建相應(yīng)的二叉樹(shù)。 二叉樹(shù)遍歷：遞歸算法、非遞歸算法測(cè)試，調(diào)用相應(yīng)函數(shù)進(jìn)展測(cè)試，結(jié)果正確。 求二叉樹(shù)深度和結(jié)點(diǎn)數(shù)：創(chuàng)建一個(gè)二叉樹(shù)，調(diào)用相關(guān)函數(shù)，測(cè)試結(jié)果正確。 計(jì)算每層結(jié)點(diǎn)數(shù)：調(diào)用levelNum()函數(shù)，測(cè)試結(jié)果正確。  調(diào)試時(shí)遇到諸多問(wèn)題，其中最主要的問(wèn)題是死循環(huán)問(wèn)題，在非遞歸遍歷時(shí)，容易進(jìn)入死循環(huán)，經(jīng)過(guò)查找資料、分步調(diào)試最終找到循環(huán)完畢條件，順利解決各個(gè)難題。1初始界面:主界面所包含的內(nèi)容2運(yùn)行結(jié)果：進(jìn)展操作1，輸入每個(gè)結(jié)點(diǎn)，顯示結(jié)果如下進(jìn)展操作2，執(zhí)行結(jié)果如下：進(jìn)展操作3，執(zhí)行結(jié)果如下：進(jìn)展操作4，執(zhí)行結(jié)果如下：圖4.5二叉樹(shù)后序遍歷:進(jìn)展操作5，執(zhí)行結(jié)果如下：進(jìn)展操作6，執(zhí)行結(jié)果如下：總結(jié)要能很好的掌握編程,僅僅通過(guò)幾個(gè)簡(jiǎn)單的程序的編寫(xiě)時(shí)無(wú)法達(dá)成的,更需要大量積累和深入才可能通過(guò)本次課程設(shè)計(jì)。有關(guān)一個(gè)課題的所有知識(shí)不僅僅是在課本上，多查閱一些資料能夠更好的完成課題，這就需要一種能力，即自學(xué)能力。本次課程設(shè)計(jì)還讓我認(rèn)識(shí)到自己的缺點(diǎn)。本次選的課題是二叉樹(shù)的遍歷，因?yàn)楸緦W(xué)期所學(xué)的就是二叉樹(shù)等數(shù)據(jù)結(jié)構(gòu)，所以認(rèn)為比擬適合。剛開(kāi)始認(rèn)為會(huì)很簡(jiǎn)單，但到后來(lái)就出現(xiàn)一些難以解決的問(wèn)題，就像教師請(qǐng)教，并查閱相關(guān)資料。經(jīng)過(guò)慢慢的調(diào)試，最終測(cè)試成功。 這次課程設(shè)計(jì)讓我所學(xué)到的數(shù)據(jù)結(jié)構(gòu)知識(shí)發(fā)揮的淋漓盡致，而且還拓展了我的知識(shí)面，使我更加熟練的掌握各種方法。 總之，這次課程設(shè)計(jì)增強(qiáng)了我的自學(xué)能力，拓展了我的知識(shí)面，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)更加了解。參考文獻(xiàn)1 嚴(yán)蔚敏吳偉民數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)清華大學(xué)， 2009年9月2 譚浩強(qiáng)C程序設(shè)計(jì)(第三版)清華大學(xué) 2009年1月