數(shù)據(jù)結(jié)構(gòu)實驗報告三二叉樹.docx

數(shù) 據(jù) 結(jié) 構(gòu)實驗報告實驗名稱： 實驗四 題目1 用二叉鏈表實現(xiàn)一個二叉樹學(xué)生姓名： 班 級： 2013211128班內(nèi)序號： 學(xué) 號： 2013210771日 期： 2014/12/051. 實驗?zāi)康恼莆斩鏄浠静僮鞯膶崿F(xiàn)方法根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實現(xiàn)一個二叉樹。二叉樹的基本功能：1、二叉樹的建立2、前序遍歷二叉樹3、中序遍歷二叉樹4、后序遍歷二叉樹5、按層序遍歷二叉樹6、求二叉樹的深度7、求指定結(jié)點到根的路徑8、二叉樹的銷毀9、其他：自定義操作編寫測試 main()函數(shù)測試二叉樹的正確性2. 程序分析2.1 存儲結(jié)構(gòu)采用二叉樹的存儲結(jié)構(gòu)，其中每個二叉樹的結(jié)點定義了一個結(jié)構(gòu)體，該結(jié)構(gòu)體包含三個元素，分別是一個T類型的數(shù)據(jù)域data，一個指向T類型的指針左孩子，一個指向T類型的指針右孩子。在對二叉樹的關(guān)鍵算法的實現(xiàn)過程中，采用了隊列的存儲結(jié)構(gòu)。對于二叉樹中每個結(jié)點的data域的賦值，我們事先把這些data儲存在一個數(shù)組中，通過對數(shù)組元素的調(diào)用事先對二叉樹中每個結(jié)點的data域的賦值。2.2 關(guān)鍵算法分析2.2.1二叉樹的建立：A 自然語言描述：1 首先判斷調(diào)用的數(shù)組是否為空，如果為空，直接將一個已經(jīng)初始化好的根節(jié)點置為空。2 如果該數(shù)組不為空，則把調(diào)用的數(shù)組的第一個元素的賦給根節(jié)點的data域。3 采用遞歸的思想，分別將根節(jié)點的左右孩子作為根節(jié)點，遞歸調(diào)用該函數(shù)。完成對左右子樹的賦值。時間復(fù)雜度：O（1）B 代碼詳細分析：templatevoid Bitree:create(Binode*&R,T data,int i)/創(chuàng)建二叉樹if(datai-1!=0)R=new Binode; /創(chuàng)建根結(jié)點R-data=datai-1;R-lch=R-rch=NULL;create(R-lch,data,2*i); /創(chuàng)建左子樹create(R-rch,data,2*i+1); /創(chuàng)建右子樹template Bitree:Bitree(T data)create(root,data,1); /create root2.2.2前序遍歷二叉樹：A. 自然語言描述：1：判斷根節(jié)點是否為空2：輸出它的data域3：遍歷左子樹4：遍歷右子樹時間復(fù)雜度：O（1）B.代碼詳細分析：template void Bitree:preorder(Binode*R) /前序遍歷if(R!=NULL)coutdata; /訪問結(jié)點preorder(R-lch); /遍歷左子樹preorder(R-rch); /遍歷右子樹 2.2.3中序遍歷二叉樹：A.自然語言描述：1：判斷根節(jié)點是否為空2：遍歷左子樹3：訪問結(jié)點4：遍歷右子樹時間復(fù)雜度：O（1）B. 代碼詳細分析：template void Bitree:Inorder(Binode*R) /中序遍歷if(R!=NULL)Inorder(R-lch); /遍歷左子樹coutdata; /訪問結(jié)點Inorder(R-rch); /遍歷右子樹2.2.4后序遍歷二叉樹：A.自然語言描述：1：判斷根節(jié)點是否為空2：遍歷左子樹3：遍歷右子樹4：訪問結(jié)點時間復(fù)雜度：O（1）B.代碼詳細分析：template void Bitree:Postorder(Binode*R) /后序遍歷if(R!=NULL)Postorder(R-lch); /遍歷左子樹Postorder(R-rch); /遍歷右子樹coutdata; /訪問結(jié)點2.2.5層序遍歷二叉樹：A.自然語言描述：1：初始化空隊列2：根結(jié)點入隊3：隊頭元素出隊4：出隊打印5：左孩子入隊6：右孩子入隊時間復(fù)雜度：O（1）B.代碼詳細分析：templatevoid Bitree:Levelorder(Binode*R) /層序遍歷Binode* queue10000;int f=0,r=0; /初始化空隊列if(R!=NULL)queue+r=R; /根結(jié)點入隊while(f!=r)Binode*p=queue+f; /隊頭元素出隊coutdata; /出隊打印if(p-lch!=NULL)queue+r=p-lch; /左孩子入隊if(p-rch!=NULL)queue+r=p-rch; /右孩子入隊2.2.6求二叉樹的深度：時間復(fù)雜度：O（1）代碼詳細分析：template int Bitree:Depth(Binode *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 nm? n:m;2.2.7求指定結(jié)點到根的路徑時間復(fù)雜度：O（n）代碼詳細分析：templatevoid Bitree:path(Binode* root,char m) /求路徑Binode* stack10000;Binode*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 路徑: ;for(int i=1;i =top;i+)coutdata;break;top-;Elses=stacktop;if(top 0)s=s-rch;tagtop=1;while(s!=NULL|top!=0);2.2.8銷毀二叉樹時間復(fù)雜度：O（1）詳細代碼分析：template void Bitree:Destroy(Binode *R) /銷毀二叉樹if (R!=NULL)Destroy(R-lch);Destroy(R-rch);delete R;template Bitree:Bitree()/銷毀根結(jié)點Destroy(root); 3.程序運行結(jié)果實現(xiàn)了二叉樹的功能4.總結(jié)對二叉樹的操作上，前序遍歷，中序遍歷，后續(xù)遍歷，層序遍歷，求二叉樹深度等函數(shù)采用了遞歸算法。為了提高運算性能，可以將它們改為非遞歸算法來實現(xiàn)，對于比較復(fù)雜的算法，遞歸和非遞歸的運算時間復(fù)雜度差別較大。在實驗中我掌握二叉樹基本操作的實現(xiàn)方法，并且根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實現(xiàn)一個二叉樹。源程序：#include using namespace std; template struct Binode T data; Binode *lch; Binode *rch; ; templateclass Bitree private: void create(Binode*&R,T data,int i); /創(chuàng)建二叉樹 void Destroy(Binode *R); public: Binode*root; /根結(jié)點 Bitree(T data); /構(gòu)造函數(shù) Bitree(); void preorder(Binode*R); /前序遍歷 void Inorder(Binode*R); /中序遍歷 void Postorder(Binode*R); /后序遍歷 void Levelorder(Binode*R); /層序遍歷 /*void find(T data);*/ int Depth(Binode *R,int d); /深度 void path(Binode* root,char); Bitree(); /析構(gòu)函數(shù); templatevoid Bitree:create(Binode*&R,T data,int i) /創(chuàng)建二叉樹 if(datai-1!=0) R=new Binode; /創(chuàng)建根結(jié)點 R-data=datai-1; R-lch=R-rch=NULL; create(R-lch,data,2*i); /創(chuàng)建左子樹 create(R-rch,data,2*i+1); /創(chuàng)建右子樹 template Bitree:Bitree(T data) create(root,data,1); /create root template void Bitree:preorder(Binode*R) /前序遍歷 if(R!=NULL) coutdata; /訪問結(jié)點 preorder(R-lch); /遍歷左子樹 preorder(R-rch); /遍歷右子樹 template void Bitree:Inorder(Binode*R) /中序遍歷 if(R!=NULL) Inorder(R-lch); /遍歷左子樹 coutdata; /訪問結(jié)點 Inorder(R-rch); /遍歷右子樹 template void Bitree:Postorder(Binode*R) /后序遍歷 if(R!=NULL) Postorder(R-lch); /遍歷左子樹 Postorder(R-rch); /遍歷右子樹 coutdata; /訪問結(jié)點 template void Bitree:Levelorder(Binode*R) /層序遍歷 Binode* queue10000; int f=0,r=0; /初始化空隊列 if(R!=NULL) queue+r=R; /根結(jié)點入隊 while(f!=r) Binode*p=queue+f; /隊頭元素出隊 coutdata; /出隊打印 if(p-lch!=NULL) queue+r=p-lch; /左孩子入隊 if(p-rch!=NULL) queue+r=p-rch; /右孩子入隊 template void Bitree:Destroy(Binode *R) /銷毀二叉樹 if (R!=NULL) Destroy(R-lch); Destroy(R-rch); delete R; template Bitree:Bitree() /銷毀根結(jié)點 Destroy(root); template int Bitree:Depth(Binode *R,int d) /深度 if (R=NULL) return d; 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 nm? n:m; template void Bitree:path(Binode* root,char m) /求路徑 Binode* stack10000; Binode*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+) coutdata; break; top-; els s=stacktop; if(top 0) s=s-rch; tagtop=1; while(s!=NULL|top!=0); void main() char buf400=0; for(int i = 0;i15;i+) bufi = i+65; Bitree ChBiTree(buf); cout前序遍歷是endl; ChBiTree.preorder(ChBiTree.root); coutendl; cout中序遍歷是