二叉树与哈夫曼编码

1、实 验 报 告（ 2014/ 2015 学年 第 二 学期）课程名称数据结构实验名称实验二 二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2015年10月31日指导单位计算机软件学院指导教师骆健学生姓名陈兵班级学号B14041126学院(系)计软院专 业软嵌NIIT实 验 报 告实验名称 实验二 二叉树的基本操作及哈夫曼编码译码系统的实现指导教师骆健实验类型 设计实验学时 2实验时间一、 实验目的和要求（1）掌握二叉链表上实现二叉树基本去处的方法。（2）学会设计基于遍历的求解二叉树应用问题的递归算法。（3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。二、实验环境(实验设备) 硬件

2、: 微型计算机 软件: Microsoft Visual C+6.0三、实验原理及内容 实验题一：在二叉链表上实现二叉树运算（1）设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。（2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。（3）设计main函数，测试上述每个运算。内容：1、建立头文件BTree.H，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件Test.cpp，编译并调试程序，直到正确运行。注意：需要用到队列的有关操作。实

3、 验 报 告（一）概要设计1.流程图及设计思想用maketree构造一棵二叉树创建二叉树删除二叉树先删除左子树再删除右子树，最后删除根节点，再释放结点空间左右子树高度之和进行比较，谁大谁就是树的高度树的高度本质就是交换每个结点的左右子树左右交换用队列实现，将跟结点入队。一：出队并输出节点的值。二： 若存在左右孩子，则将其入队。循环以上两个步骤，直到队列为空。运用后序遍历思想，把树分解为左右子树和跟结点节点数量层次遍历二叉树根据二叉树的定义和遍历算法的定义，和很容易实现递归遍历二叉树实 验 报 告代码：#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叶子结点数：" << 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();实验题二：哈夫曼编码和译码系统（1）所设计的系统重复显示以下菜单项：B建树：读入字符集和各字符频度，建立哈夫曼树。T遍历：先序和中序遍历二叉树。E生成编码：根据已建成的哈夫曼树，产生

19、各字符的哈夫曼编码。C编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。D译码：读入codefile.txt，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件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 /优先权队列类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) /向上调整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 /结点类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+; /确定字符数量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; /将字符读入一位数组n2+;BTNode<T> *c = NULL;cout << "译码为 :"int n3 = 0;while (n3 < n)while (t)c = t;if (ren3 = '0') /左0右1根据0或1向左走向右走直到叶子结点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; /将结果写进文件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函数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 << "-欢迎使用哈夫曼编码和译码系统-" <

37、;< endl;cout << "* 请选择下列序号进行运算: *" << 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 << "- 输入操作项-" << endl;HfmTree<int> Ht;int num;void Make_Ht()char str100;int weight100;cout << "请输入字符个数 :"cin >> num; c

39、out << "请输入权值 :"for (int i = 0; i < num; i+)cin >> weighti;cout << "请输入相应字符集 :"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 << "请输入由字符集中字符组成的任意字符串: "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