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

數(shù)據(jù)結(jié)構(gòu) 實(shí) 驗(yàn) 報(bào) 告 1.實(shí)驗(yàn)?zāi)康暮蛢?nèi)容：掌握二叉樹(shù)基本操作的實(shí)現(xiàn)方法2.程序分析2.1存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)2程序流程 2.3關(guān)鍵算法分析算法一：Create(BiNode* &R,T data,int i,int n)【1】算法功能：創(chuàng)建二叉樹(shù)【2】算法基本思想：利用順序存儲(chǔ)結(jié)構(gòu)為輸入，采用先建立根結(jié)點(diǎn)，再建立左右孩子的方法來(lái)遞歸建立二叉鏈表的二叉樹(shù)【3】算法空間時(shí)間復(fù)雜度分析：O(n)【4】代碼邏輯： 如果位置小于數(shù)組的長(zhǎng)度則 創(chuàng)建根結(jié)點(diǎn) 將數(shù)組的值賦給剛才創(chuàng)建的結(jié)點(diǎn)的數(shù)據(jù)域 創(chuàng)建左子樹(shù)，如果當(dāng)前結(jié)點(diǎn)位置為i,則左孩子位置為2i 創(chuàng)建右子樹(shù)，如果當(dāng)前結(jié)點(diǎn)位置為i,則右孩子位置為2i+1 否則R為空 算法二：CopyTree(BiNode*sR,BiNode* &dR)）【1】算法功能：復(fù)制構(gòu)造函數(shù)【2】算法基本思想：按照先創(chuàng)建根結(jié)點(diǎn)，再遞歸創(chuàng)建左右子樹(shù)的方法來(lái)實(shí)現(xiàn)。【3】算法空間時(shí)間復(fù)雜度分析：O（n)【4】代碼邏輯: 如果源二叉樹(shù)根結(jié)點(diǎn)不為空 則 創(chuàng)建根結(jié)點(diǎn) 調(diào)用函數(shù)自身，創(chuàng)建左子樹(shù) 調(diào)用函數(shù)自身，創(chuàng)建右子樹(shù) 將該函數(shù)放在復(fù)制構(gòu)造函數(shù)中調(diào)用，就可以實(shí)現(xiàn)復(fù)制構(gòu)造函數(shù)算法三：PreOrder(BiNode*R)【1】算法功能：二叉樹(shù)的前序遍歷【2】算法基本思想：這個(gè)代碼用的是優(yōu)化算法，提前讓當(dāng)前結(jié)點(diǎn)出棧。【3】算法空間時(shí)間復(fù)雜度分析：O（n）【4】代碼邏輯（偽代碼） 如果當(dāng)前結(jié)點(diǎn)為非空，則 訪問(wè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è)過(guò)程，直到結(jié)點(diǎn)為空并且?？账惴ㄋ模篒nOrder(BiNode*R)【1】算法功能：二叉樹(shù)的中序遍歷【2】算法基本思想：遞歸【3】算法空間時(shí)間復(fù)雜度分析：未知【4】代碼邏輯： 如果R為非空： 則調(diào)用函數(shù)自身遍歷左孩子 訪問(wèn)該結(jié)點(diǎn) 再調(diào)用自身訪問(wèn)該結(jié)點(diǎn)的右孩子算法五：LevelOrder(BiNode*R)【1】算法功能：二叉樹(shù)的層序遍歷【2】算法基本思想：【3】算法空間時(shí)間復(fù)雜度分析：O（n）【4】代碼邏輯（偽代碼）： 若根結(jié)點(diǎn)非空，入隊(duì) 如果隊(duì)列不空 對(duì)頭元素出隊(duì) 訪問(wèn)該元素 若該結(jié)點(diǎn)的左孩子為非空，則左孩子入隊(duì)； 若該結(jié)點(diǎn)的右孩子為非空，則右孩子入隊(duì)； 算法六：Count(BiNode*R)【1】算法功能：計(jì)算結(jié)點(diǎn)的個(gè)數(shù)【2】算法基本思想：遞歸【3】算法空間時(shí)間復(fù)雜度分析：未知【4】代碼邏輯： 如果R不為空的話(huà) 調(diào)用函數(shù)自身計(jì)算左孩子的結(jié)點(diǎn)數(shù) 調(diào)用函數(shù)自身計(jì)算右孩子的結(jié)點(diǎn)數(shù) template int BiTree:Count(BiNode*R) if(R=NULL)return 0; else int m=Count(R-lchild); int n=Count(R-rchild); return m+n+1; 算法七：Release(BiNode*R)【1】算法功能：釋放動(dòng)態(tài)內(nèi)存【2】算法基本思想：左右子樹(shù)全部釋放完畢后再釋放該結(jié)點(diǎn)【3】算法空間時(shí)間復(fù)雜度分析：未知【4】代碼邏輯： 調(diào)用函數(shù)自身，釋放左子樹(shù) 調(diào)用函數(shù)自身，釋放右子樹(shù) 釋放根結(jié)點(diǎn) 釋放二叉樹(shù) template void BiTree:Release(BiNode*R) if(R!=NULL) Release(R-lchild); Release(R-rchild); delete R; template BiTree:BiTree() Release(root); int main() int a10=1,2,3,4,5,6,7,8,9,10; BiTree BTree(a,10); BiTreeTree(BTree); BTree.PreOrder(BTree.root); coutendl; Tree.PreOrder(Tree.root); coutendl; BTree.InOrder(BTree.root); coutendl; Tree.InOrder(Tree.root); coutendl; BTree.PostOrder(BTree.root); coutendl; Tree.PostOrder(Tree.root); coutendl; BTree.LevelOrder(BTree.root); coutendl; Tree.LevelOrder(Tree.root); coutendl; int m=BTree.Count(BTree.root);coutmendl; 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ù)的過(guò)程中，在沒(méi)有思路的時(shí)候可以巧妙的利用遞歸算法。但是我的代碼仍然應(yīng)該改進(jìn)，應(yīng)該進(jìn)一步簡(jiǎn)化，減少算法的時(shí)間復(fù)雜度和空間復(fù)雜度。#includeusing namespace std;templateclass BiNodepublic:T data;BiNode*lchild;BiNode*rchild; ; templateclass BiTree public: BiNode*root;BiTree(T data,int n);BiTree(BiTree& r);void PreOrder(BiNode*R);void InOrder(BiNode*R);void PostOrder(BiNode*R);void LevelOrder(BiNode*R);int Count(BiNode*R);BiTree();private:void Create(BiNode* &R,T data,int i,int n);void CopyTree(BiNode*sR,BiNode* &dR);void Release(BiNode*R); ; template void BiTree: Create(BiNode* &R,T data,int i,int n) if(i=n&datai-1) R=new BiNode; R-data=datai-1; Create(R-lchild,data,2*i,n); Create(R-rchild,data,2*i+1,n); else R=NULL; template BiTree:BiTree(T data,int n) Create(root,data,1,n); template void BiTree:CopyTree(BiNode*sR,BiNode* &dR) if(sR=NULL) dR=NULL; else dR=new BiNode; dR-data=sR-data; CopyTree(sR-lchild,dR-lchild); CopyTree(sR-rchild,dR-rchild); template BiTree:BiTree(BiTree& p) CopyTree(p.root,this-root);/this? template void BiTree:PreOrder(BiNode*R) BiNode*S100; int top=-1; while(top!=-1)|(R!=NULL) if(R!=NULL) coutdatalchild; elseR=Stop-;R=R-rchild; template void BiTree:InOrder(BiNode*R) if(R!=NULL) InOrder(R-lchild); coutdatarchild); template void BiTree: PostOrder(BiNode*R) if(R!=NULL) PostOrder(R-lchild); PostOrder(R-rchild); coutdata ; template void BiTree:LevelOrder(BiNode*R) BiNode*queue100; int f=0,r=0; if(R!=NULL) queue+r=R; while(f!=r) BiNode*p=queue+f; coutdatalchild!=NULL) queue+r=p-lchild; if(p-rchild!=NULL) queue+r=p-rchild; template int BiTree:Count(BiNode*R) if(R=NULL)return 0; else int m=Count(R-lchild); int n=Count(R-rchild); return m+n+1; template void BiTree:Release(BiNode*R) if(R!=NULL) Release(R-lchild); Release(R-rchild); delete R; template BiTree:BiTree() Release(root); int main() int a5=1,2,3,4,5; BiTree BTree(a,5); BiTreeTree(BTree); BTree.PreOrder(BTree.root); coutendl;