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

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

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

3、其編碼結(jié)果保存在磁盤文件中。D譯碼：讀入文件，利用已建成的哈夫曼樹進行譯碼，并將譯碼結(jié)果存入磁盤文件P一打?。浩聊伙@示文件。X一退出。內(nèi)容：1、建立頭文件BTree.H,在該文件中定義二叉樹的鏈式存儲結(jié)構(gòu)，并編寫二叉樹的各種基本操作實現(xiàn)函數(shù)。同時建立一個驗證操作實現(xiàn)的主函數(shù)文件Test.cpp,編譯并調(diào)試程序，直到正確運行。注意：需要用到隊列的有關(guān)操作。說明：二叉樹的基本操作可包括：(1)voidClear(BTreeNode*BT)/消除一棵二叉樹，并釋放結(jié)點空間(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è)計/構(gòu)造一棵二叉樹BT/撤銷一棵二叉樹BT/先序遍歷二叉樹BT/中序遍歷二叉樹BT/后序遍歷二叉樹BT/層次遍歷二叉樹BT求二叉樹BT的結(jié)點數(shù)量/把二叉樹BT的左右子樹進行交換/求二叉樹BT的高

5、度1.流程圖及設(shè)計思想求樹的高度左右子樹高度之和進行比較，誰大誰就是樹的高度刪除二叉樹先刪除左子樹，再刪-除右子樹，最后刪除根節(jié)點，再釋放結(jié)點空間2,本程序包含的模塊(1)主程序模塊Voidmain()(初始化；構(gòu)造一棵二叉樹；各種遍歷二叉樹；對二叉樹進行各種常見運算；刪除二叉樹；)(2)二叉樹模塊一一實現(xiàn)二叉樹的抽象數(shù)據(jù)類型和基本操作(3)隊列模塊一一實現(xiàn)隊列的抽象數(shù)據(jù)類(4)二叉樹運算模塊一一求二叉樹的結(jié)點，葉子數(shù)目五.詳細設(shè)計一.先序遍歷：A.自然語言描述：1,判斷根節(jié)點會否為空，如果為空，返回2.如果根節(jié)點不為空3,先輸出根節(jié)點，再遞歸調(diào)用自身依次輸出左孩子和右孩子B.代碼詳細分析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é)點是否為空，如果為空，返回2 .如果根節(jié)點不為空3 .遞歸調(diào)用自身輸出左孩子，再輸出根結(jié)點，遞歸調(diào)用輸出右孩子B.代碼詳細分析：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é)點是否為空，如果為空，返回2 .如果根節(jié)點不為空3 .遞歸調(diào)用自身輸出左孩子和右孩子，再輸出根結(jié)點B.代碼詳細分析：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é)點是否為空，如果是，結(jié)束3 .如果不是，根節(jié)點入隊4 .取隊首元素，輸出隊首元素5 .將隊首的非空左右結(jié)點入隊列，刪除隊首元素6 .循環(huán)下去，直到隊列為空B.代碼詳細分析：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é)點數(shù)：A.自然語言描述：1：判斷根節(jié)點是否為空，如果為空，返回02:如果根節(jié)點不為空3:遞歸調(diào)用求二叉樹的結(jié)點數(shù)的函數(shù)，參數(shù)改為根節(jié)點的左孩子4:遞歸調(diào)用求二叉樹的結(jié)點數(shù)的函數(shù)，參數(shù)改為根節(jié)點的右孩子5:返回根節(jié)點的左右字數(shù)的結(jié)點數(shù)之和B.代碼詳細分析：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é)點是否為空，如果為空，返回2 .如果不為空，再判斷該節(jié)點左右孩子是否同時為空，3 .如果是，返回4 .如果不為空，交換左右孩子5 .返回循環(huán)，遍歷左右子樹B.代碼詳細分析：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é)點是否為空，如果根節(jié)點為空，返回02:如果根節(jié)點不為空但是根節(jié)點的左右孩子同時為空，返回13:如果以上兩個條件都不成立4:遞歸調(diào)用

14、求二叉樹的深度，函數(shù)的參數(shù)改為根節(jié)點的左孩子，并且深度初始化為15:遞歸調(diào)用求二叉樹的深度，函數(shù)的參數(shù)改為跟結(jié)點的右孩子，并且深度初始化為06:返回4與5步中得出深度較大的那個數(shù)作為二叉樹的深度數(shù)B.代碼詳細分析：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;六.實驗總結(jié)：在剛進行編寫這個程序的時候，只是機械的將課本上的算法敲上去，然后執(zhí)行，可是在后面的幾個功能中，在需要在前面的基礎(chǔ)上進行改變，例如：在求深度的時候，則和遍歷有點類似，只不過，深度是分別遍歷左子樹和右子樹，然后比較；最難的則是層次遍歷了，最初的時候一點兒思緒也沒有，后來在同學的幫助下和上網(wǎng)查了相關(guān)的資料，才編寫出來,真可謂幾經(jīng)波折。實驗任務(wù)要求不僅要求對課本知識有較深刻的了解，同時要求程序設(shè)計者有較強的思維和動手能力，讓更加了解編程思想和編程技巧。這次實驗設(shè)計讓我有一個深刻的體會，那就是細節(jié)決定成敗，編程最需要的是嚴謹，如何的嚴謹都不過分，往

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

17、DBECF后序遍歷DEFCB結(jié)點數(shù)和5當右頭震后的前序遢歷BCFED樹的圖度曲八.“二叉樹基本運算”源代碼: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