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

1、1. 實(shí)驗(yàn)?zāi)康暮蛢?nèi)容：掌握二叉樹基本操作的實(shí)現(xiàn)方法2. 程序分析數(shù)據(jù)結(jié)構(gòu)實(shí) 驗(yàn) 報(bào) 告2.1存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)2.程序流程2.3關(guān)鍵算法分析算法一：Create(BiNode<T>* &R,T data口,int i,int n)11算法功能：創(chuàng)建二叉樹2算法基本思想：利用順序存儲(chǔ)結(jié)構(gòu)為輸入，采用先建立根結(jié)點(diǎn)，再建立 左右孩子的方法來遞歸建立二叉鏈表的二叉樹【3】 算法空間時(shí)間復(fù)雜度分析：O(n)41代碼邏輯：如果位置小于數(shù)組的長(zhǎng)度則 創(chuàng)建根結(jié)點(diǎn)將數(shù)組的值賦給剛才創(chuàng)建的結(jié)點(diǎn)的數(shù)據(jù)域創(chuàng)建左子樹，如果當(dāng)前結(jié)點(diǎn)位置為i, 則左孩子位置為2i創(chuàng)建右子樹，如果當(dāng)前結(jié)點(diǎn)位置為i, 則右孩

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

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

4、層序遍歷【 2】 算法基本思想：【 3】 算法空間時(shí)間復(fù)雜度分析： O( n)【 4】 代碼邏輯(偽代碼)：若根結(jié)點(diǎn)非空，入隊(duì)如果隊(duì)列不空對(duì)頭元素出隊(duì)訪問該元素若該結(jié)點(diǎn)的左孩子為非空，則左孩子入隊(duì)；若該結(jié)點(diǎn)的右孩子為非空，則右孩子入隊(duì)；算法六： Count(BiNode<T>*R)【 1】 算法功能：計(jì)算結(jié)點(diǎn)的個(gè)數(shù)【 2】 算法基本思想：遞歸【 3】 算法空間時(shí)間復(fù)雜度分析：未知【 4】 代碼邏輯：如果R不為空的話調(diào)用函數(shù)自身計(jì)算左孩子的結(jié)點(diǎn)數(shù)調(diào)用函數(shù)自身計(jì)算右孩子的結(jié)點(diǎn)數(shù)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】 算法功能：釋放動(dòng)態(tài)內(nèi)存【 2】 算法基本思想：左右子樹全部釋放完畢后再釋放該結(jié)點(diǎn)【 3】 算法空間時(shí)間復(fù)雜度分析：未知【 4】 代碼邏輯：調(diào)用函數(shù)自身，釋放左子樹調(diào)用函數(shù)自身，釋放右子樹釋放根結(jié)點(diǎn)釋放二叉樹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. 測(cè)試數(shù)據(jù)：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. 總結(jié)：4.1: 這次實(shí)驗(yàn)大多用了遞歸的算法，比較好理解。4.2: 新得體會(huì)：在創(chuàng)建二叉樹的過程中，在沒有思路的時(shí)候可以巧妙的利用遞歸算法。但是我的代碼仍然應(yīng)該改進(jìn)，應(yīng)該進(jìn)一步簡(jiǎn)化，減少算法的時(shí)間復(fù)雜度和空間復(fù)雜度。#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