B11041309數(shù)據(jù)結(jié)構(gòu)試驗(yàn)二

1、AU點(diǎn)曙/身（2012/2013學(xué)年第二學(xué)期）題目：二叉樹的基本操作及哈夫曼編專業(yè)服務(wù)外包學(xué)生姓名王翰林班級(jí)學(xué)號(hào)B11041209指導(dǎo)教師鄒志強(qiáng)指導(dǎo)單位計(jì)算機(jī)軟件學(xué)院日期2012.10.26簡短評(píng)語教師簽名：年月日評(píng)分等級(jí)備注評(píng)分等級(jí)有五種：優(yōu)秀、良好、中等、及格、不及格一.實(shí)驗(yàn)?zāi)康暮鸵竽康模?、掌握二叉鏈表上實(shí)現(xiàn)二叉樹基本操作。2、學(xué)會(huì)設(shè)計(jì)基于遍歷的求解二叉樹應(yīng)用問題的遞歸算法。3、理解哈夫曼樹的構(gòu)造算法，學(xué)習(xí)設(shè)計(jì)哈夫曼編碼和譯碼系統(tǒng)要求：能成功演示二叉樹的有關(guān)算法，運(yùn)算完畢后能成功釋放二叉樹所有結(jié)點(diǎn)占用的系統(tǒng)類存。二.實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)學(xué)校機(jī)房電腦設(shè)備硬件，VC+6.0軟件三.實(shí)驗(yàn)原理

2、及內(nèi)容原理：(1)在二叉樹上實(shí)現(xiàn)二叉樹運(yùn)算1:設(shè)計(jì)遞歸算法，實(shí)現(xiàn)下列二叉樹運(yùn)算：刪除一棵二叉樹，求一棵二叉樹的高度，求一棵二叉樹中葉子結(jié)點(diǎn)數(shù)，復(fù)制一棵二叉樹，交換一棵二叉樹的左右子樹。2:設(shè)計(jì)算法，按自上到下，自左向右的次序，即按層次遍歷一棵二叉樹。3:設(shè)計(jì)main函數(shù)，測試上述每個(gè)運(yùn)算。(2)哈夫曼編碼和譯碼系統(tǒng)1:所設(shè)計(jì)的系統(tǒng)重復(fù)顯示以下菜單項(xiàng)。B一建樹：讀入字符集和各字符頻度，建立哈夫曼樹。T一遍歷：先序和中序遍歷二叉樹。E一生成編碼：根據(jù)已建成的哈夫曼樹，產(chǎn)生個(gè)字符的哈夫曼編碼。C一編碼：輸入由字符集中字符組成的任意字符串，利用已生成的哈夫曼樹進(jìn)行編碼，顯示編碼結(jié)果，并將輸入的字符串及

3、其編碼結(jié)果保存在磁盤文件中。D譯碼：讀入文件，利用已建成的哈夫曼樹進(jìn)行譯碼，并將譯碼結(jié)果存入磁盤文件P一打?。浩聊伙@示文件。X一退出。內(nèi)容：1、建立頭文件BTree.H,在該文件中定義二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，并編寫二叉樹的各種基本操作實(shí)現(xiàn)函數(shù)。同時(shí)建立一個(gè)驗(yàn)證操作實(shí)現(xiàn)的主函數(shù)文件Test.cpp,編譯并調(diào)試程序，直到正確運(yùn)行。注意：需要用到隊(duì)列的有關(guān)操作。說明：二叉樹的基本操作可包括：(1)voidClear(BTreeNode*BT)/消除一棵二叉樹，并釋放結(jié)點(diǎn)空間(2) voidMakeTree(BTreeNode*BT)(3) voidBreakTree(BTreeNode*BT)(4)v

4、oidPreOrder(BTreeNode*BT)(5)voidInOrder(BTreeNode*BT)(6)voidPostOrder(BTreeNode*BT)(7)voidFloorOrder(BTreeNode*BT)(8)intSize(BTreeNode*BT)/(9)voidExchange(BTreeNode*BT)(10)intGetHeight(BTreeNode*BT)四.概要設(shè)計(jì)/構(gòu)造一棵二叉樹BT/撤銷一棵二叉樹BT/先序遍歷二叉樹BT/中序遍歷二叉樹BT/后序遍歷二叉樹BT/層次遍歷二叉樹BT求二叉樹BT的結(jié)點(diǎn)數(shù)量/把二叉樹BT的左右子樹進(jìn)行交換/求二叉樹BT的高

5、度1.流程圖及設(shè)計(jì)思想求樹的高度左右子樹高度之和進(jìn)行比較，誰大誰就是樹的高度刪除二叉樹先刪除左子樹，再刪-除右子樹，最后刪除根節(jié)點(diǎn)，再釋放結(jié)點(diǎn)空間2,本程序包含的模塊(1)主程序模塊Voidmain()(初始化；構(gòu)造一棵二叉樹；各種遍歷二叉樹；對(duì)二叉樹進(jìn)行各種常見運(yùn)算；刪除二叉樹；)(2)二叉樹模塊一一實(shí)現(xiàn)二叉樹的抽象數(shù)據(jù)類型和基本操作(3)隊(duì)列模塊一一實(shí)現(xiàn)隊(duì)列的抽象數(shù)據(jù)類(4)二叉樹運(yùn)算模塊一一求二叉樹的結(jié)點(diǎn)，葉子數(shù)目五.詳細(xì)設(shè)計(jì)一.先序遍歷：A.自然語言描述：1,判斷根節(jié)點(diǎn)會(huì)否為空，如果為空，返回2.如果根節(jié)點(diǎn)不為空3,先輸出根節(jié)點(diǎn)，再遞歸調(diào)用自身依次輸出左孩子和右孩子B.代碼詳細(xì)分析te

6、mplate<classT>voidBinaryTree<T>:PreOrder(void(*Visit)(T&x)(PreOrder(Visit,root);)template<classT>voidBinaryTree<T>:PreOrder(void(*Visit)(T&x),BTNode<T>*t)(if(t)(Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);二.中序遍歷：A.自然語言描述：1 .判斷根

7、節(jié)點(diǎn)是否為空，如果為空，返回2 .如果根節(jié)點(diǎn)不為空3 .遞歸調(diào)用自身輸出左孩子，再輸出根結(jié)點(diǎn)，遞歸調(diào)用輸出右孩子B.代碼詳細(xì)分析：template<classT>voidBinaryTree<T>:InOrder(void(*Visit)(T&x)(InOrder(Visit,root);template<classT>voidBinaryTree<T>:InOrder(void(*Visit)(T&x),BTNode<T>*t)(if(t)(InOrder(Visit,t->lChild);Visit(t-&g

8、t;element);InOrder(Visit,t->rChild);三.后序遍歷：A.自然語言描述：1 .判斷根節(jié)點(diǎn)是否為空，如果為空，返回2 .如果根節(jié)點(diǎn)不為空3 .遞歸調(diào)用自身輸出左孩子和右孩子，再輸出根結(jié)點(diǎn)B.代碼詳細(xì)分析：template<classT>voidBinaryTree<T>:PostOrder(void(*Visit)(T&x)(PostOrder(Visit,root);template<classT>voidBinaryTree<T>:PostOrder(void(*Visit)(T&x),BT

9、Node<T>*t)(if(t)(PostOrder(Visit,t->lChild);PostOrder(Visit,t->rChild);Visit(t->element);四.層次遍歷二叉樹：A.自然語言描述：1 .定義頭指針和尾指針和空指針p2 .根節(jié)點(diǎn)是否為空，如果是，結(jié)束3 .如果不是，根節(jié)點(diǎn)入隊(duì)4 .取隊(duì)首元素，輸出隊(duì)首元素5 .將隊(duì)首的非空左右結(jié)點(diǎn)入隊(duì)列，刪除隊(duì)首元素6 .循環(huán)下去，直到隊(duì)列為空B.代碼詳細(xì)分析：template<classT>voidBinaryTree<T>:FloorOrder(void(*Visit)

10、(T&x)(FloorOrder(Visit,root);template<classT>voidBinaryTree<T>:;FloorOrder(void(*Visit)(Visit<T>*x),BTNode<T>*t)(SeqQueue<BTNode<T>*>se(100);se.EnQueue(t);BTNode<T>*temp;while(!se.IsEmpty()(se.Front(temp);Visit(temp);se.DeQueue();if(temp->lchild)se.En

11、Queue(temp->lchild);if(temp->child)se.EnQueue(temp->rchild);五.求二叉樹的結(jié)點(diǎn)數(shù)：A.自然語言描述：1：判斷根節(jié)點(diǎn)是否為空，如果為空，返回02:如果根節(jié)點(diǎn)不為空3:遞歸調(diào)用求二叉樹的結(jié)點(diǎn)數(shù)的函數(shù)，參數(shù)改為根節(jié)點(diǎn)的左孩子4:遞歸調(diào)用求二叉樹的結(jié)點(diǎn)數(shù)的函數(shù)，參數(shù)改為根節(jié)點(diǎn)的右孩子5:返回根節(jié)點(diǎn)的左右字?jǐn)?shù)的結(jié)點(diǎn)數(shù)之和B.代碼詳細(xì)分析：template<classT>intBinaryTree<T>:Size()(returnSize(root);template<classT>intBi

12、naryTree<T>:Size(BTNode<T>*t)(if(!t)return0;elsereturnSize(t->lChild)+Size(t->rChild)+1;)六.二叉樹的左右交換：A.自然語言描述：1 .判斷根節(jié)點(diǎn)是否為空，如果為空，返回2 .如果不為空，再判斷該節(jié)點(diǎn)左右孩子是否同時(shí)為空，3 .如果是，返回4 .如果不為空，交換左右孩子5 .返回循環(huán)，遍歷左右子樹B.代碼詳細(xì)分析：template<classT>voidBinaryTree<T>:Exchange()(Exchange(root);)templat

13、e<classT>voidBinaryTree<T>:Exchange(BTNode<T>*t)(if(!t)return;BTNode<T>*temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);)七.求二叉樹的深度：A.自然語言描述：1：判斷根節(jié)點(diǎn)是否為空，如果根節(jié)點(diǎn)為空，返回02:如果根節(jié)點(diǎn)不為空但是根節(jié)點(diǎn)的左右孩子同時(shí)為空，返回13:如果以上兩個(gè)條件都不成立4:遞歸調(diào)用

14、求二叉樹的深度，函數(shù)的參數(shù)改為根節(jié)點(diǎn)的左孩子，并且深度初始化為15:遞歸調(diào)用求二叉樹的深度，函數(shù)的參數(shù)改為跟結(jié)點(diǎn)的右孩子，并且深度初始化為06:返回4與5步中得出深度較大的那個(gè)數(shù)作為二叉樹的深度數(shù)B.代碼詳細(xì)分析：template<classT>intBinaryTree<T>:GetHeight(BTNode<T>*t)(inttempl;inttempr;if(!t)return0;templ=GetHeight(t->lChild);tempr=GetHeight(t->rChild);if(templ+>tempr+)returnt

15、empl;elsereturntempr;六.實(shí)驗(yàn)總結(jié)：在剛進(jìn)行編寫這個(gè)程序的時(shí)候，只是機(jī)械的將課本上的算法敲上去，然后執(zhí)行，可是在后面的幾個(gè)功能中，在需要在前面的基礎(chǔ)上進(jìn)行改變，例如：在求深度的時(shí)候，則和遍歷有點(diǎn)類似，只不過，深度是分別遍歷左子樹和右子樹，然后比較；最難的則是層次遍歷了，最初的時(shí)候一點(diǎn)兒思緒也沒有，后來在同學(xué)的幫助下和上網(wǎng)查了相關(guān)的資料，才編寫出來,真可謂幾經(jīng)波折。實(shí)驗(yàn)任務(wù)要求不僅要求對(duì)課本知識(shí)有較深刻的了解，同時(shí)要求程序設(shè)計(jì)者有較強(qiáng)的思維和動(dòng)手能力，讓更加了解編程思想和編程技巧。這次實(shí)驗(yàn)設(shè)計(jì)讓我有一個(gè)深刻的體會(huì)，那就是細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過分，往

16、往檢查了半天發(fā)現(xiàn)錯(cuò)誤發(fā)生在某個(gè)括號(hào)，分號(hào)，引號(hào)，或者數(shù)據(jù)類型上。例如：在撤銷一棵二叉樹時(shí)刪除根節(jié)點(diǎn)，沒有把根節(jié)點(diǎn)置為空，又或者中請(qǐng)了一個(gè)新的結(jié)點(diǎn)空間，卻沒有把它釋放等等。這次實(shí)驗(yàn)讓我收獲不少，我認(rèn)識(shí)到了，大一的課程確實(shí)沒有學(xué)好，一定程度上影響到了這次程序設(shè)計(jì)，不過我的確把二叉樹的一些基本概念掌握得更牢固了，學(xué)到了二叉樹的一些基本運(yùn)算，多多少少給我積累了編程的經(jīng)驗(yàn)，更加激發(fā)了我對(duì)數(shù)據(jù)結(jié)構(gòu)的興趣，讓我更有信心把這門課學(xué)好，讓我更有信心把這門專業(yè)學(xué)好。謝謝老師！七.測試結(jié)果：C:UserssaoxueerDesktopDSA-Exp-2-only_BTreeTest.exe前序遍歷BDCEF中序遍歷

17、DBECF后序遍歷DEFCB結(jié)點(diǎn)數(shù)和5當(dāng)右頭震后的前序遢歷BCFED樹的圖度曲八.“二叉樹基本運(yùn)算”源代碼:BTree.h:#include<iostream>usingnamespacestd;template<classT>structBTNode(Telement;BTNode<T>*lChild,*rChild;BTNode()(lChild=rChild=NULL;BTNode(constT&x)(element=x;lChild=rChild=NULL;BTNode(constT&x,BTNode<T>*l,BTNod

18、e<T>*r)(element=x;lChild=l;rChild=r;template<classT>classBinaryTree(public:BinaryTree()root=NULL;BinaryTree()Clear(root);boolIsEmpty()const;voidClear();boolRoot(T&x)const;intSize();voidMakeTree(constT&e,BinaryTree<T>&left,BinaryTree<T>&right);voidBreakTree(T&a

19、mp;e,BinaryTree<T>&left,BinaryTree<T>&right);voidLevelOrder(void(*Visit(T&x);voidPreOrder(void(*Visit)(T&x);voidInOrder(void(*Visit)(T&x);voidPostOrder(void(*Visit)(T&x);voidExchange();intGetHeight();protected:BTNode<T>*root;private:voidClear(BTNode<T>

20、*t);intSize(BTNode<T>*t);voidLevelOrder(void(*Visit)(T&x),BTNode<T>*t);voidPreOrder(void(*Visit)(T&x),BTNode<T>*t);voidInOrder(void(*Visit)(T&x),BTNode<T>*t);voidPostOrder(void(*Visit)(T&x),BTNode<T>*t);voidExchange(BTNode<T>*t);intGetHeight(BTNode

21、<T>*t);template<classT>voidBinaryTree<T>:Clear(BTNode<T>*t)if(!t)return;Clear(t->lChild);Clear(t->rChild);deletet;template<classT>boolBinaryTree<T>:Root(T&x)constif(root)x=root->element;returntrue;elsereturnfalse;template<classT>voidBinaryTree&l

22、t;T>:MakeTree(constT&e,BinaryTree<T>&left,BinaryTree<T>&right)if(root|&left=&right)return;root=newBTNode<T>(e,left.root,right.root);left.root=right.root=NULL;template<classT>voidBinaryTree<T>:BreakTree(T&x,BinaryTree<T>&left,BinaryTr

23、ee<T>&right)if(!root|&left=&right|left.root|right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;deleteroot;root=NULL;template<classT>voidVisit(T&x)cout<<x<<""template<classT>voidBinaryTree<T>:PreOrder

24、(void(*Visit)(T&x)PreOrder(Visit,root);template<classT>voidBinaryTree<T>二PreOrder(void(*Visit)(T&x),BTNode<T>*t)if(t)Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);template<classT>voidBinaryTree<T>:InOrder(void(*Visit)(T&x)InO

25、rder(Visit,root);template<classT>voidBinaryTree<T>:InOrder(void(*Visit)(T&x),BTNode<T>*t)if(t)InOrder(Visit,t->lChild);Visit(t->element);InOrder(Visit,t->rChild);template<classT>voidBinaryTree<T>:PostOrder(void(*Visit)(T&x)PostOrder(Visit,root);)templat

26、e<classT>voidBinaryTree<T>:PostOrder(void(*Visit)(T&x),BTNode<T>*t)if(t)PostOrder(Visit,t->lChild);PostOrder(Visit,t->rChild);Visit(t->element);)template<classT>voidBinaryTree<T>:FloorOrder(void(*Visit)(T&x)FloorOrder(Visit,root);)template<classT>

27、voidBinaryTree<T>:FloorOrder(void(*Visit)(T&x),BTNode<T>*t)SeqQueue<BTNode<T>*>se(100);se.EnQueue(t);BTNode<T>*tmp;while(!se.IsEmpty()se.Front(tmp);Visit(tmp);se.DeQueue();if(tmp->lChild)se.EnQueue(tmp->lChild);if(tmp->Child)se.EnQueue(tmp->rChild);)temp

28、late<classT>intBinaryTree<T>:Size()(returnSize(root);)template<classT>intBinaryTree<T>:Size(BTNode<T>*t)(if(!t)return0;elsereturnSize(t->lChild)+Size(t->rChild)+1;)template<classT>voidBinaryTree<T>:Exchange()(Exchange(root);)template<classT>voidBinaryTree<T>:Exchange(BTNode<T>*t)(if(!t)return;BTNode<T>*temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);)template<classT>intBinaryTree<T>:GetHeight()(return