1、精選優質文檔-傾情為你奉上實 驗 報 告（ 2016 / 2017 學年 第 一 學期）課程名稱數據結構 A實驗名稱二叉樹的基本操作及哈夫曼編碼譯碼系統的實現專心-專注-專業實 驗 報 告實驗名稱二叉樹的基本操作及哈夫曼編碼譯碼系統的實現指導教師實驗類型驗證實驗學時2+2實驗時間一、 實驗目的和要求目的：創建一棵二叉樹，實現先序、中序和后序遍歷一棵二叉樹，計算二叉樹結點個數等操作。哈夫曼編碼/譯碼系統。要求：能成功演示二叉樹的有關運算，運算完畢后能成功釋放二叉樹所有結點占用的系統內存。二、實驗環境(實驗設備)PC計算機，Windows 7操作系統，IDE: Codeblocks 16.01編譯

2、器: GNU GCC Compiler三、實驗原理及內容程序一：二叉樹的創建以及基本運算本程序一共包含兩個類，一個是BTNode 結點類，定義了三個數據成員，分別是該結點元素數值和指向左右子樹的指針，定義了三個重載的構造函數。，聲明Btree類是BTNode的友元，Visit函數是BTNode的友元函數。本程序另一個類是Btree 二叉樹類，包含一個數據成員（指向根節點的指針root）和一組運算，包括先序，中序，后序，層次遍歷，構造二叉樹，拆分二叉樹，判斷是否空，計算結點數，釋放二叉樹占用空間等。類UML圖：實 驗 報 告核心模塊代碼:1. 二叉樹的創建創建一個二叉樹要新申請一個結點，左右子樹

3、分別指向參數的兩個二叉樹，結點元素賦值為參數值。要先判斷左右子樹是不是同一個樹以及當前調用對象是不是一個空二叉樹。最后要將引用參數中root指針賦值為NULL，反正指針共享同一個空間造成混亂。代碼：template <class T>void BTree<T>:MakeTree(const T &e, BTree<T>& left, BTree<T>& right) if(root|&left=&right) return; root=new BTNode<T>(e,left.root,righ

4、t.root); left.root=right.root=NULL;cout<<"here in BTree<T>:MakeTree"<<endl;2. 二叉樹的拆分將一個二叉樹拆分成兩個二叉樹，首先要判斷參數中二叉樹是不是空，是不是同一個二叉樹，以及當前對象二叉樹是不是空。然后將引用參數的root指針賦值為當前對象的左右子樹。最后delete當前對象root指向的結點，并將root賦值為NULL，防止指針指向的空間被共享。代碼：template <class T>void BTree<T>:BreakTree(

5、T &e,BTree<T>&left, BTree<T>& right)cout<<"here in BTree<T>:BreakTree."<<endl;if(left.root|right.root|!root|&left=&right) return ;e=root->element;left.root=root->lchild;right.root=root->rchild;delete root;root=NULL;3. 二叉樹的遍歷二叉樹的先序遍

6、歷重載有兩個函數，分別是面向用戶的PreOrder(void (*Visit)(BTNode<T>* u)函數和私有函數PreOrder(void (*Visit)(BTNode<T>*u), BTNode<T>*t)。前者調用后者進行遞歸，完成遍歷。先序遍歷中。先訪問當前結點的element域，在分別調用PreOrder遞歸訪問左右子樹，如果當前指針t為空，則達到遞歸邊界返回。中序遍歷和后序遍歷只在Visit訪問element出現的位置有區別，其他一樣。先序遍歷代碼：template <class T>void BTree<T>:P

7、reOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)if(t) Visit(t); PreOrder(Visit,t->lchild); PreOrder(Visit,t->rchild);中序遍歷代碼：template <class T>void BTree<T>:InOrder (void (*Visit)(BTNode<T>* u),BTNode<T>* t)if (t)InOrder(Visit,t->lchild);Visit(t); InOrder

8、(Visit,t->rchild);后序遍歷代碼：template <class T>void BTree<T>:PostOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)if (t) PostOrder(Visit,t->lchild); PostOrder(Visit,t->rchild); Visit(t);算法分析：結點數是n個，如果不考慮系統棧的消耗，由于回溯，每個結點最多訪問2次，所以時間復雜度是O（n）。4. 二叉樹的層次遍歷實現二叉樹的層次遍歷，定義一個臨時的隊列（隊列

9、中元素是指向結點的指針），首先將根節點入隊列，當對列不為空的時候：取隊首元素，輸出隊首元素，將隊首元素的左右結點入隊列，刪除隊首元素。如此循環直到隊列為空。代碼：template <class T>void BTree<T>:CenOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t) if(t=NULL) return; queue<BTNode<T>* > s;/需在頭文件加入#include <queue> s.push(t); BTNode<T> *p

10、; while(s.empty()=0) p=s.front(); Visit(p); if(p->lchild!=NULL) s.push(p->lchild); if(p->rchild!=NULL) s.push(p->rchild); s.pop(); 算法分析：While循環中每次都要pop()一個元素，結點數為n個，最終n個元素都要加入隊列，出隊列，while循環執行n次，所以時間復雜度是O（n）。空間復雜度分析：隊列s中最壞的情況是每次出去一個加入兩個，最多時候有n/2個元素，所以空間復雜度是O(n)。5. 求二叉樹的鏡像二叉樹通過面向用戶的Exch函數調

11、用Change函數進行遞歸，完成二叉樹的反轉。對于每一個結點。交換左右子樹指針的值，是左子樹指向原右子樹，右子樹指針指向原左子樹，并進入到下一次遞歸。代碼：template <class T>void BTree<T>:Change(BTNode<T> *t) if(t) Change(t->lchild); Change(t->rchild); BTNode<T> *p; p=t->lchild; t->lchild=t->rchild; t->rchild=p; 算法分析：相當于進行了一次遍歷，每一個結點訪

12、問有限次，所以時間復雜度是O（n）。6. 計算二叉樹結點數目二叉樹結點數=左子樹結點數+右子樹結點數+1。其中1是當前結點。根據這個公式編寫遞歸程序。注意遞歸邊界p=NULL返回0.代碼：template <class T>int BTree<T>:CountNode(BTNode<T> *p) if(p=NULL) return 0; else return CountNode(p->lchild)+CountNode(p->rchild)+1;算法分析：設一共n個結點，對每個結點由于回溯最多訪問兩次，所以時間復雜度是O（n）。7. 計算二叉樹

13、的高度二叉樹的高度等于所有葉子中路徑長度最大的葉子的路徑長度。調用遞歸即可完成算法。代碼：int GetHeight() return GetHeight(root);template <class T>int BTree<T>:GetHeight(BTNode<T>* t)if(!t)return 0; /若為空節點，則返回0if(!t->lchild)&&(!t->rchild) return 1; /若為葉子節點，則返回1int lHeight=GetHeight(t->lchild);int rHeight=GetH

14、eight(t->rchild);return (lHeight>rHeight?lHeight:rHeight)+1; 算法分析：遞歸過程中，每個結點都要進入，從下到上累計最大高度，時間復雜度是O（n）；8. 計算二叉樹葉子總數如果當前結點是葉子，則返回1，如果不是葉子，則返回左子樹葉子和右子樹葉子之和。代碼：int GetLeaf() return GetLeaf(root);template<class T>int BTree<T>:GetLeaf(BTNode<T> *t)if(!t)return 0;int tmp=0; if(t-&g

15、t;lchild!=NULL) tmp+=GetLeaf(t->lchild); if(t->rchild!=NULL) tmp+=GetLeaf(t->rchild); if(t->lchild=NULL&&t->rchild=NULL) return 1; return tmp;算法復雜度是O（n）。9.釋放二叉樹占用的內存空間由于二叉樹所有結點都是動態申請的，所以程序最后要編寫析構函數釋放動態內存空間。由于析構函數沒有參數，所以在析構函數調用另一個Delete函數完成這個任務。Delete函數中首先判斷當前指針參數是不是空，如果空返回（由于多

16、個二叉樹對象可能有父子關系，父親析構后再析構兒子，不判斷可能會造成內存無法訪問的錯誤）。然后調用遞歸先進入葉子結點，刪除葉子結點，再一層一層從下往上進行釋放空間。代碼：BTree() Delete();void Delete() Delete(root); root=NULL; cout<<"釋放空間完成"<<endl;template <class T>void BTree<T>:Delete(BTNode<T>* p) if(p=NULL) return; if(p->lchild!=NULL) Dele

17、te(p->lchild); if(p->rchild!=NULL) Delete(p->rchild); delete p;算法分析：每個結點遍歷刪除一次，時間復雜度是O(n)。實 驗 報 告程序測試：運行結果：結果分析：正確實 驗 報 告程序二：哈夫曼編碼譯碼系統的實現程序自定義了4個類分別是BTNode類，BinaryTree類HfmTree類,PrioQueue類，類圖如下：BTNode類中定義v用來標識當前節點是雙親的左孩子（0）還是右孩子（1），*lChild,*rChild,*parent,用來指向孩子和雙親,value字符用來存放當前結點代表的字符，也可能為空

18、，code數組用來存放當前結點的01編碼。并定義了四組重載的構造函數。BinaryTree類中數據成員定義了一個root指針，成員函數包括二叉樹構造，先序，中序，后序，層次遍歷二叉樹，二叉樹的清空釋放。HfmTree類繼承了BinaryTree類，新增了weight數據用來表示當前根節點權值，并把它作為關鍵字，成員函數新增了為weight的存取，root的置空，CreateCode（）函數對當前哈夫曼樹每一個結點產生代碼，并存放在每個結點的code數組中。getcode()函數將當前哈夫曼樹所有葉子的字符所對應的代碼一一打印。FindV（char value）函數找到參數字符對應結點的地址，并

19、返回。CodeToArticle()函數將字符串轉換成相應的01代碼，GetParents()函數將所有結點的parent賦值為雙親地址。CodeToArticle（）將輸入的01代碼或者文件中的01代碼譯碼成字符串。程序通過main函數中的switch語句跳轉到相應的功能函數中，執行相應的任務。程序定義了一個 哈夫曼樹對象Hfm 來實現哈夫曼樹中相應的操作，一個w數組保存建樹時權值，一個s數組保存建樹時字符串。核心功能代碼：1. buildtree()函數構建二叉樹：函數首先根據提示讀入字符串和對應的權值，保存到全局變量s和w中，然后調用CreateHfmTree（）函數創建哈夫曼樹，再調用

20、Hfm.GetParents()完成哈夫曼樹中結點parent指針賦值，再調用Hfm.CreateCode()完成哈夫曼樹中結點code數組來計算結點對應的01編碼序列。（1） CreateHfmTree（w,s,num）函數 （B選項）函數定義了一個優先權隊列pq，首先將每一個字符和都建成一個哈夫曼樹，加入到pq隊列中，然后每次取出weight最小的兩個哈夫曼樹，將他們權值相加建立成新的哈夫曼樹，并加入到pq隊列中，重復上述操作（n-1）次直到隊列剩下一個元素就是建好的哈夫曼樹，并返回。代碼：template<class T>HfmTree<T> CreateHfmT

21、ree(T w,char s,int n) /構造哈夫曼樹int i;PrioQueue<HfmTree<T> > pq(n);HfmTree<T> x, y, z, zero;for(i = 0; i < n; i+)z.MakeTree(wi, si, x ,y);z.putW(wi);pq.Append(z);z.SetNull();for(i = 1; i < n; i+)pq.Serve(x);pq.Serve(y);z.MakeTree(x.getW() + y.getW(),'0', x, y);z.putW(x.g

22、etW() + y.getW();pq.Append(z);z.SetNull();pq.Serve(z);return z;算法分析：將每一個結點建立成樹要n次操作，合并樹要n-1次操作，一共2*n-1次操作，時間復雜度是O(n)。pq隊列最多的時候有n個只包含一個結點的哈夫曼樹，空間復雜度是O(n)。（2） GetParents（）函數完成parent指針賦值調用遞歸，如果為空返回，如果當前結點有左孩子，則將左孩子結點的parent賦值為當前結點地址，右孩子同理，然后遞歸到下一層左孩子和右孩子中。代碼：template<class T>void HfmTree<T>

23、:GetParents(BTNode<T> * t) if(!t) return;if(t->lChild!=NULL) t->lChild->parent=t; if(t->rChild!=NULL) t->rChild->parent=t; GetParents(t->lChild); GetParents(t->rChild);算法分析：由于每個結點都要遍歷一遍，所以時間復雜度是O(n)（3） CreateCode（）函數BTNode類結點中有個數據成員為vector<int> code 數組，用來存放每一個結點的0

24、1編碼，當前結點的左孩子編碼比當前結點編碼后面多一個0，當前結點右孩子編碼比當前結點后面多一個1。根據這個調用遞歸。當前結點是左孩子還是右孩子已經在maketree時用v標識好了。代碼：template<class T>void HfmTree<T>:CreateCode(BTNode<T>* t) if(t=NULL) return ; if(t->parent) for(int i=0;i<t->parent->code.size();i+) t->code.push_back(t->parent->codei)

25、; t->code.push_back(t->v); CreateCode(t->lChild); CreateCode(t->rChild);算法分析：對每個結點都要遞歸遍歷到，每個結點賦值平局情況是n/2次，所以時間復雜度是O(n2)。除了根節點，每個結點都有一個code數組（vector）,平均每個結點code長度是n/2，所以空間復雜度是O(n2)。2. BianLi()函數對當前哈夫曼樹進行遍歷（T選項）先序，中序，后序，層次遍歷算法本報告上面一個程序已經有了，這個地方就不在闡述了。3. Hfm.getcode()函數輸出當前編碼方案（E選項）調用遞歸，如果當

26、前遞歸到的結點是葉子，則首先打印出葉子代表的字符，然后打印出葉子節點的code數組。如果遞歸到的結點是空，則返回。如果是中間的結點，則遞歸的下一層左孩子和右孩子。代碼：template<class T>void HfmTree<T>:getcode(BTNode<T>* t) if(t=NULL) return; if(t->lChild=NULL)&&(t->rChild=NULL) cout<<t->value<<":" for(int i=0;i<t->code.

27、size();i+) cout<<t->codei; cout<<endl; getcode(t->lChild); getcode(t->rChild);4. ArticleToCode()函數對字符串進行編碼(C選項)定義一個string類對象ss用來讀取需要翻譯的字符串。用for循環，對ss中每一個字符，調用哈夫曼中的FindV（）尋找字符的地址并賦值到p指針，然后打印出p中的code數組。最后寫入到文件即可。代碼:void ArticleToCode() /Cofstream foutt("textfile.txt");if

28、(!foutt)cout<<"Cannot open textfile.txt!"<<endl;return ;ofstream foutc("codefile.txt");if(!foutc)cout<<"Cannot open codefile.txt!"<<endl;return ;cout<<"Please input the article that you want to code: (end with Enter)"<<endl;

29、getchar();string ss;getline(cin,ss);foutt<<ss;for(int i=0;i<ss.size();i+) BTNode<int> *p=Hfm.FindV(ssi); if(p=NULL) printf("未找到字符 %c n",ssi); continue; for(int j=0;j<p->code.size();j+) printf("%d",p->codej); char cc=p->codej+'0' foutc<<cc;

30、 cout<<endl<<endl; cout<<"Encoding complete."<<endl<<endl;foutt.close();foutc.close();算法分析：對每一個字符都要調用FinV（）函數進行查找，查找的平均情況是找n/2個結點，FindV的時間復雜度是O(n)，字符有n個，綜上，時間復雜度是O(n2)。5. CodeToArticle()函數 進行譯碼 (D選項)定義一個string類ccs用來保存需要進行譯碼的字符串，如果要輸入01進行譯碼，則ccs用cin讀取，如果要對文件譯碼，

31、則ccs從文件讀取。將指針p指向哈夫曼樹root，對ccs中字符，如果是0則進入左孩子，如果是1就進入右孩子，如果當前結點是葉子，就將結點代表的字符打印并寫入到文件，并將p重置到root繼續上述操作。代碼：template<class T>void HfmTree<T>:CodeToArticle() CodeToArticle(this->root);template<class T>void HfmTree<T>:CodeToArticle(BTNode<T>* t) ofstream foutr("resultf

32、ile.txt");if(!foutr)cout<<"Cannot open resultfile.txt!"<<endl;return ;char c;ifstream foutc("codefile.txt");if(!foutc)cout<<"Cannot open codefile.txt!"<<endl;return ;cout<<"請輸入選項:"<<endl<<"1. 輸入01代碼進行譯碼"

33、<<endl<<"2. 對codefile.txt文件中01代碼進行譯碼"<<endl;int choice; string ccs; cin>>choice; if(choice=2) foutc>>ccs; else if(choice=1) cout<<"輸入代碼,無空格，回車結束"<<endl; string cc; getchar(); cin>>ccs; else return; int i=0; while(i<ccs.size() BTN

34、ode<int> *p=t; while(p->lChild!=NULL|p->rChild!=NULL) if(ccsi='0') p=p->lChild; else p=p->rChild; i+; printf("%c ",p->value); foutr<<(p->value); cout<<endl<<endl;算法分析:對每一個01字符只要進行一次操作(進入孩子或者打印)，所以時間復雜度是O(n).6. Print()打印文件內容（P選項）定義一個string類對

35、象ss，將文件流輸入到ss中，然后輸出ss中內容即可.代碼：void Print() ifstream foutt("textfile.txt");if(!foutt)cout<<"Cannot open textfile.txt!"<<endl;return ;cout<<endl<<"-textfile.txt-"<<endl;string ss;while(foutt>>ss) cout<<ss<<" " cout<<endl<<"-"<<endl;foutt.close();ifstream foutc("codefile.txt");if(!foutc)cout<<"Cannot open codefile