二叉樹與哈夫曼編碼

1、實(shí) 驗(yàn) 報(bào) 告（ 2014/ 2015 學(xué)年 第 二 學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱實(shí)驗(yàn)二 二叉樹的基本操作及哈夫曼編碼譯碼系統(tǒng)的實(shí)現(xiàn)實(shí)驗(yàn)時(shí)間2015年10月31日指導(dǎo)單位計(jì)算機(jī)軟件學(xué)院指導(dǎo)教師駱健學(xué)生姓名陳兵班級(jí)學(xué)號(hào)B14041126學(xué)院(系)計(jì)軟院專 業(yè)軟嵌NIIT實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)名稱 實(shí)驗(yàn)二 二叉樹的基本操作及哈夫曼編碼譯碼系統(tǒng)的實(shí)現(xiàn)指導(dǎo)教師駱健實(shí)驗(yàn)類型 設(shè)計(jì)實(shí)驗(yàn)學(xué)時(shí) 2實(shí)驗(yàn)時(shí)間一、 實(shí)驗(yàn)?zāi)康暮鸵螅?）掌握二叉鏈表上實(shí)現(xiàn)二叉樹基本去處的方法。（2）學(xué)會(huì)設(shè)計(jì)基于遍歷的求解二叉樹應(yīng)用問(wèn)題的遞歸算法。（3）理解哈夫曼樹的構(gòu)造算法，學(xué)習(xí)設(shè)計(jì)哈夫曼編碼和譯碼系統(tǒng)。二、實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備) 硬件

2、: 微型計(jì)算機(jī) 軟件: Microsoft Visual C+6.0三、實(shí)驗(yàn)原理及內(nèi)容 實(shí)驗(yàn)題一：在二叉鏈表上實(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ù)，測(cè)試上述每個(gè)運(yùn)算。內(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)操作。實(shí)

3、 驗(yàn) 報(bào) 告（一）概要設(shè)計(jì)1.流程圖及設(shè)計(jì)思想用maketree構(gòu)造一棵二叉樹創(chuàng)建二叉樹刪除二叉樹先刪除左子樹再刪除右子樹，最后刪除根節(jié)點(diǎn)，再釋放結(jié)點(diǎn)空間左右子樹高度之和進(jìn)行比較，誰(shuí)大誰(shuí)就是樹的高度樹的高度本質(zhì)就是交換每個(gè)結(jié)點(diǎn)的左右子樹左右交換用隊(duì)列實(shí)現(xiàn)，將跟結(jié)點(diǎn)入隊(duì)。一：出隊(duì)并輸出節(jié)點(diǎn)的值。二： 若存在左右孩子，則將其入隊(duì)。循環(huán)以上兩個(gè)步驟，直到隊(duì)列為空。運(yùn)用后序遍歷思想，把樹分解為左右子樹和跟結(jié)點(diǎn)節(jié)點(diǎn)數(shù)量層次遍歷二叉樹根據(jù)二叉樹的定義和遍歷算法的定義，和很容易實(shí)現(xiàn)遞歸遍歷二叉樹實(shí) 驗(yàn) 報(bào) 告代碼：#include<iostream>using namespace std;tem

4、plate<class T>struct BTNodeBTNode() 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;rChild = r;T element;BTNode<T> *lChild, *rChild;template<class T>class BinaryTree

5、public :BinaryTree() root = NULL; BinaryTree();bool IsEmpty()const;void Clear();bool Root(T& x)const;void MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right);void MakeTree(BTNode<T>* r);void BreakTree(T& x, BinaryTree<T>& left, BinaryTree&l

6、t;T>& right);void DeleteTree();void PreOrder(void(*Visit)(T& x);int GetTreeHeight()const;int GetLeavesNumber()const;BTNode<T>* CopyTree()const;void ExchangeChildTree();protected:BTNode<T>* root;private:void Clear(BTNode<T>* &t);void PreOrder(void(*Visit)(T& x),BT

7、Node<T>* t);void DeleteTree(BTNode<T> *t);int GetTreeHeight(BTNode<T> *t)const;int GetLeavesNumber(BTNode<T> *t)const;BTNode<T>* CopyTree(const BTNode<T> *t)const;void ExchangeChildTree(BTNode<T> *t);template<class T>bool BinaryTree<T>:Root(T&

8、; x)constif (root)x = root->element; return true;elsereturn false;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.root);le

9、ft.root =NULL;right.root = NULL;template<class T>void BinaryTree<T>:MakeTree(BTNode<T>* r)root = r;template<class T>void BinaryTree<T>:BreakTree( T& x, BinaryTree<T>& left, BinaryTree<T>& right)if (!root | &left = &right | left.root | rig

10、ht.root)return;x = root->element;left.root = root->lChild;right.root = root->rChild;delete root;root = NULL;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),BT

11、Node<T>* t)if (t)Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);template<class T>void BinaryTree<T>:DeleteTree()DeleteTree(root);template<class T>void BinaryTree<T>:DeleteTree(BTNode<T> *t)if (t)DeleteTree(t->lChild);DeleteTree(t

12、->rChild);delete t;template<class T>int BinaryTree<T>:GetTreeHeight()constreturn GetTreeHeight(root);template<class T>int BinaryTree<T>:GetTreeHeight(BTNode<T> *t)constif (t)return (GetTreeHeight(t->lChild) > GetTreeHeight(t->rChild) ? GetTreeHeight(t->lC

13、hild) : GetTreeHeight(t->rChild) + 1;elsereturn 0;template<class T>int BinaryTree<T>:GetLeavesNumber()constreturn GetLeavesNumber(root);template<class T>int BinaryTree<T>:GetLeavesNumber(BTNode<T> *t)constif (!t->lChild&&!t->rChild)return 1;elsereturn G

14、etLeavesNumber(t->lChild) + GetLeavesNumber(t->rChild);template<class T>BTNode<T>* BinaryTree<T>:CopyTree()constreturn CopyTree(root);template<class T>BTNode<T>* BinaryTree<T>:CopyTree(const BTNode<T> *t)constif (t)BTNode<T> *p = new BTNode<T&

15、gt;(t->element);p->lChild = CopyTree(t->lChild);p->rChild = CopyTree(t->rChild);return p;return NULL;template<class T>void BinaryTree<T>:ExchangeChildTree()ExchangeChildTree(root);template<class T>void BinaryTree<T>:ExchangeChildTree(BTNode<T> *t)if (!t-&

16、gt;lChild&&!t->rChild)return;ExchangeChildTree(t->lChild);ExchangeChildTree(t->rChild);BTNode<T> *tmp;tmp = t->lChild;t->lChild = t->rChild;t->rChild = tmp;template<class T>void Visit(T& x)cout << x << " "void main()BinaryTree<cha

17、r> a, b, x, y, z;char e;y.MakeTree('E', a, b);z.MakeTree('F', a, b);x.MakeTree('C', y, z);y.MakeTree('D', a, b);z.MakeTree('B', y, x);z.PreOrder(Visit);cout << "n葉子結(jié)點(diǎn)數(shù)：" << z.GetLeavesNumber();cout << "n樹的高度：" <<

18、z.GetTreeHeight();BTNode<char>* r = z.CopyTree();BinaryTree<char> m;m.MakeTree(r);cout << endl;m.PreOrder(Visit);z.ExchangeChildTree();cout << endl;z.PreOrder(Visit);char n = getchar();實(shí)驗(yàn)題二：哈夫曼編碼和譯碼系統(tǒng)（1）所設(shè)計(jì)的系統(tǒng)重復(fù)顯示以下菜單項(xiàng)：B建樹：讀入字符集和各字符頻度，建立哈夫曼樹。T遍歷：先序和中序遍歷二叉樹。E生成編碼：根據(jù)已建成的哈夫曼樹，產(chǎn)生

19、各字符的哈夫曼編碼。C編碼：輸入由字符集中字符組成的任意字符串，利用已生成的哈夫曼編碼進(jìn)行編碼，顯示編碼結(jié)果，并將輸入的字符串及其編碼結(jié)果分別保存在磁盤文件textfile.txt和codefile.txt中。D譯碼：讀入codefile.txt，利用已建成的哈夫曼樹進(jìn)行譯碼，并將譯碼結(jié)果存入磁盤文件result.txt中。P打?。浩聊伙@示文件textfile.txt、codefile.txt和result.txt。X退出。源代碼：#include <iostream>#include <fstream>#include <string>#include &

20、lt;cstring>using namespace std;template<class T>class PrioQueue /優(yōu)先權(quán)隊(duì)列類public: PrioQueue(int mSize = 20);PrioQueue() deleteq; bool IsEmpty() const return n = 0; bool IsFull() const return n = maxSize; void Append(const T&x);void Serve(T&x); private:void AdjustDown(int r, int j);void

21、 AdjustUp(int j);T *q;int n, maxSize;template<class T>PrioQueue<T>:PrioQueue(int mSize)maxSize = mSize;n = 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

22、) / 2;qi = temp;template<class T>void PrioQueue<T>:Append(const T&x) /插入新元素if (IsFull()cout << "Overflow" << endl;return;qn+ = x;AdjustUp(n - 1);template<class T>void PrioQueue<T>:Serve(T&x) /刪除堆頂元素if (IsEmpty()cout << "Underflow"

23、 << endl;return; x = q0;q0 = q-n;AdjustDown(0, n - 1);template<class T>void PrioQueue<T>:AdjustDown(int r, int j) /向上調(diào)整int child = 2 * r + 1;T temp = qr;while (child <= j)if (child < j) && (qchild > qchild + 1)child+;if (temp <= qchild)break;q(child - 1) / 2 = q

24、child;child = 2 * child + 1;q(child - 1) / 2 = temp;template<class T>struct BTNode /結(jié)點(diǎn)類BTNode()lChild = rChild = NULL;BTNode(const T&x, const char &y)element = x;ch = y;lChild = rChild = parent = NULL;memset(z, -1, sizeof(z);BTNode(const T&x, const char &y, BTNode<T>*l, B

25、TNode<T>*r)element = x;ch = y;lChild = l;rChild = r;parent = NULL;memset(z, -1, sizeof(z);T element;BTNode<T> *lChild, *rChild, *parent;char ch;int val;int z100;template<class T> /二叉樹類class BinaryTreepublic: BinaryTree()root = NULL; i = -1; BinaryTree() void MakeTree(const T&x,

26、 const char &y, BinaryTree<T>&left, BinaryTree<T>& right); void PreOrder(void(*Visit)(T&x); void InOrder(void(*Visit)(T&x); void Create_code(); void Create_code_out(); void Code(); void Compile(); void Print(); BTNode<T>*root;private:int i;void PreOrder(void(*Vi

27、sit)(T&x), BTNode<T>*t);void InOrder(void(*Visit)(T&x), BTNode<T>*t);void Create_code(BTNode<T>*t);void Create_code_out(BTNode<T>*t);void Code(BTNode<T>*t);void Make(BTNode<T>*t, char a);void Compile(BTNode<T>*t)ifstream inf("codefile.txt")

28、;if (!inf)cout << "Cannot open the filen"return;ofstream outs("result.txt", ios:trunc);if (!outs)cout << "Cannot open the filen"return;outs.close();char *re;char tmp;int n = 0;while (inf.get(tmp)n+; /確定字符數(shù)量inf.close();re = new charn + 1;int n2 = 0;ifstream i

29、n("codefile.txt");if (!in)cout << "Cannot open the filen"return;while (in.get(tmp)ren2 = tmp; /將字符讀入一位數(shù)組n2+;BTNode<T> *c = NULL;cout << "譯碼為 :"int n3 = 0;while (n3 < n)while (t)c = t;if (ren3 = '0') /左0右1根據(jù)0或1向左走向右走直到葉子結(jié)點(diǎn)t = t->lChild;els

30、et = t->rChild;n3+;ofstream outs("result.txt", ios:app);if (!outs)cout << "Cannot open the filen"return;cout << c->ch; /輸出字符outs << c->ch; /將結(jié)果寫進(jìn)文件outs.close();t = root;n3-;cout << endl;template<class T>void BinaryTree<T>:MakeTree(cons

31、t T&x, const char &y, BinaryTree<T>&left, BinaryTree<T>& right) /建樹if (root | &left = &right)return;root = new BTNode<T>(x, y, left.root, right.root);if (left.root != right.root)left.root->parent = root;right.root->parent = root;left.root->val = 0;r

32、ight.root->val = 1;left.root = right.root = NULL;template<class T> /Visit函數(shù)void Visit(T&x)cout << x << " "template<class T>void BinaryTree<T>:PreOrder(void(*Visit)(T&x) /先序遍歷cout << "先序遍歷為: "PreOrder(Visit, root);cout << endl;t

33、emplate<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->rChild);template<class T>void BinaryTree<T>:InOrder(void(*Visit)(T&x) cout << "中序遍歷為: "InOrd

34、er(Visit, root);cout << endl;template<class T>void BinaryTree<T>:InOrder(void(*Visit)(T&x), BTNode<T>*t)if (t)InOrder(Visit, t->lChild);Visit(t->element);InOrder(Visit, t->rChild);template<class T>class HfmTree : public BinaryTree<T> public:operator T

35、() const return weight; T getW() return weight; void putW(const T&x) weight = x; void SetNull() root = NULL; private:T weight;template<class T>HfmTree<T> CreateHfmTree(T w, char q, int n) PrioQueue<HfmTree<T> > pq(n);HfmTree<T> x, y, z, zero;for (int i = 0; i < n

36、; i+)z.MakeTree(wi, qi, x, y);z.putW(wi);pq.Append(z);z.SetNull();for (int i = 1; i < n; i+)pq.Serve(x);pq.Serve(y);z.MakeTree(x.getW() + y.getW(), 'e', x, y);z.putW(x.getW() + y.getW();pq.Append(z);z.SetNull();pq.Serve(z);return z;void menu()cout << "-歡迎使用哈夫曼編碼和譯碼系統(tǒng)-" <

37、;< endl;cout << "* 請(qǐng)選擇下列序號(hào)進(jìn)行運(yùn)算: *" << endl;cout << "* B-建樹 *" << endl;cout << "* T-遍歷 *" << endl;cout << "* E-生成編碼 *" << endl;cout << "* C-編碼 *" << endl;cout << "* D-譯碼 *"

38、 << endl;cout << "* P-打印 *" << endl;cout << "* X-退出 *" << endl << endl;cout << "- 輸入操作項(xiàng)-" << endl;HfmTree<int> Ht;int num;void Make_Ht()char str100;int weight100;cout << "請(qǐng)輸入字符個(gè)數(shù) :"cin >> num; c

39、out << "請(qǐng)輸入權(quán)值 :"for (int i = 0; i < num; i+)cin >> weighti;cout << "請(qǐng)輸入相應(yīng)字符集 :"cin >> str;Ht = CreateHfmTree(weight, str, num);void Traversal_Ht()Ht.PreOrder(Visit);Ht.InOrder(Visit);template<class T>void BinaryTree<T>:Create_code()Create_co

40、de(root);template<class T>void BinaryTree<T>:Create_code(BTNode<T>*t)if (t)if (t->parent)for (int j = 0; j <= i; j+)t->zj = t->parent->zj; i+;t->zi = t->val; Create_code(t->lChild); Create_code(t->rChild); i-;template<class T>void BinaryTree<T>

41、;:Create_code_out() Create_code_out(root);template<class T>void BinaryTree<T>:Create_code_out(BTNode<T>*t)if (t) if (t->lChild = t->rChild) cout << t->ch << ":" int i = 0; while (t->zi != -1) cout << t->zi; i+;cout << endl;Create_cod

42、e_out(t->lChild);Create_code_out(t->rChild);template<class T>void BinaryTree<T>:Code()Code(root);template<class T>void BinaryTree<T>:Code(BTNode<T>*t) ofstream outf("textfile.txt");if (!outf)cout << "Cannot open the filen"return;ofstream

43、outs("codefile.txt", ios:trunc);if (!outs)cout << "Cannot open the filen"return;outs.close();char str2100;cout << "請(qǐng)輸入由字符集中字符組成的任意字符串: "cin >> str2;outf << str2; outf.close();int l = strlen(str2);cout << "編碼為 :" << endl;for

44、(int i = 0; i < l; i+)Make(root, str2i);cout << endl;template<class T>void BinaryTree<T>:Make(BTNode<T> *t, char a)int i = 0;if (t)if (t->ch = a) ofstream outs("codefile.txt", ios:app); while (t->zi != -1) cout << t->zi; outs << t->zi; i+;outs.close();return;Make(t->lChild, a);Make(t->rChild, a);templat