1、數 據 結 構實驗報告實驗名稱： 實驗四 題目1 用二叉鏈表實現一個二叉樹學生姓名： 班 級： 2013211128班內序號： 學 號： 2013210771日 期： 2014/12/051. 實驗目的掌握二叉樹基本操作的實現方法根據二叉樹的抽象數據類型的定義，使用二叉鏈表實現一個二叉樹。二叉樹的基本功能：1、二叉樹的建立2、前序遍歷二叉樹3、中序遍歷二叉樹4、后序遍歷二叉樹5、按層序遍歷二叉樹6、求二叉樹的深度7、求指定結點到根的路徑8、二叉樹的銷毀9、其他：自定義操作編寫測試 main()函數測試二叉樹的正確性2. 程序分析2.1 存儲結構采用二叉樹的存儲結構，其中每個二叉樹的結點定義了一

2、個結構體，該結構體包含三個元素，分別是一個T類型的數據域data，一個指向T類型的指針左孩子，一個指向T類型的指針右孩子。在對二叉樹的關鍵算法的實現過程中，采用了隊列的存儲結構。對于二叉樹中每個結點的data域的賦值，我們事先把這些data儲存在一個數組中，通過對數組元素的調用事先對二叉樹中每個結點的data域的賦值。2.2 關鍵算法分析2.2.1二叉樹的建立：A 自然語言描述：1 首先判斷調用的數組是否為空，如果為空，直接將一個已經初始化好的根節點置為空。2 如果該數組不為空，則把調用的數組的第一個元素的賦給根節點的data域。3 采用遞歸的思想，分別將根節點的左右孩子作為根節點，遞歸調用該

3、函數。完成對左右子樹的賦值。時間復雜度：O（1）B 代碼詳細分析：template<class T>void Bitree<T>:create(Binode<T>*&R,T data,int i)/創建二叉樹if(datai-1!=0)R=new Binode<T> /創建根結點R->data=datai-1;R->lch=R->rch=NULL;create(R->lch,data,2*i); /創建左子樹create(R->rch,data,2*i+1); /創建右子樹template <class

4、 T>Bitree<T>:Bitree(T data)create(root,data,1); /create root2.2.2前序遍歷二叉樹：A. 自然語言描述：1：判斷根節點是否為空2：輸出它的data域3：遍歷左子樹4：遍歷右子樹時間復雜度：O（1）B.代碼詳細分析：template <class T>void Bitree<T>:preorder(Binode<T>*R) /前序遍歷if(R!=NULL)cout<<R->data; /訪問結點preorder(R->lch); /遍歷左子樹preorder

5、(R->rch); /遍歷右子樹 2.2.3中序遍歷二叉樹：A.自然語言描述：1：判斷根節點是否為空2：遍歷左子樹3：訪問結點4：遍歷右子樹時間復雜度：O（1）B. 代碼詳細分析：template <class T>void Bitree<T>:Inorder(Binode<T>*R) /中序遍歷if(R!=NULL)Inorder(R->lch); /遍歷左子樹cout<<R->data; /訪問結點Inorder(R->rch); /遍歷右子樹2.2.4后序遍歷二叉樹：A.自然語言描述：1：判斷根節點是否為空2：遍歷左

6、子樹3：遍歷右子樹4：訪問結點時間復雜度：O（1）B.代碼詳細分析：template <class T>void Bitree<T>:Postorder(Binode<T>*R) /后序遍歷if(R!=NULL)Postorder(R->lch); /遍歷左子樹Postorder(R->rch); /遍歷右子樹cout<<R->data; /訪問結點2.2.5層序遍歷二叉樹：A.自然語言描述：1：初始化空隊列2：根結點入隊3：隊頭元素出隊4：出隊打印5：左孩子入隊6：右孩子入隊時間復雜度：O（1）B.代碼詳細分析：templat

7、e<class T>void Bitree<T>:Levelorder(Binode<T>*R) /層序遍歷Binode<T>* queue10000;int f=0,r=0; /初始化空隊列if(R!=NULL)queue+r=R; /根結點入隊while(f!=r)Binode<T>*p=queue+f; /隊頭元素出隊cout<<p->data; /出隊打印if(p->lch!=NULL)queue+r=p->lch; /左孩子入隊if(p->rch!=NULL)queue+r=p->r

8、ch; /右孩子入隊2.2.6求二叉樹的深度：時間復雜度：O（1）代碼詳細分析：template <class T>int Bitree<T>:Depth(Binode<T> *R,int d) /深度if (R=NULL) return d;if (R->lch=NULL) && (R->rch=NULL)return d+1;elseint m = Depth(R->lch,d+1);int n = Depth(R->rch,d+1);return n>m? n:m;2.2.7求指定結點到根的路徑時間復雜度：

9、O（n）代碼詳細分析：template<class T>void Bitree<T>:path(Binode<T>* root,char m) /求路徑Binode<T>* stack10000;Binode<T>*s;int tag10000;int top=0;s=root;dowhile(s!=NULL)top+;stacktop=s;tagtop=0;s=s->lch;if(top> 0)if(tagtop=1)if(stacktop->data=m)cout<< "路徑: "

10、for(int i=1;i <=top;i+)cout<<stacki->data;break;top-;Elses=stacktop;if(top> 0)s=s->rch;tagtop=1;while(s!=NULL|top!=0);2.2.8銷毀二叉樹時間復雜度：O（1）詳細代碼分析：template <class T>void Bitree<T>:Destroy(Binode<T> *R) /銷毀二叉樹if (R!=NULL)Destroy(R->lch);Destroy(R->rch);delete R

11、;template <class T>Bitree<T>:Bitree()/銷毀根結點Destroy(root); 3.程序運行結果實現了二叉樹的功能4.總結對二叉樹的操作上，前序遍歷，中序遍歷，后續遍歷，層序遍歷，求二叉樹深度等函數采用了遞歸算法。為了提高運算性能，可以將它們改為非遞歸算法來實現，對于比較復雜的算法，遞歸和非遞歸的運算時間復雜度差別較大。在實驗中我掌握二叉樹基本操作的實現方法，并且根據二叉樹的抽象數據類型的定義，使用二叉鏈表實現一個二叉樹。源程序：#include<iostream> using namespace std; templat

12、e<class T> struct Binode T data; Binode<T> *lch; Binode<T> *rch; ; template<class T>class Bitree private: void create(Binode<T>*&R,T data,int i); /創建二叉樹 void Destroy(Binode<T> *R); public: Binode<T>*root; /根結點 Bitree(T data); /構造函數 Bitree(); void preorde

13、r(Binode<T>*R); /前序遍歷 void Inorder(Binode<T>*R); /中序遍歷 void Postorder(Binode<T>*R); /后序遍歷 void Levelorder(Binode<T>*R); /層序遍歷 /*void find(T data);*/ int Depth(Binode<T> *R,int d); /深度 void path(Binode<T>* root,char); Bitree(); /析構函數; template<class T>void Bi

14、tree<T>:create(Binode<T>*&R,T data,int i) /創建二叉樹 if(datai-1!=0) R=new Binode<T> /創建根結點 R->data=datai-1; R->lch=R->rch=NULL; create(R->lch,data,2*i); /創建左子樹 create(R->rch,data,2*i+1); /創建右子樹 template <class T> Bitree<T>:Bitree(T data) create(root,data,

15、1); /create root template <class T> void Bitree<T>:preorder(Binode<T>*R) /前序遍歷 if(R!=NULL) cout<<R->data; /訪問結點 preorder(R->lch); /遍歷左子樹 preorder(R->rch); /遍歷右子樹 template <class T> void Bitree<T>:Inorder(Binode<T>*R) /中序遍歷 if(R!=NULL) Inorder(R->

16、lch); /遍歷左子樹 cout<<R->data; /訪問結點 Inorder(R->rch); /遍歷右子樹 template <class T> void Bitree<T>:Postorder(Binode<T>*R) /后序遍歷 if(R!=NULL) Postorder(R->lch); /遍歷左子樹 Postorder(R->rch); /遍歷右子樹 cout<<R->data; /訪問結點 template<class T> void Bitree<T>:Leve

17、lorder(Binode<T>*R) /層序遍歷 Binode<T>* queue10000; int f=0,r=0; /初始化空隊列 if(R!=NULL) queue+r=R; /根結點入隊 while(f!=r) Binode<T>*p=queue+f; /隊頭元素出隊 cout<<p->data; /出隊打印 if(p->lch!=NULL) queue+r=p->lch; /左孩子入隊 if(p->rch!=NULL) queue+r=p->rch; /右孩子入隊 template <class

18、T> void Bitree<T>:Destroy(Binode<T> *R) /銷毀二叉樹 if (R!=NULL) Destroy(R->lch); Destroy(R->rch); delete R; template <class T> Bitree<T>:Bitree() /銷毀根結點 Destroy(root); template <class T> int Bitree<T>:Depth(Binode<T> *R,int d) /深度 if (R=NULL) return d;

19、if (R->lch=NULL) && (R->rch=NULL) return d+1; else int m = Depth(R->lch,d+1); int n = Depth(R->rch,d+1); return n>m? n:m; template<class T> void Bitree<T>:path(Binode<T>* root,char m) /求路徑 Binode<T>* stack10000; Binode<T>*s; int tag10000; int top=0; s=root; do while(s!=NULL) top+; stacktop=s; tagtop=0; s=s->lch; if(top> 0) if(tagtop=1) if(stacktop->data=m) cout<< "路徑: " for(int i=1;i <=top;i+) cout<<stacki->data; break; top-; els s=stacktop; if(top> 0) s=s