1、1. 實驗目的和內容：掌握二叉樹基本操作的實現方法2. 程序分析數據結構實 驗 報 告2.1存儲結構鏈式存儲2.程序流程2.3關鍵算法分析算法一：Create(BiNode<T>* &R,T data口,int i,int n)11算法功能：創建二叉樹2算法基本思想：利用順序存儲結構為輸入，采用先建立根結點，再建立 左右孩子的方法來遞歸建立二叉鏈表的二叉樹【3】 算法空間時間復雜度分析：O(n)41代碼邏輯：如果位置小于數組的長度則 創建根結點將數組的值賦給剛才創建的結點的數據域創建左子樹，如果當前結點位置為i, 則左孩子位置為2i創建右子樹，如果當前結點位置為i, 則右孩

2、子位置為2i+1否則R為空算法二： CopyTree（BiNode<T>*sR,BiNode<T>* &dR）【 1】 算法功能：復制構造函數【 2】算法基本思想：按照先創建根結點，再遞歸創建左右子樹的方法來實現。【 3】算法空間時間復雜度分析： O（ n）【 4】代碼邏輯 :如果源二叉樹根結點不為空則創建根結點調用函數自身，創建左子樹調用函數自身，創建右子樹將該函數放在復制構造函數中調用，就可以實現復制構造函數算法三： PreOrder（BiNode<T>*R）【 1】 算法功能：二叉樹的前序遍歷【 2】 算法基本思想：這個代碼用的是優化算法，提前

3、讓當前結點出棧。【 3】 算法空間時間復雜度分析： O（ n）【 4】 代碼邏輯（偽代碼）如果當前結點為非空，則訪問當前結點當前結點入棧將當前結點的左孩子作為當前結點 如果為空則棧頂結點出棧則將該結點的右孩子作為當前結點反復執行這兩個過程，直到結點為空并且棧空算法四： InOrder(BiNode<T>*R)1】 算法功能：二叉樹的中序遍歷2】 算法基本思想：遞歸3】 算法空間時間復雜度分析：未知4】 代碼邏輯：如果R為非空：則調用函數自身遍歷左孩子訪問該結點再調用自身訪問該結點的右孩子算法五： LevelOrder(BiNode<T>*R)【 1】 算法功能：二叉樹的

4、層序遍歷【 2】 算法基本思想：【 3】 算法空間時間復雜度分析： O( n)【 4】 代碼邏輯(偽代碼)：若根結點非空，入隊如果隊列不空對頭元素出隊訪問該元素若該結點的左孩子為非空，則左孩子入隊；若該結點的右孩子為非空，則右孩子入隊；算法六： Count(BiNode<T>*R)【 1】 算法功能：計算結點的個數【 2】 算法基本思想：遞歸【 3】 算法空間時間復雜度分析：未知【 4】 代碼邏輯：如果R不為空的話調用函數自身計算左孩子的結點數調用函數自身計算右孩子的結點數template<class T>int BiTree<T>:Count(BiNode

5、<T>*R)if(R=NULL)return 0;elseint m=Count(R->lchild);int n=Count(R->rchild);return m+n+1;算法七： Release(BiNode<T>*R)【 1】 算法功能：釋放動態內存【 2】 算法基本思想：左右子樹全部釋放完畢后再釋放該結點【 3】 算法空間時間復雜度分析：未知【 4】 代碼邏輯：調用函數自身，釋放左子樹調用函數自身，釋放右子樹釋放根結點釋放二叉樹template<class T>void BiTree<T>:Release(BiNode<

6、;T>*R)if(R!=NULL)Release(R->lchild);Release(R->rchild);delete R;template<class T>BiTree<T>:BiTree()Release(root);int main()int a10=1,2,3,4,5,6,7,8,9,10;BiTree<int> BTree(a,10);BiTree<int>Tree(BTree);BTree.PreOrder(BTree.root); cout<<endl;Tree.PreOrder(Tree.root

7、); cout<<endl;BTree.InOrder(BTree.root); cout<<endl;Tree.InOrder(Tree.root); cout<<endl;BTree.PostOrder(BTree.root); cout<<endl;Tree.PostOrder(Tree.root); cout<<endl;BTree.LevelOrder(BTree.root); cout<<endl;Tree.LevelOrder(Tree.root); cout<<endl;int m=BTree.

8、Count(BTree.root); cout<<m<<endl;return 0;3. 測試數據：int a10=1,2,3,4,5;1 2 4 5 31 2 4 5 34 2 5 1 34 5 2 3 11 2 3 4 554. 總結：4.1: 這次實驗大多用了遞歸的算法，比較好理解。4.2: 新得體會：在創建二叉樹的過程中，在沒有思路的時候可以巧妙的利用遞歸算法。但是我的代碼仍然應該改進，應該進一步簡化，減少算法的時間復雜度和空間復雜度。#include<iostream>using namespace std;template<class T&

9、gt;class BiNodepublic:T data;BiNode<T>*lchild;BiNode<T>*rchild;template<class T>class BiTreepublic:BiNode<T>*root;BiTree(T data,int n);BiTree(BiTree<T>& r);void PreOrder(BiNode<T>*R);void InOrder(BiNode<T>*R);void PostOrder(BiNode<T>*R);void LevelO

10、rder(BiNode<T>*R);int Count(BiNode<T>*R);BiTree();private:void Create(BiNode<T>* &R,T data,int i,int n);void CopyTree(BiNode<T>*sR,BiNode<T>* &dR);void Release(BiNode<T>*R);template<class T>void BiTree<T>: Create(BiNode<T>* &R,T data,

11、int i,int n)if(i<=n&&datai-1)R=new BiNode<T>R->data=datai-1;Create(R->lchild,data,2*i,n);Create(R->rchild,data,2*i+1,n);else R=NULL;template<class T>BiTree<T>:BiTree(T data,int n)Create(root,data,1,n);template<class T>void BiTree<T>:CopyTree(BiNode&l

12、t;T>*sR,BiNode<T>* &dR) if(sR=NULL)dR=NULL;elsedR=new BiNode<T>dR->data=sR->data;CopyTree(sR->lchild,dR->lchild);CopyTree(sR->rchild,dR->rchild);template<class T>BiTree<T>:BiTree(BiTree<T>& p)CopyTree(p.root,this->root);/this?template<

13、class T>void BiTree<T>:PreOrder(BiNode<T>*R)BiNode<T>*S100;int top=-1;while(top!=-1)|(R!=NULL)if(R!=NULL)cout<<R->data<<"" S+top=R;R=R->lchild;) else ( R=Stop-; R=R->rchild;)template<class T>void BiTree<T>:InOrder(BiNode<T>*R)(if(

14、R!=NULL)(InOrder(R->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>

15、;void BiTree<T>:LevelOrder(BiNode<T>*R)(BiNode<T>*queue100;int f=0,r=0;if(R!=NULL)queue+r=R;while(f!=r)(BiNode<T>*p=queue+f; cout<<p->data<<" "if(p->lchild!=NULL) queue+r=p->lchild;if(p->rchild!=NULL) queue+r=p->rchild;template<class T&

16、gt;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>void BiTree<T>:Release(BiNode<T>*R)if(R!=NULL)Release(R->lchild);Release(R->rchild);delete R;template<class T>BiTree<T>:BiTree()Release(root);int main()int a5=1,2,3,4,5;BiTree<int> BTree(a,5);BiTree<int>Tree(BTree);BTree.PreOrder(BTree.root