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

1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)三題目1二叉樹姓名： 班級(jí)： 班內(nèi)序號(hào)：學(xué)號(hào)： 2013210465 1實(shí)驗(yàn)要求根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉樹。 二叉樹的基本功能：1、二叉樹的建立2、前序遍歷二叉樹3、中序遍歷二叉樹4、后序遍歷二叉樹5、按層序遍歷二叉樹6、求二叉樹的深度7、求指定結(jié)點(diǎn)到根的路徑8、二叉樹的銷毀9、其他：自定義操作編寫測(cè)試main()函數(shù)測(cè)試線性表的正確性2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu)lch data rch使用二叉鏈表實(shí)現(xiàn)二叉樹的存儲(chǔ)，其示意圖如下圖所示： data rchlch data data data 2.2

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

3、der(BiNode*R) if(R!=NULL) Postorder(R-lchild); /遍歷左子樹 Postorder(R-rchild); /遍歷右子樹 coutdata; /訪問結(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) /求二叉樹的深度 if (R=NULL) /如果二叉樹為空，返回0return d; if (R-lch=NULL)&(R-rch=NULL) /如果二叉樹沒有孩子，返回二叉樹深度return d+1; else /如果二叉樹有孩子，做遞歸循環(huán)，并返回二叉樹的最長(zhǎng)路徑，即二叉樹深度 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） 求二叉樹深度：O（n)3. 程序運(yùn)行結(jié)果3.1 測(cè)試主函數(shù)流程 開始創(chuàng)建字符數(shù)組創(chuàng)建二叉樹前序遍歷中序遍歷后序遍歷層序遍歷求二叉樹深度求指定結(jié)點(diǎn)到二叉樹根節(jié)點(diǎn)路徑結(jié)束 4. 總結(jié)該次試驗(yàn)中，二叉樹的建立，前序遍

6、歷，中序遍歷，后序遍歷，求二叉樹的深度以及二叉樹的銷毀都涉及到遞歸函數(shù)的巧妙應(yīng)用。二叉樹的層序遍歷則利用“隊(duì)”的概念來實(shí)現(xiàn)根節(jié)點(diǎn)入隊(duì)，出隊(duì)，并讓其孩子按順序入隊(duì)。個(gè)人覺得最難的部分莫過于求指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑。對(duì)于尋找指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑，首先覺得應(yīng)該是一個(gè)一個(gè)節(jié)點(diǎn)地尋找，直到找到要求的結(jié)點(diǎn)，尋找過程即用到二叉樹的遍歷，比如該實(shí)驗(yàn)中用到的前序遍歷；再者，關(guān)于路徑，想到“迷宮問題”，即使用“?！贝鎯?chǔ)尋找到指定結(jié)點(diǎn)的正確路徑，并一一出棧，就可得到指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑。對(duì)于編程，有些巧妙而經(jīng)典的方法需要記憶，獨(dú)自想出每種問題的算法比較困難，也浪費(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)建二叉樹void Release(BiNode*R);/釋放二叉樹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) /表示位置，從開始，表示數(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)建左子樹Create(R-rchild,data,2*i+1,n); /創(chuàng)建右子樹else R=NULL;templateBiTree:BiTree(T data,int n)Create(root,data,1,n);/前序遍歷templatevoid BiTree:Preorder(BiNode*R)if(R!=NULL)coutdata; /訪問節(jié)點(diǎn)Preorder(R-lchild); /遍歷左子樹Preorder(R-rchild); /遍歷右子樹/中序遍歷templatevoid BiTre

10、e:Inorder(BiNode*R)if(R!=NULL)Inorder(R-lchild); /遍歷左子樹coutdata; /訪問結(jié)點(diǎn)Inorder(R-rchild); /遍歷右子樹/后序遍歷templatevoid BiTree:Postorder(BiNode*R)if(R!=NULL)Postorder(R-lchild); /遍歷左子樹Postorder(R-rchild); /遍歷右子樹coutdata; /訪問結(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); 釋放左子樹Release(R-rchild); /釋放右子樹delete R; /釋放根節(jié)點(diǎn)/釋放二叉樹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