二叉樹基本操作以及哈夫曼編碼譯碼系統(tǒng)

1、實(shí) 驗(yàn) 報(bào) 告（2015 / 2016 學(xué)年 第 二 學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱二叉樹基本操作以及哈夫曼編碼譯碼系統(tǒng)實(shí)驗(yàn)時(shí)間 2016年4月14日指導(dǎo)單位南京郵電大學(xué)指導(dǎo)教師駱健學(xué)生姓名吳佳瑤班級學(xué)號B14111708學(xué)院(系) 管理學(xué)院專 業(yè)信息管理與信息系統(tǒng)二叉樹的基本運(yùn)算：1、 問題描述1. 設(shè)計(jì)遞歸算法，實(shí)現(xiàn)二叉樹的運(yùn)算：刪除一棵二叉樹，求一棵二叉樹的高度，求一棵二叉樹中葉子節(jié)點(diǎn)數(shù)，復(fù)制一棵二叉樹，交換一棵二叉樹的左右子樹2. 設(shè)計(jì)算法，自上而下，自左向右即按層次遍歷一棵二叉樹3. 設(shè)計(jì)main函數(shù)，測試上述每個(gè)運(yùn)算二、系統(tǒng)分析和概要設(shè)計(jì)首先用maketree構(gòu)造一棵二叉樹，然后遍

2、歷二叉樹，然后交換每個(gè)結(jié)點(diǎn)的左右子樹，接著算出輸?shù)酶叨群腿~子節(jié)點(diǎn)，最后刪除。三、詳細(xì)設(shè)計(jì)T1. 類和類的層次結(jié)構(gòu)BinaryTree#BTNode * root-static int number+BinaryTree()+BinaryTree()+void Copy(BinaryTree &r) const+bool IsEmpty()const+void Clear()+void Exchange()+bool Root(T& x)const;+int GetHeight()+voidMakeTree(const T& x,BinaryTree& left,BinaryTree& righ

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

4、 (*Visit)(T &x),BTNode* t)-void LevelOrder(void (*Visit)(T& x),BTNode* t) 2. 核心算法建立二叉樹的void MakeTree(const T& x,BinaryTree& left,BinaryTree& right)和計(jì)算葉子節(jié)點(diǎn)的int Size();3. 算法分析刪除一棵二叉樹，求一棵二叉樹的高度，求一棵二叉樹中葉子節(jié)點(diǎn)數(shù)，復(fù)制一棵二叉樹等都是用遞歸的方法實(shí)現(xiàn)。四、 程序代碼建立二叉樹樹用maketree構(gòu)造一棵二叉樹遞歸遍歷二叉樹根據(jù)二叉樹的定義和遍歷算法的定義，和很容易實(shí)現(xiàn)層次遍歷二叉樹節(jié)點(diǎn)數(shù)量用隊(duì)列實(shí)現(xiàn)，將

5、跟結(jié)點(diǎn)入隊(duì)。一：出隊(duì)并輸出節(jié)點(diǎn)的值。二： 若存在左右孩子，則將其入隊(duì)。循環(huán)以上兩個(gè)步驟，直到隊(duì)列為空。運(yùn)用后序遍歷思想，把樹分解為左右子樹和跟結(jié)點(diǎn)左右交換本質(zhì)就是交換每個(gè)結(jié)點(diǎn)的左右子樹樹的高度左右子樹高度之和進(jìn)行比較，誰大誰就是樹的高度刪除二叉樹先刪除左子樹，再刪除右子樹，最后刪除根節(jié)點(diǎn)，再釋放結(jié)點(diǎn)空間一先序遍歷：template void BinaryTree:PreOrder(void (*Visit)(T& x)PreOrder(Visit,root);templatevoid BinaryTree:PreOrder(void (*Visit)(T& x),BTNode* t)if(t)

6、Visit(t-element);PreOrder(Visit,t-lChild)；PreOrder(Visit,t-rChild);二中序遍歷：template void BinaryTree:InOrder(void (*Visit)(T& x)InOrder(Visit,root);templatevoid BinaryTree:InOrder(void (*Visit)(T& x),BTNode* t)if(t)InOrder(Visit,t-lChild);Visit(t-element);InOrder(Visit,t-rChild);三后序遍歷：template void Bin

7、aryTree:PostOrder(void (*Visit)(T& x)PostOrder(Visit,root);template void BinaryTree:PostOrder(void (*Visit)(T& x),BTNode* t)if(t)PostOrder(Visit,t-lChild);PostOrder(Visit,t-rChild);Visit(t-element);四層次遍歷二叉樹：template void BinaryTree:FloorOrder(void (*Visit)(T &x) FloorOrder(Visit,root);template void

8、BinaryTree:;FloorOrder(void(*Visit)(Visit*x),BTNode*t) SeqQueueBTNode*se(100); se.EnQueue(t); BTNode*temp; while(!se.IsEmpty() se.Front(temp); Visit(temp); se.DeQueue(); if(temp-lchild) se.EnQueue(temp-lchild); if(temp-child) se.EnQueue(temp-rchild); 五求二叉樹的結(jié)點(diǎn)數(shù)：template int BinaryTree:Size()return Si

9、ze(root);template int BinaryTree:Size(BTNode* t)if(!t)return 0;elsereturn Size(t-lChild)+Size(t-rChild)+1;六二叉樹的左右交換:template void BinaryTree:Exchange()Exchange(root);template void BinaryTree:Exchange(BTNode* t)if(!t)return;BTNode* temp;temp=t-lChild;t-lChild=t-rChild;t-rChild=temp;Exchange(t-lChild)

10、;Exchange(t-rChild);七求二叉樹的深度：template int BinaryTree:GetHeight(BTNode* t)int templ;int tempr;if(!t)return 0;templ=GetHeight(t-lChild);tempr=GetHeight(t-rChild);if(templ+tempr+)return templ;elsereturn tempr;五、測試用例和運(yùn)行結(jié)果測試用例結(jié)果如下圖所示。哈夫曼編碼和譯碼系統(tǒng)：一、問題描述1.所設(shè)計(jì)的系統(tǒng)重復(fù)顯示以下菜單B-建樹：讀入字符集和各字符頻度T-遍歷：先序和中序遍歷二叉樹E-生成代碼：

11、根據(jù)已經(jīng)簡稱的哈夫曼數(shù)生成代碼，產(chǎn)生各字符的哈夫曼樹C-編碼：輸入由字符集中字符組成的任意字符串，利用已經(jīng)生成的哈夫曼編碼進(jìn)行編碼，顯示編碼結(jié)果，并將輸入的字符串及其編碼結(jié)果分別保存在磁盤文件textfile.txt和codefile.txt中D-譯碼：讀入codefile.txt，利用已經(jīng)建成的哈夫曼樹進(jìn)行譯碼，并將譯碼結(jié)果存入磁盤文件result.txtP-打?。浩聊伙@示文件textfile.txt 、codefile.txt、 resultfile.txtX-退出二、系統(tǒng)分析和概要設(shè)計(jì)主要包括實(shí)現(xiàn)主菜單以及菜單里每個(gè)函數(shù)的功能（創(chuàng)建函數(shù)實(shí)現(xiàn)接收字符，接收權(quán)值，構(gòu)建哈夫曼樹并保存文件，編碼

12、函數(shù)實(shí)現(xiàn)對用戶輸入的秘文進(jìn)行哈夫曼編碼，即對每個(gè)字符翻譯出其密文代碼并保存文件，譯碼函數(shù)實(shí)現(xiàn)譯碼即輸出密文的源碼）。三、詳細(xì)設(shè)計(jì)T1. 類和類的層次結(jié)構(gòu)BinaryTree#BTNode * root-static int number+BinaryTree()+BinaryTree()+bool IsEmpty()const+void Clear()+bool Root(T& x)const;+voidMakeTree(const T& x,BinaryTree& left,BinaryTree& right)+void BreakTree(T&x,BinaryTree& left,Bina

13、ryTree& right)+void PreOrder()+void inOrder() +void leaf()+void visit(T& x) +-void postOrder() -void Clear(BTNode* &t)-void PreOrder(,BTNode* t)-void prePrint(BTNode* t)-void inOrder(BTNode* t)-void postOrder(BTNode* t)PrioQueue-T* q;-int n,maxSize;+PrioQueue(int mSize=20)+PrioQueue()+bool IsEmpty()

14、 const+bool IsFull() const+void Append(const T &x)+void Serve(T& x)-void AdjustDown (int r, int j)-void AdjustUp (int j)T THfmTree-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, string& c)2. 核心算法TT實(shí)現(xiàn)優(yōu)先權(quán)隊(duì)列的App

15、end(x)以及Serve(x)函T數(shù)以及AdjustUp() 、AdjustDown()函數(shù)3. 算法分析時(shí)間復(fù)雜度均為O(n)四、程序代碼#include #include using namespace std;int *weightArray;string s;string *codeArray;template struct BTNode BTNode() lChild = rChild = NULL; BTNode(const T& x) element = x; lChild = rChild = NULL; BTNode(const T& x, BTNode* l, BTNod

16、e* r) element = x; lChild = l; rChild = r; T element; BTNode *lChild, *rChild;templateclass 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& left, BinaryTree& right

17、);void breakTree(T& x, BinaryTree& left, BinaryTree& right);void preOrder() preOrder(root);void inOrder() inOrder(root);void postOrder() postOrder(root);void leaf()prePrint(root);void visit(T& x) cout x ;protected:BTNode* root;private:void Clear(BTNode* t);void prePrint(BTNode* t);void preOrder(BTNo

18、de* t);void inOrder(BTNode* t);void postOrder(BTNode* t);template bool BinaryTree:Root(T& x) constif (root) x = root - element;return true;elsereturn false;template void BinaryTree:makeTree(const& x, BinaryTree& left, BinaryTree& right)if (root | &left = &right) return;root = new BTNode(x, left.root

19、, right.root);left.root = right.root = NULL;template void BinaryTree:breakTree(T& x, BinaryTree& left, BinaryTree& 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;template void BinaryTr

20、ee:preOrder(BTNode* t) if (t)visit(t - element);preOrder(t - lChild);preOrder(t - rChild);template void BinaryTree:inOrder(BTNode* t)if (t)inOrder(t - lChild);visit(t - element);inOrder(t - rChild);template void BinaryTree:postOrder(BTNode* t) if (t) postOrder(t - lChild);postOrder(t - rChild);visit

21、(t - element);template void BinaryTree:Clear(BTNode* t) if(t)Clear(t-lChild);Clear(t-rChild);delete t;t=NULL;template void BinaryTree:prePrint(BTNode* t)if (t) if (t - lChild = NULL) & (t - rChild = NULL) visit(t - element);return;prePrint(t - lChild);prePrint(t - rChild);templateclass PrioQueue pub

22、lic:PrioQueue(int mSize=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 PrioQueue:PrioQueue(int mSize) maxSize=mSize; n=0;q=new

23、 TmaxSize;template void PrioQueue:AdjustUp (int j) int i=j;T temp=qi;while (i0 & tempq(i-1)/2)qi=q(i-1)/2; i=(i-1)/2; qi=temp;template void PrioQueue:Append(const T &x)if(IsFull() cout Overflow;return;qn+=x;AdjustUp(n-1);template void PrioQueue:Serve(T& x)if(IsEmpty()cout Underflow;return;x=q0;q0=q-

24、n;AdjustDown (0, n-1);template void PrioQueue:AdjustDown (int r, int j) int child = 2 * r + 1;T temp = qr;while (child = j) if (child qchild + 1) child+;if (temp = qchild) break;q(child - 1) / 2 = qchild;child = 2 * child + 1;q(child - 1) / 2 = temp;template class HfmTree: public BinaryTreepublic:op

25、erator T()const return weight;T getW()return weight;void putW(const T& 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, string& c);template void HfmTree:decode(string decodeString)if (codeArray = NULL) cout 尚未編碼！ end

26、l;return;BTNode* searchNode = root;for (int i = 0; i decodeString.length(); i+) if (decodeStringi != 0 & decodeStringi != 1) cout 碼格式不正確！ lChild = NULL & searchNode - rChild = NULL)T value = searchNode - element;for (int j = 0; j s.length(); j+)if (value = weightArrayj) cout lChild;if (decodeStringi

27、 = 1) searchNode = searchNode - rChild;if (searchNode - 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 void HfmTree:code(BTNode* t, string& c) if (t) if (t - lChild = NULL & t - rCh

28、ild = NULL) for (int i = 0; i element = weightArrayi) codeArrayi = c;/cout NO i ;cout 字符 si 的權(quán)重是 weightArrayi , 哈夫曼編碼是 codeArrayi 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 HfmTree

29、 CreateHfmTree (T *w,int n)PrioQueue HfmTree pq(n); HfmTree x,y,z; for (int i=0;in;i+) z.makeTree(wi,x,y); z.putW(wi); pq.Append(z); z.SetNull(); for (i=1;in;i+)pq.Serve(x); pq.Serve(y); z.makeTree(x.getW()+y.getW(),x,y); z.putW(x.getW()+y.getW();pq.Append(z); z.SetNull(); pq.Serve(z); return z; voi

30、d input(HfmTree& p)cout s;weightArray = new ints.length();codeArray = new strings.length();for (int i = 0; i s.length(); i+) cout 請輸入第 (i + 1) 個(gè)字符的權(quán)值： weightArrayi;p = CreateHfmTree(weightArray, s.length();/p.postOrder();void createCode(HfmTree& p) if (codeArray = NULL) cout 樹為空！ endl;return;string

31、c;p.code(c);void encode()if (codeArray = NULL) cout 尚未編碼！ endl;return;string encodeString;cout encodeString;cout n經(jīng)過編碼的碼值為：;for (int i = 0; i encodeString.length(); i+) for (int j = 0; j s.length(); j+) if (sj = encodeStringj) cout codeArrayj;break;cout endl;void main() bool flag = true;HfmTree p;st

32、ring decodeString;while (flag) cout*B建樹*endl;cout*T遍歷*endl;cout*E生成編碼*endl;cout*C編碼*endl;cout*D譯碼*endl;cout*X退出*endl;cout c;cout endl;switch (c) case B:input(p);break;case T:if (p != NULL) cout 前序遍歷：;p.preOrder();cout endl;cout 中序遍歷：;p.inOrder();cout endl;cout 后序遍歷：;p.postOrder();cout endl;else cout

33、 尚未建樹！ endl;break;case E:createCode(p);break;case C:encode();break;case D:cout decodeString;p.decode(decodeString);break;case X:flag = false;break;5、 測試用例和運(yùn)行結(jié)六、實(shí)驗(yàn)小結(jié)通過這次實(shí)驗(yàn)，我對一個(gè)二叉樹以及哈夫曼有著更加全面深刻的認(rèn)識，會(huì)采用不同的數(shù)據(jù)存儲方式，如之前的棧，現(xiàn)在的二叉樹等，可以提高了程序的運(yùn)行效率。在編寫這個(gè)程序的過程中，對如哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應(yīng)用范圍，二叉樹的復(fù)制及遍歷等問題。在這次實(shí)驗(yàn)，體會(huì)到了編完

34、程序的滿足感，也從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱的地方加以改進(jìn)。程序代碼:一、#includetemplatestruct BTNodeBTNode()lChild=rChild=NULL;BTNode(const T &x)element=x;lChild=rChild=NULL;BTNode(const T &x,BTNode* l,BTNode* r)element=x;lChild=l;rChild=r;T element;BTNode* lChild,* rChild;templateclass BinaryTreepublic:BinaryTree()root=NULL;Binar

35、yTree()Clear();void Copy(BinaryTree &r) const;bool IsEmpty()constreturn root = NULL;void Clear();void Exchange();bool Root(T& x)const;int GetHeight();void MakeTree(const T& x,BinaryTree& left,BinaryTree& right);void BreakTree(T& x,BinaryTree& left,BinaryTree& right);void PreOrder(void (*Visit)(T &x)

36、;void LevelOrder(void (*Visit)(T& x);int Size();BinaryTree(BinaryTree &t)root=Copy(t.root);/void InOrder(void (*Visit)(T &x);/void PostOrder(void (*Visit)(T &x);BTNode* Copy(BTNode* t);protected:BTNode * root;private:static int number;void Clear(BTNode* &t);void Exchange(BTNode* t);int GetHeight(BTN

37、ode* t);int Size(BTNode* t);void PreOrder(void (*Visit)(T &x),BTNode* t);void LevelOrder(void (*Visit)(T& x),BTNode* t);/void InOrder(void (*Visit)(T &x),BTNode* t);/ void PostOrder(void (*Visit)(T &x),BTNode* t);template bool BinaryTree:Root(T &x)constif(root)x=root-element;return true;else return

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

39、oot=right.root=NULL;template void BinaryTree:BreakTree(T& x,BinaryTree& left,BinaryTree& 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;template BTNode* BinaryTree:Copy(BTNode* t)if(!t)return NULL;BTNode*q=new

40、 BTNode(t-element);q-lChild=Copy(t-lChild);q-rChild=Copy(t-rChild);return q;template void Visit(T &x)coutx ;template void BinaryTree:PreOrder(void (*Visit)(T& x)PreOrder(Visit,root);template void BinaryTree:PreOrder(void (*Visit)(T& x),BTNode* t)if(t)Visit(t-element);PreOrder(Visit,t-lChild);PreOrder(Visit,t-rChild);template void BinaryTree:Exc