1、實 驗 報 告（2014 / 2015 學年 第 一 學期）課程名稱數據結構實驗名稱二叉樹基本操作以及哈夫曼編碼譯碼系統實驗時間 年月日指導單位指導教師學生姓名班級學號學院(系)專 業二叉樹的基本運算：1、 問題描述1. 設計遞歸算法，實現二叉樹的運算：刪除一棵二叉樹，求一棵二叉樹的高度，求一棵二叉樹中葉子節點數，復制一棵二叉樹，交換一棵二叉樹的左右子樹2. 設計算法，自上而下，自左向右即按層次遍歷一棵二叉樹3. 設計main函數，測試上述每個運算二、系統分析和概要設計首先用maketree構造一棵二叉樹，然后遍歷二叉樹，然后交換每個結點的左右子樹，接著算出輸得高度和葉子節點，最后刪除。三、詳

2、細設計T1. 類和類的層次結構BinaryTree#BTNode<T> * root-static int number+BinaryTree()+BinaryTree()+void Copy(BinaryTree<T> &r) const+bool IsEmpty()const+void Clear()+void Exchange()+bool Root(T& x)const;+int GetHeight()+voidMakeTree(const T& x,BinaryTree<T>& left,BinaryTree<

3、T>& right)+void BreakTree(T&x,BinaryTree<T>& left,BinaryTree<T>& right)+void PreOrder(void (*Visit)(T &x)+void LevelOrder(void (*Visit)(T& x)+int Size()+BinaryTree<T>(BinaryTree<T> &t)+BTNode<T>* Copy(BTNode<T>* t)-void Clear(BTNode&

4、lt;T>* &t)-void Exchange(BTNode<T>* t)-int GetHeight(BTNode<T>* t)-int Size(BTNode<T>* t)-void PreOrder(void (*Visit)(T &x),BTNode<T>* t)-void LevelOrder(void (*Visit)(T& x),BTNode<T>* t) 2. 核心算法建立二叉樹的void MakeTree(const T& x,BinaryTree<T>&

5、left,BinaryTree<T>& right)和計算葉子節點的int Size();3. 算法分析刪除一棵二叉樹，求一棵二叉樹的高度，求一棵二叉樹中葉子節點數，復制一棵二叉樹等都是用遞歸的方法實現。4、 程序代碼建立二叉樹樹 遍歷二叉樹葉子節點數量樹的高度 左右交換復制二叉樹刪除二叉樹 流程圖 #include<iostream.h>template<class T>struct BTNodeBTNode()lChild=rChild=NULL;BTNode(const T &x)element=x;lChild=rChild=NULL

6、;BTNode(const T &x,BTNode<T>* l,BTNode<T>* r)element=x;lChild=l;rChild=r;T element;BTNode<T>* lChild,* rChild;template<class T>class BinaryTreepublic:BinaryTree()root=NULL;BinaryTree()Clear();void Copy(BinaryTree<T> &r) const;bool IsEmpty()constreturn root = NUL

7、L;void Clear();void Exchange();bool Root(T& x)const;int GetHeight();void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right);void BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right);void PreOrder(void (*Visit)(T &x);void LevelOrd

8、er(void (*Visit)(T& x);int Size();BinaryTree<T>(BinaryTree<T> &t)root=Copy(t.root);/void InOrder(void (*Visit)(T &x);/void PostOrder(void (*Visit)(T &x);BTNode<T>* Copy(BTNode<T>* t);protected:BTNode<T> * root;private:static int number;void Clear(BTNode&

9、lt;T>* &t);void Exchange(BTNode<T>* t);int GetHeight(BTNode<T>* t);int Size(BTNode<T>* t);void PreOrder(void (*Visit)(T &x),BTNode<T>* t);void LevelOrder(void (*Visit)(T& x),BTNode<T>* t);/void InOrder(void (*Visit)(T &x),BTNode<T>* t);/ void Po

10、stOrder(void (*Visit)(T &x),BTNode<T>* t);template <class T>bool BinaryTree<T>:Root(T &x)constif(root)x=root->element;return true;else return false;template <class T>void BinaryTree<T>:Clear()Clear(root);template <class T>void BinaryTree<T>:Clear(

11、BTNode<T>* &t)if(t)Clear(t->lChild);Clear(t->rChild);delete t;t=NULL;template <class T>void BinaryTree<T>:MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right)if(root|&left=&right)return;root=new BTNode <T>(x,left.root,right.r

12、oot);left.root=right.root=NULL;template <class T>void BinaryTree<T>:BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right)if(!root|&left=&right|left.root|right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;delete roo

13、t;root=NULL;template <class T>BTNode<T>* BinaryTree<T>:Copy(BTNode<T>* t)if(!t)return NULL;BTNode<T>*q=new BTNode<T>(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);return q;template <class T>void Visit(T &x)cout<<x&l

14、t;<" "template <class T>void BinaryTree<T>:PreOrder(void (*Visit)(T& x)PreOrder(Visit,root);template <class T>void BinaryTree<T>:PreOrder(void (*Visit)(T& x),BTNode<T>* t)if(t)Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rC

15、hild);template <class T>void BinaryTree<T>:Exchange()Exchange(root);template <class T>void BinaryTree<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)

16、;template <class T>int BinaryTree<T>:GetHeight()return GetHeight(root);template <class T>int BinaryTree<T>:GetHeight(BTNode<T>* t)int templ;int tempr;if(!t)return 0;templ=GetHeight(t->lChild);tempr=GetHeight(t->rChild);if(templ+>tempr+)return templ;elsereturn t

17、empr;template <class T>int BinaryTree<T>:number=0;template <class T>int BinaryTree<T>:Size()Size(root);return number;template <class T>int BinaryTree<T>:Size(BTNode<T>* t)if(t!=NULL)Size(t->lChild);if(t->lChild =NULL&&t->rChild =NULL)number+

18、;Size(t->rChild);return number;template <class T>void BinaryTree<T>:LevelOrder(void (*Visit)(T& x)PreOrder(Visit,root);template <class T>void BinaryTree<T>:LevelOrder(void (*Visit)(T& x),BTNode<T>* t)BTNode *quene50,*p;int pre=1,rear=1;quene+pre=t;while(pre!=

19、0)p=quene+rear;cout<<p->element<<" "if(p->lChild !=NULL)quene+pre=p->rChild ;if(p->rChild !=NULL)quene+pre=p->lChild ;void main()BinaryTree <char> a,b,x,y,z;y.MakeTree('E',a,b);z.MakeTree('F',a,b);x.MakeTree('C',y,z);y.MakeTree('

20、D',a,b);z.MakeTree('B',y,x);cout<<"二叉樹z的先序遍歷:"<<endl;z.PreOrder(Visit);cout<<endl;cout<<"層次遍歷二叉樹:"z.LevelOrder(Visit);cout<<endl;BinaryTree<char> q(z);cout<<"復制的二叉樹q的先序遍歷:"<<endl;q.PreOrder(Visit);cout<<e

21、ndl;cout<<"樹的高度:"cout<<z.GetHeight()<<endl;cout<<"葉子節點數量:"cout<<z.Size()<<endl;z.Exchange();cout<<"二叉樹左右子樹交換后的先序遍歷:"<<endl;z.PreOrder(Visit);cout<<endl;五、測試用例和運行結果測試用例如main函數中所示，結果如下圖所示。哈夫曼編碼和譯碼系統：一、問題描述1.所設計的系統重復顯示以

22、下菜單B-建樹：讀入字符集和各字符頻度T-遍歷：先序和中序遍歷二叉樹E-生成代碼：根據已經簡稱的哈夫曼數生成代碼，產生各字符的哈夫曼樹C-編碼：輸入由字符集中字符組成的任意字符串，利用已經生成的哈夫曼編碼進行編碼，顯示編碼結果，并將輸入的字符串及其編碼結果分別保存在磁盤文件textfile.txt和codefile.txt中D-譯碼：讀入codefile.txt，利用已經建成的哈夫曼樹進行譯碼，并將譯碼結果存入磁盤文件result.txtP-打印：屏幕顯示文件textfile.txt 、codefile.txt、 resultfile.txtX-退出二、系統分析和概要設計主要包括實現主菜單以及

23、菜單里每個函數的功能（創建函數實現接收字符，接收權值，構建哈夫曼樹并保存文件，編碼函數實現對用戶輸入的秘文進行哈夫曼編碼，即對每個字符翻譯出其密文代碼并保存文件，譯碼函數實現譯碼即輸出密文的源碼）。三、詳細設計T1. 類和類的層次結構BinaryTree#BTNode<T> * root-static int number+BinaryTree()+BinaryTree()+bool IsEmpty()const+void Clear()+bool Root(T& x)const;+voidMakeTree(const T& x,BinaryTree<T>

24、;& left,BinaryTree<T>& right)+void BreakTree(T&x,BinaryTree<T>& left,BinaryTree<T>& right)+void PreOrder()+void inOrder() +void leaf()+void visit(T& x) +-void postOrder() -void Clear(BTNode<T>* &t)-void PreOrder(,BTNode<T>* t)-void prePrint(B

25、TNode<T>* t)-void inOrder(BTNode<T>* t)-void postOrder(BTNode<T>* t)PrioQueue-T* q;-int n,maxSize;+PrioQueue(int mSize=20)+PrioQueue()+bool IsEmpty() const+bool IsFull() const+void Append(const T &x)+void Serve(T& x)-void AdjustDown (int r, int j)-void AdjustUp (int j)T THf

26、mTree-T weight+operator T()const+T getW()+void putW(const T& x)+void SetNull() +void code(string& c) +void decode(string s)-void code(BTNode<T>* t, string& c)2. 核心算法TT實現優先權隊列的Append(x)以及Serve(x)函T數以及AdjustUp() 、AdjustDown()函數3. 算法分析時間復雜度均為O(n)四、程序代碼#include <iostream>#include

27、 <string>using namespace std;int *weightArray;string s;string *codeArray;template <class T>struct BTNode BTNode() lChild = rChild = NULL; BTNode(const T& x) element = x; lChild = rChild = NULL; BTNode(const T& x, BTNode<T>* l, BTNode<T>* r) element = x; lChild = l; rC

28、hild = r; T element; BTNode<T> *lChild, *rChild;template<class T>class BinaryTree public:BinaryTree()root = NULL;BinaryTree() Clear();bool isEmpty() const return root = NULL;void Clear()Clear(root);bool Root(T& x) const;void makeTree(const& x, BinaryTree<T>& left, Binar

29、yTree<T>& right);void breakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right);void preOrder() preOrder(root);void inOrder() inOrder(root);void postOrder() postOrder(root);void leaf()prePrint(root);void visit(T& x) cout << x << " "protect

30、ed:BTNode<T>* root;private:void Clear(BTNode<T>* t);void prePrint(BTNode<T>* t);void preOrder(BTNode<T>* t);void inOrder(BTNode<T>* t);void postOrder(BTNode<T>* t);template <class T> bool BinaryTree<T>:Root(T& x) constif (root) x = root -> eleme

31、nt;return true;elsereturn false;template <class T> void BinaryTree<T>:makeTree(const& x, BinaryTree<T>& left, BinaryTree<T>& right)if (root | &left = &right) return;root = new BTNode<T>(x, left.root, right.root);left.root = right.root = NULL;template

32、 <class T> void BinaryTree<T>:breakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right) if (!root | &left = &right | left.root | right.root) return;x = root -> element;left.root = root -> lChild;right.root = root -> rChild;delete root;root = NULL

33、;template <class T>void BinaryTree<T>:preOrder(BTNode<T>* t) if (t)visit(t -> element);preOrder(t -> lChild);preOrder(t -> rChild);template <class T>void BinaryTree<T>:inOrder(BTNode<T>* t)if (t)inOrder(t -> lChild);visit(t -> element);inOrder(t -&g

34、t; rChild);template <class T>void BinaryTree<T>:postOrder(BTNode<T>* t) if (t) postOrder(t -> lChild);postOrder(t -> rChild);visit(t -> element);template <class T>void BinaryTree<T>:Clear(BTNode<T>* t) if(t)Clear(t->lChild);Clear(t->rChild);delete t

35、;t=NULL;template <class T>void BinaryTree<T>:prePrint(BTNode<T>* t)if (t) if (t -> lChild = NULL) && (t -> rChild = NULL) visit(t -> element);return;prePrint(t -> lChild);prePrint(t -> rChild);template<class T>class PrioQueue public:PrioQueue(int mSize=

36、20);PrioQueue()delete q;bool IsEmpty() constreturn n=0;bool IsFull() constreturn n=maxSize;void Append(const T &x);void Serve(T& x);private:void AdjustDown (int r, int j);void AdjustUp (int j);T* q;int n,maxSize;template <class T>PrioQueue<T>:PrioQueue(int mSize) maxSize=mSize; n

37、=0;q=new TmaxSize;template <class T>void PrioQueue<T>:AdjustUp (int j) int i=j;T temp=qi;while (i>0 && temp<q(i-1)/2)qi=q(i-1)/2; i=(i-1)/2; qi=temp;template <class T>void PrioQueue<T>:Append(const T &x)if(IsFull() cout<< "Overflow"return;qn+

38、=x;AdjustUp(n-1);template <class T>void PrioQueue<T>:Serve(T& x)if(IsEmpty()cout<< "Underflow"return;x=q0;q0=q-n;AdjustDown (0, n-1);template <class T>void PrioQueue<T>:AdjustDown (int r, int j) int child = 2 * r + 1;T temp = qr;while (child <= j) if (c

39、hild < j) && (qchild > qchild + 1) child+;if (temp <= qchild) break;q(child - 1) / 2 = qchild;child = 2 * child + 1;q(child - 1) / 2 = temp;template <class T>class HfmTree: public BinaryTree<T>public:operator T()const return weight;T getW()return weight;void putW(const T

40、& x) weight=x; void SetNull()root=NULL; void code(string& c) code(root, c);void decode(string s);private:T weight;void code(BTNode<T>* t, string& c);template <class T>void HfmTree<T>:decode(string decodeString)if (codeArray = NULL) cout << "尚未編碼！" <&l

41、t; endl;return;BTNode<T>* searchNode = root;for (int i = 0; i < decodeString.length(); i+) if (decodeStringi != '0' && decodeStringi != '1') cout << "碼格式不正確！" << endl;return;if (searchNode -> lChild = NULL && searchNode -> rChild =

42、 NULL)T value = searchNode -> element;for (int j = 0; j < s.length(); j+)if (value = weightArrayj) cout << sj;break;searchNode = root;if (decodeStringi = '0') searchNode = searchNode -> lChild;if (decodeStringi = '1') searchNode = searchNode -> rChild;if (searchNode

43、 -> lChild = NULL && searchNode -> rChild = NULL) T value = searchNode -> element;for (int j = 0; j < s.length(); j+)if (value = weightArrayj)cout << sj;break;cout << endl;template <class T>void HfmTree<T>:code(BTNode<T>* t, string& c) if (t) if

44、(t -> lChild = NULL && t -> rChild = NULL) for (int i = 0; i < s.length(); i+) if (t -> element = weightArrayi) codeArrayi = c;/cout << "NO" << i << " "cout << "字符" << si << "的權重是" << weightArrayi &

45、lt;< ", 哈弗曼編碼是" << codeArrayi << endl; break;if (t -> lChild != NULL) string ls;ls.assign(c);ls.append("0");code(t -> lChild, ls);if (t -> rChild != NULL) string rs;rs.assign(c);rs.append("1");code(t -> rChild, rs);template <class T>HfmT

46、ree<T> CreateHfmTree (T *w,int n)PrioQueue <HfmTree<T> > pq(n); HfmTree<T> x,y,z; for (int i=0;i<n;i+) z.makeTree(wi,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(),x,y); z.putW(x.getW()+y.getW();pq.App

47、end(z); z.SetNull(); pq.Serve(z); return z; void input(HfmTree<int>& p)cout << "請輸入需要編碼的字符組成的字符串: "cin >> s;weightArray = new ints.length();codeArray = new strings.length();for (int i = 0; i < s.length(); i+) cout << "請輸入第" << (i + 1) << "個字符的權值：" << endl;cin >> weightArrayi;p = CreateHfmTree(weightArray, s.length();/p.postOrder();void createCode(HfmTree<int>& p) if (codeArra