數(shù)據(jù)結構課程設計二叉樹的遍歷

1、摘要針對現(xiàn)實世界中許多關系復雜的數(shù)據(jù)，如人類社會的家譜，各種社會組織機構,博弈交通等復雜事物或過程以及客觀世界中廣泛存在的具有分支關系或層次特性的對象如操作系統(tǒng)的文件構成、人工智能和算法分析的模型表示以及數(shù)據(jù)庫系統(tǒng)的信息組織形式等，用線性結構難以把其中的邏輯關系表達出來，必須借助于數(shù)和圖這樣的非線性結構，因此在以模擬客觀世界問題，解決客觀世界問題為主要任務的計算機領域中樹型結構是信息的一種重要組織形式，樹有著廣泛應用。在樹型結構的應用中又以二叉樹最為常用。二叉樹是一種非常重要的非線性結構，所描述的數(shù)據(jù)有明顯的層次關系，其中的每個元素只有一個前驅，二叉樹是最為常用的數(shù)據(jù)結構，它的實際應用非常廣泛

2、，二叉樹的遍歷方式有三種，前序遍歷，中序遍歷，后序遍歷，先序遍歷的順序為：NLR先根結點，然后左子樹，右子樹；中序遍歷順序為；LNR先左子樹，然后根結點，右子樹；后序遍歷順序為：LRN先左子樹，然后右子樹，根結點。由前序和中序遍歷，有中序和后序遍歷序列可以唯一確定一棵二叉樹。對于給幾個數(shù)據(jù)的排序或在已知的幾個數(shù)據(jù)中進行查找，二叉樹均能提供一種十分有效的方法，比如在查找問題上，任何借助于比較法查找長度為的一個序表的算法，都可以表示成一株二叉樹。反之，任何二叉樹都對應一個查找有序表的有效方法根據(jù)樹的數(shù)學理論，對于算法分析的某些最有啟發(fā)性的應用，是與給出用于計算各種類型中不同樹的數(shù)目的公式有關的。本

3、文對二叉樹以及二叉樹的各種功能做介紹以及寫出一些基本的程序，讓我們對二叉樹的理解有更好的效果。關鍵詞：二叉樹的遍歷；左子樹；右子樹；遞歸I目錄1.問題概述31.1問題描述31.2需求分析31.3設計內容和要求31.4流程圖及結構圖32.概要設計32.1數(shù)據(jù)結構設計：32.2源程序代碼33.調試分析33.1調試中的問題34.測試結果3總結3參考文獻3181.問題概述1.1問題描述創(chuàng)建二叉樹并遍歷 基本要求： 該程序集成了如下功能：（1）二叉樹的建立（2）遞歸和非遞歸先序，中序和后序遍歷二叉樹（3）按層次遍歷二叉樹（4）交換二叉樹的左右子樹（5）輸出葉子結點（6）遞歸和非遞歸計

4、算葉子結點的數(shù)目1.2需求分析分先序遍歷，中序遍歷和后序遍歷三種情況考慮。1. 先序遍歷，當二叉樹非空時按以下順序遍歷，否則結束操作：1 訪問根結點；2 按先序遍歷規(guī)則遍歷左子樹；3 按先序遍歷規(guī)則遍歷右子樹；2. 中序遍歷，當二叉樹非空時按以下順序遍歷，否則結束操作：1 按中序遍歷規(guī)則遍歷左子樹；2 訪問根結點；3 按中序遍歷規(guī)3遍歷右子樹。3. 后序遍歷，當二叉樹非空時按以下順序遍歷，否則結束操作：1 按后序遍歷規(guī)則遍歷左子樹；2 按后序遍歷規(guī)則遍歷右子樹；3 訪問根結點。1.3設計內容和要求對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存貯結構，并利用棧的五種基本運算（清空堆棧、壓棧、

5、彈出、取棧頂元素、判棧空）實現(xiàn)二叉樹的先序、中序、后序三種周游，輸出三種周游的結果。1.4流程圖及結構圖YESYESNONO開始i=0i<nbtreetypenewNodeMultiplexroot=newNodei+結束是否為空returnroot圖1.1 流程圖 b c d e f a圖1.2二叉鏈表存儲結構模擬圖2.概要設計2.1數(shù)據(jù)結構設計：1 二叉樹結點數(shù)據(jù)類型定義為： template <typename T> struct BiNode  BiNode<T>*rchild

6、,*lchild;/指向左孩子的指針T data;/結點數(shù)據(jù)信息  2 二叉樹數(shù)據(jù)類型定義為： template <typename T> class BiTree  template <typename T> friend ostream & operator <<(ostream &os ,BiTree<T> &

7、bt); public: BiTree();/無參構造函數(shù) BiTree(int m);/有參空構造函數(shù) BiTree(T ary,int num,T none);/有參構造函數(shù)  BiTree();/析構函數(shù) void preorder();/遞歸前序遍歷  void inorder();/遞歸中序遍歷  void postorder();/遞歸后續(xù)遍歷 void levelorder();/層

8、序遍歷 int  count();/計算二叉樹的結點數(shù)  void display(ostream &os);/打印二叉樹，有層次  void LevelNum();/計算每一層結點數(shù)  void PreOrder();/非遞歸前序遍歷  void PostOrder();/非遞歸后序遍歷  void creat();/創(chuàng)建二叉樹 protected: /以下函數(shù)供上面函數(shù)調用&

9、#160; /對應相同功能 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)建二叉樹  void PreOrder(BiNode<T>* root);/前序遍歷 &

10、#160;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>

11、* root);/遞歸后續(xù)遍歷  void levelorder(BiNode<T>*root);/層序遍歷  int count(BiNode<T>* root);/計算結點數(shù)   void display(ostream& os,BiNode<T>* root,int dep);/打印 static bool leastCommanAncestor(BiNode<

12、T> *root, T va, T vb, BiNode<T>                       private:BiNode<T> *rootptr; 2.2源程序代碼#include <iostream>using namespace

13、 std;/*/二叉樹結點類的定義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ù)的默認構造函數(shù);/*/二叉樹的建立template <class T>void create

14、BinTree(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); /*/二叉樹的先序遍歷template <cla

15、ss T>void preOrder( BTNode<T> * & p) if(p) cout<<p->data<<" " preOrder(p->Lchild); preOrder(p->Rchild); /*/二叉樹的中序遍歷template <class T>void inOrder(BTNode<T> * & p) if(p) inOrder(p->Lchild); cout<<p->data<<" " inOr

16、der(p->Rchild); /*/二叉樹的后序遍歷template <class T>void levelOrder(BTNode<T> *& p) if(p) levelOrder(p->Lchild); levelOrder(p->Rchild); cout<<p->data<<" " /*/統(tǒng)計二叉樹中結點的個數(shù)template<class T>int countNode(BTNode<T> * & p) if(p = NULL) return 0; r

17、eturn 1+countNode(p->Lchild)+countNode(p->Rchild);/*/求二叉樹的深度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;/*/二叉樹的消毀操作template<class T>BTNode<T>* d

18、estroy(BTNode<T>* p) /消毀函數(shù)，用來消毀二叉樹中的各個結點 if(p) return destroy(p->Lchild); return destroy(p->Rchild); delete p; /*/主函數(shù)的設計 int main () BTNode<int> * rootNode = NULL; int choiced = 0; while(true) system("cls"); cout<<"nnn -主界面-nnn" cout<<" 1、創(chuàng)建二叉樹

19、2、先序遍歷二叉樹n" cout<<" 3、中序遍歷二叉樹 4、后序遍歷二叉樹n" cout<<" 5、統(tǒng)計結點總數(shù) 6、查看樹深度 n" cout<<" 7、消毀二叉樹 0、退出nn" cout<<" 請選擇操作：" cin>>choiced; if(choiced = 0) return 0; else if(choiced = 1) system("cls"); cout<<"請輸入每個結點，回車確

20、認，并以-1結束：n" createBinTree(rootNode ); else if(choiced = 2) system("cls"); cout<<"先序遍歷二叉樹結果：n" preOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 3) system("cls"); cout<<"中序遍歷二叉樹結果：n" inOrder(rootNode); cout<&

21、lt;endl; system("pause"); else if(choiced = 4) system("cls"); cout<<"后序遍歷二叉樹結果：n" levelOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 5) system("cls"); int count = countNode(rootNode); cout<<"二叉樹中結點總數(shù)為"<

22、;<count<<endl; system("pause"); else if(choiced = 6) system("cls"); int dep = depth(rootNode); cout<<"此二叉樹的深度為"<<dep<<endl; system("pause"); else if(choiced = 7) system("cls"); cout<<"二叉樹已被消毀！n" destroy(rootNode); cout<<endl; system("pause"); else system("cls"); cout<<"nnnnnt錯誤選擇！n" 3.調試分析3.1調試中的問題創(chuàng)建二叉樹：依次輸入二叉樹前序遍歷序列，構建相應的二叉樹。 二叉樹遍歷：遞歸算法、非遞歸算法測試，調用相應函數(shù)