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

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