北郵數(shù)據(jù)結(jié)構(gòu)第三次實(shí)驗(yàn)-二叉樹(shù)(修改)

1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)三題目1二叉樹(shù)姓名： 班級(jí)： 班內(nèi)序號(hào)：學(xué)號(hào)： 2013210465 1實(shí)驗(yà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、其他：自定義操作編寫(xiě)測(cè)試main()函數(shù)測(cè)試線性表的正確性2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu)lch data rch使用二叉鏈表實(shí)現(xiàn)二叉樹(shù)的存儲(chǔ)，其示意圖如下圖所示： data rchlch data data data 2.2

2、關(guān)鍵算法分析前序遍歷：訪問(wèn)根節(jié)點(diǎn)遍歷左子樹(shù)遍歷右子樹(shù)具體算法：templatevoid BiTree:PreOrder(BiNode* R)/前序遍歷if(R!=NULL)coutdata; /訪問(wèn)結(jié)點(diǎn)PreOrder(R-lch); /遍歷左子樹(shù)PreOrder(R-rch); /遍歷右子樹(shù)中序遍歷：templatevoid BiTree:Inorder(BiNode*R) if(R!=NULL) Inorder(R-lchild); /遍歷左子樹(shù) coutdata; /訪問(wèn)結(jié)點(diǎn) Inorder(R-rchild); /遍歷右子樹(shù) 后序遍歷templatevoid BiTree:Postor

3、der(BiNode*R) if(R!=NULL) Postorder(R-lchild); /遍歷左子樹(shù) Postorder(R-rchild); /遍歷右子樹(shù) coutdata; /訪問(wèn)結(jié)點(diǎn) 層序遍歷： templatevoid BiTree:LevelOrder(BiNode* R)/層序遍歷BiNode* queue100; /創(chuàng)建隊(duì)int f=0,r=0; /r為隊(duì)尾指針，f為對(duì)頭指針if(R!=NULL)queue+r=R; /頭結(jié)點(diǎn)入隊(duì)while(f!=r) /如果隊(duì)不為空，做此循環(huán)BiNode* p=queue+f; /出隊(duì)coutdata;if(p-lch!=NULL) /出

4、隊(duì)結(jié)點(diǎn)若有左右孩子，則左右孩子依次入隊(duì)queue+r=p-lch;if(p-rch!=NULL)queue+r=p-rch;求深度:template int BiTree:Depth(BiNode* R,int d) /求二叉樹(shù)的深度 if (R=NULL) /如果二叉樹(shù)為空，返回0return d; if (R-lch=NULL)&(R-rch=NULL) /如果二叉樹(shù)沒(méi)有孩子，返回二叉樹(shù)深度return d+1; else /如果二叉樹(shù)有孩子，做遞歸循環(huán)，并返回二叉樹(shù)的最長(zhǎng)路徑，即二叉樹(shù)深度 int m=GetDepth(R-lch,d+1); int n=GetDepth(R-rch,d

5、+1); return nm?n:m; 求路徑：templatebool BiTree:Getpath(BiNode*R,int d) if(R=NULL)return false; if(R-data=d|Getpath(R-lchild,d)|Getpath(R-rchild,d) coutdata ; return true; 時(shí)間復(fù)雜度: 前序遍歷：O（n） 層序遍歷：O（n） 求二叉樹(shù)深度：O（n)3. 程序運(yùn)行結(jié)果3.1 測(cè)試主函數(shù)流程 開(kāi)始創(chuàng)建字符數(shù)組創(chuàng)建二叉樹(shù)前序遍歷中序遍歷后序遍歷層序遍歷求二叉樹(shù)深度求指定結(jié)點(diǎn)到二叉樹(shù)根節(jié)點(diǎn)路徑結(jié)束 4. 總結(jié)該次試驗(yàn)中，二叉樹(shù)的建立，前序遍

6、歷，中序遍歷，后序遍歷，求二叉樹(shù)的深度以及二叉樹(shù)的銷毀都涉及到遞歸函數(shù)的巧妙應(yīng)用。二叉樹(shù)的層序遍歷則利用“隊(duì)”的概念來(lái)實(shí)現(xiàn)根節(jié)點(diǎn)入隊(duì)，出隊(duì)，并讓其孩子按順序入隊(duì)。個(gè)人覺(jué)得最難的部分莫過(guò)于求指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑。對(duì)于尋找指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑，首先覺(jué)得應(yīng)該是一個(gè)一個(gè)節(jié)點(diǎn)地尋找，直到找到要求的結(jié)點(diǎn)，尋找過(guò)程即用到二叉樹(shù)的遍歷，比如該實(shí)驗(yàn)中用到的前序遍歷；再者，關(guān)于路徑，想到“迷宮問(wèn)題”，即使用“?！贝鎯?chǔ)尋找到指定結(jié)點(diǎn)的正確路徑，并一一出棧，就可得到指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑。對(duì)于編程，有些巧妙而經(jīng)典的方法需要記憶，獨(dú)自想出每種問(wèn)題的算法比較困難，也浪費(fèi)時(shí)間，而借鑒一些經(jīng)典算法，有利于加快工作，也啟迪

7、我們一些算法的創(chuàng)新。所以，我們需要記憶一些經(jīng)典算法。源程序：#includeusing namespace std;templatestruct BiNodeT data;BiNode*lchild;BiNode*rchild;templateclass BiTreeprivate:void Create(BiNode*&R,T data,int i,int n);/創(chuàng)建二叉樹(shù)void Release(BiNode*R);/釋放二叉樹(shù)public:BiNode*root; /根節(jié)點(diǎn)BiTree(T data,int n); /構(gòu)造函數(shù)void Preorder(BiNode*R); /前序遍歷

8、void Inorder(BiNode*R); /中序遍歷void Postorder(BiNode*R); /后序遍歷void Leveorder(BiNode*R); /層序遍歷BiTree(); /析構(gòu)函數(shù) int Count(BiNode*R); /結(jié)點(diǎn)數(shù)bool Getpath(BiNode*R,int d); /路徑int GetDepth(BiNode*R,int d); /深度;templatevoid BiTree:Create(BiNode*&R,T data,int i,int n) /表示位置，從開(kāi)始，表示數(shù)組的長(zhǎng)度if(i=n)R=new BiNode; /創(chuàng)建根節(jié)點(diǎn)

9、R-data=datai-1;Create(R-lchild,data,2*i,n); /創(chuàng)建左子樹(shù)Create(R-rchild,data,2*i+1,n); /創(chuàng)建右子樹(shù)else R=NULL;templateBiTree:BiTree(T data,int n)Create(root,data,1,n);/前序遍歷templatevoid BiTree:Preorder(BiNode*R)if(R!=NULL)coutdata; /訪問(wèn)節(jié)點(diǎn)Preorder(R-lchild); /遍歷左子樹(shù)Preorder(R-rchild); /遍歷右子樹(shù)/中序遍歷templatevoid BiTre

10、e:Inorder(BiNode*R)if(R!=NULL)Inorder(R-lchild); /遍歷左子樹(shù)coutdata; /訪問(wèn)結(jié)點(diǎn)Inorder(R-rchild); /遍歷右子樹(shù)/后序遍歷templatevoid BiTree:Postorder(BiNode*R)if(R!=NULL)Postorder(R-lchild); /遍歷左子樹(shù)Postorder(R-rchild); /遍歷右子樹(shù)coutdata; /訪問(wèn)結(jié)點(diǎn)/層序遍歷templatevoid BiTree:Leveorder(BiNode*R)BiNode*queue100;int f=0;int r=0; /初始化

11、空隊(duì)列if(R!=NULL) queue+r=R; /根節(jié)點(diǎn)入隊(duì)while(f!=r)BiNode*p=queue+f; /對(duì)頭元素出隊(duì)coutdata; /出隊(duì)打印if(p-lchild!=NULL) queue+r=p-lchild; /左孩子入隊(duì)if(p-rchild!=NULL) queue+r=p-rchild; /右孩子入隊(duì)/析1函數(shù)templatevoid BiTree:Release(BiNode*R)if(R!=NULL)Release(R-lchild); 釋放左子樹(shù)Release(R-rchild); /釋放右子樹(shù)delete R; /釋放根節(jié)點(diǎn)/釋放二叉樹(shù)templat

12、eBiTree:BiTree()Release(root);/求結(jié)點(diǎn)總數(shù)templateint BiTree:Count(BiNode *R)if(R=NULL)return 0;elseint m=Count(R-lchild);int n=Count(R-rchild);return m+n+1;/求深度templateint BiTree:GetDepth(BiNode *R,int d)if(R=NULL)return d;if(R-lchild=NULL)&(R-rchild=NULL)return d+1;elseint m=GetDepth(R-lchild,d+1);int n

13、=GetDepth(R-rchild,d+1);return nm?n:m; /查詢結(jié)點(diǎn)路徑? templatebool BiTree:Getpath(BiNode*R,int d) if(R=NULL)return false;if(R-data=d|Getpath(R-lchild,d)|Getpath(R-rchild,d)coutdata ;return true;void main() char data50=abcdefgh;BiTreetree(data,8);cout前序遍歷為：;tree.Preorder(tree.root);coutendl;cout中序遍歷為：;tree.Inorder(tree.root);coutendl;cout后序遍歷為：;tree.Postorder(tree.root);coute