北郵數(shù)據(jù)結構第三次實驗-二叉樹(修改)

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

2、關鍵算法分析前序遍歷：訪問根節(jié)點遍歷左子樹遍歷右子樹具體算法：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-

3、>lchild); /遍歷左子樹 cout<<R->data; /訪問結點 Inorder(R->rchild); /遍歷右子樹 后序遍歷template<class T>void BiTree<T>:Postorder(BiNode<T>*R) if(R!=NULL) Postorder(R->lchild); /遍歷左子樹 Postorder(R->rchild); /遍歷右子樹 cout<<R->data; /訪問結點 層序遍歷： template<class T>void BiT

4、ree<T>:LevelOrder(BiNode<T>* R)/層序遍歷BiNode<T>* queue100; /創(chuàng)建隊int f=0,r=0; /r為隊尾指針，f為對頭指針if(R!=NULL)queue+r=R; /頭結點入隊while(f!=r) /如果隊不為空，做此循環(huán)BiNode<T>* p=queue+f; /出隊cout<<p->data;if(p->lch!=NULL) /出隊結點若有左右孩子，則左右孩子依次入隊queue+r=p->lch;if(p->rch!=NULL)queue+r=p-

5、>rch;求深度:template<class T> int BiTree<T>:Depth(BiNode<T>* R,int d) /求二叉樹的深度 if (R=NULL) /如果二叉樹為空，返回0return d; if (R->lch=NULL)&&(R->rch=NULL) /如果二叉樹沒有孩子，返回二叉樹深度return d+1; else /如果二叉樹有孩子，做遞歸循環(huán)，并返回二叉樹的最長路徑，即二叉樹深度 int m=GetDepth(R->lch,d+1); int n=GetDepth(R->r

6、ch,d+1); return n>m?n:m; 求路徑：template<class T>bool BiTree<T>:Getpath(BiNode<T>*R,int d) if(R=NULL)return false; if(R->data=d|Getpath(R->lchild,d)|Getpath(R->rchild,d) cout<<R->data<<" " return true; 時間復雜度: 前序遍歷：O（n） 層序遍歷：O（n） 求二叉樹深度：O（n)3. 程序運行結

7、果3.1 測試主函數(shù)流程 開始創(chuàng)建字符數(shù)組創(chuàng)建二叉樹前序遍歷中序遍歷后序遍歷層序遍歷求二叉樹深度求指定結點到二叉樹根節(jié)點路徑結束 4. 總結該次試驗中，二叉樹的建立，前序遍歷，中序遍歷，后序遍歷，求二叉樹的深度以及二叉樹的銷毀都涉及到遞歸函數(shù)的巧妙應用。二叉樹的層序遍歷則利用“隊”的概念來實現(xiàn)根節(jié)點入隊，出隊，并讓其孩子按順序入隊。個人覺得最難的部分莫過于求指定結點到根節(jié)點的路徑。對于尋找指定結點到根節(jié)點的路徑，首先覺得應該是一個一個節(jié)點地尋找，直到找到要求的結點，尋找過程即用到二叉樹的遍歷，比如該實驗中用到的前序遍歷；再者，關于路徑，想到“迷宮問題”，即使用“棧”存儲尋找到指定結點的正確路徑

8、，并一一出棧，就可得到指定結點到根節(jié)點的路徑。對于編程，有些巧妙而經典的方法需要記憶，獨自想出每種問題的算法比較困難，也浪費時間，而借鑒一些經典算法，有利于加快工作，也啟迪我們一些算法的創(chuàng)新。所以，我們需要記憶一些經典算法。源程序：#include<iostream>using namespace std;template<class T>struct BiNodeT data;BiNode<T>*lchild;BiNode<T>*rchild;template<class T>class BiTreeprivate:void Cre

9、ate(BiNode<T>*&R,T data,int i,int n);/創(chuàng)建二叉樹void Release(BiNode<T>*R);/釋放二叉樹public:BiNode<T>*root; /根節(jié)點BiTree(T data,int n); /構造函數(shù)void Preorder(BiNode<T>*R); /前序遍歷void Inorder(BiNode<T>*R); /中序遍歷void Postorder(BiNode<T>*R); /后序遍歷void Leveorder(BiNode<T>*R

10、); /層序遍歷BiTree(); /析構函數(shù) int Count(BiNode<T>*R); /結點數(shù)bool Getpath(BiNode<T>*R,int d); /路徑int GetDepth(BiNode<T>*R,int d); /深度;template<class T>void BiTree<T>:Create(BiNode<T>*&R,T data,int i,int n) /表示位置，從開始，表示數(shù)組的長度if(i<=n)R=new BiNode<T> /創(chuàng)建根節(jié)點R->d

11、ata=datai-1;Create(R->lchild,data,2*i,n); /創(chuàng)建左子樹Create(R->rchild,data,2*i+1,n); /創(chuàng)建右子樹else R=NULL;template<class T>BiTree<T>:BiTree(T data,int n)Create(root,data,1,n);/前序遍歷template<class T>void BiTree<T>:Preorder(BiNode<T>*R)if(R!=NULL)cout<<R->data; /訪問節(jié)

12、點Preorder(R->lchild); /遍歷左子樹Preorder(R->rchild); /遍歷右子樹/中序遍歷template<class T>void BiTree<T>:Inorder(BiNode<T>*R)if(R!=NULL)Inorder(R->lchild); /遍歷左子樹cout<<R->data; /訪問結點Inorder(R->rchild); /遍歷右子樹/后序遍歷template<class T>void BiTree<T>:Postorder(BiNode&

13、lt;T>*R)if(R!=NULL)Postorder(R->lchild); /遍歷左子樹Postorder(R->rchild); /遍歷右子樹cout<<R->data; /訪問結點/層序遍歷template<class T>void BiTree<T>:Leveorder(BiNode<T>*R)BiNode<T>*queue100;int f=0;int r=0; /初始化空隊列if(R!=NULL) queue+r=R; /根節(jié)點入隊while(f!=r)BiNode<T>*p=que

14、ue+f; /對頭元素出隊cout<<p->data; /出隊打印if(p->lchild!=NULL) queue+r=p->lchild; /左孩子入隊if(p->rchild!=NULL) queue+r=p->rchild; /右孩子入隊/析1函數(shù)template<class T>void BiTree<T>:Release(BiNode<T>*R)if(R!=NULL)Release(R->lchild); 釋放左子樹Release(R->rchild); /釋放右子樹delete R; /釋放

15、根節(jié)點/釋放二叉樹template<class T>BiTree<T>:BiTree()Release(root);/求結點總數(shù)template<class T>int BiTree<T>:Count(BiNode<T> *R)if(R=NULL)return 0;elseint m=Count(R->lchild);int n=Count(R->rchild);return m+n+1;/求深度template<class T>int BiTree<T>:GetDepth(BiNode<T&

16、gt; *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=GetDepth(R->rchild,d+1);return n>m?n:m; /查詢結點路徑? template<class T>bool BiTree<T>:Getpath(BiNode<T>*R,int d) if(R=NULL)return false;if(R->

17、data=d|Getpath(R->lchild,d)|Getpath(R->rchild,d)cout<<R->data<<" "return true;void main() char data50="abcdefgh"BiTree<char>tree(data,8);cout<<"前序遍歷為："tree.Preorder(tree.root);cout<<endl;cout<<"中序遍歷為："tree.Inorder(tree.root);cout<<endl;cout<<"后序遍歷為："tree.Postorder(tree.root);cout<<endl;cout<<"層序遍歷為："tree.Leveorder(tree.root);cout<<endl;