二叉树与哈夫曼编码.doc

实 验 报 告（ 2014/ 2015 学年 第 二 学期）课程名称数据结构实验名称实验二 二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2015年10月31日指导单位计算机软件学院指导教师骆健学生姓名陈兵班级学号B14041126学院(系)计软院专 业软嵌NIIT实 验 报 告实验名称 实验二 二叉树的基本操作及哈夫曼编码译码系统的实现指导教师骆健实验类型 设计实验学时 2实验时间一、 实验目的和要求（1）掌握二叉链表上实现二叉树基本去处的方法。（2）学会设计基于遍历的求解二叉树应用问题的递归算法。（3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。二、实验环境(实验设备) 硬件: 微型计算机 软件: Microsoft Visual C+6.0三、实验原理及内容 实验题一：在二叉链表上实现二叉树运算（1）设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。（2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。（3）设计main函数，测试上述每个运算。内容：1、建立头文件BTree.H，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件Test.cpp，编译并调试程序，直到正确运行。注意：需要用到队列的有关操作。实 验 报 告（一）概要设计1.流程图及设计思想用maketree构造一棵二叉树创建二叉树删除二叉树先删除左子树再删除右子树，最后删除根节点，再释放结点空间左右子树高度之和进行比较，谁大谁就是树的高度树的高度本质就是交换每个结点的左右子树左右交换用队列实现，将跟结点入队。一：出队并输出节点的值。二： 若存在左右孩子，则将其入队。循环以上两个步骤，直到队列为空。运用后序遍历思想，把树分解为左右子树和跟结点节点数量层次遍历二叉树根据二叉树的定义和遍历算法的定义，和很容易实现递归遍历二叉树实 验 报 告代码：#includeusing namespace std;templatestruct 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; BinaryTree();bool IsEmpty()const;void Clear();bool Root(T& x)const;void MakeTree(const T& x, BinaryTree& left, BinaryTree& right);void MakeTree(BTNode* r);void BreakTree(T& x, BinaryTree& left, BinaryTree& right);void DeleteTree();void PreOrder(void(*Visit)(T& x);int GetTreeHeight()const;int GetLeavesNumber()const;BTNode* CopyTree()const;void ExchangeChildTree();protected:BTNode* root;private:void Clear(BTNode* &t);void PreOrder(void(*Visit)(T& x),BTNode* t);void DeleteTree(BTNode *t);int GetTreeHeight(BTNode *t)const;int GetLeavesNumber(BTNode *t)const;BTNode* CopyTree(const BTNode *t)const;void ExchangeChildTree(BTNode *t);templatebool BinaryTree:Root(T& x)constif (root)x = root-element; return true;elsereturn false;templatevoid BinaryTree:MakeTree(const T& x, BinaryTree& left, BinaryTree& right)if (root | &left = &right)return;root = new BTNode(x, left.root, right.root);left.root =NULL;right.root = NULL;templatevoid BinaryTree:MakeTree(BTNode* r)root = r;templatevoid 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;templatevoid BinaryTree:PreOrder(void(*Visit)(T& x)PreOrder(Visit, root);templatevoid BinaryTree:PreOrder(void(*Visit)(T& x),BTNode* t)if (t)Visit(t-element);PreOrder(Visit,t-lChild);PreOrder(Visit,t-rChild);templatevoid BinaryTree:DeleteTree()DeleteTree(root);templatevoid BinaryTree:DeleteTree(BTNode *t)if (t)DeleteTree(t-lChild);DeleteTree(t-rChild);delete t;templateint BinaryTree:GetTreeHeight()constreturn GetTreeHeight(root);templateint BinaryTree:GetTreeHeight(BTNode *t)constif (t)return (GetTreeHeight(t-lChild) GetTreeHeight(t-rChild) ? GetTreeHeight(t-lChild) : GetTreeHeight(t-rChild) + 1;elsereturn 0;templateint BinaryTree:GetLeavesNumber()constreturn GetLeavesNumber(root);templateint BinaryTree:GetLeavesNumber(BTNode *t)constif (!t-lChild&!t-rChild)return 1;elsereturn GetLeavesNumber(t-lChild) + GetLeavesNumber(t-rChild);templateBTNode* BinaryTree:CopyTree()constreturn CopyTree(root);templateBTNode* BinaryTree:CopyTree(const BTNode *t)constif (t)BTNode *p = new BTNode(t-element);p-lChild = CopyTree(t-lChild);p-rChild = CopyTree(t-rChild);return p;return NULL;templatevoid BinaryTree:ExchangeChildTree()ExchangeChildTree(root);templatevoid BinaryTree:ExchangeChildTree(BTNode *t)if (!t-lChild&!t-rChild)return;ExchangeChildTree(t-lChild);ExchangeChildTree(t-rChild);BTNode *tmp;tmp = t-lChild;t-lChild = t-rChild;t-rChild = tmp;templatevoid Visit(T& x)cout x ;void main()BinaryTree 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树的高度： z.GetTreeHeight();BTNode* r = z.CopyTree();BinaryTree m;m.MakeTree(r);cout endl;m.PreOrder(Visit);z.ExchangeChildTree();cout endl;z.PreOrder(Visit);char n = getchar();实验题二：哈夫曼编码和译码系统（1）所设计的系统重复显示以下菜单项：B建树：读入字符集和各字符频度，建立哈夫曼树。T遍历：先序和中序遍历二叉树。E生成编码：根据已建成的哈夫曼树，产生各字符的哈夫曼编码。C编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。D译码：读入codefile.txt，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt中。P打印：屏幕显示文件textfile.txt、codefile.txt和result.txt。X退出。源代码：#include #include #include #include using namespace std;templateclass 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 AdjustUp(int j);T *q;int n, maxSize;templatePrioQueue:PrioQueue(int mSize)maxSize = mSize;n = 0;q = new TmaxSize;templatevoid PrioQueue: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;templatevoid PrioQueue:Append(const T&x) /插入新元素if (IsFull()cout Overflow endl;return;qn+ = x;AdjustUp(n - 1);templatevoid PrioQueue:Serve(T&x) /删除堆顶元素if (IsEmpty()cout Underflow endl;return; x = q0;q0 = q-n;AdjustDown(0, n - 1);templatevoid 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;templatestruct 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*l, BTNode*r)element = x;ch = y;lChild = l;rChild = r;parent = NULL;memset(z, -1, sizeof(z);T element;BTNode *lChild, *rChild, *parent;char ch;int val;int z100;template /二叉树类class BinaryTreepublic: BinaryTree()root = NULL; i = -1; BinaryTree() void MakeTree(const T&x, const char &y, BinaryTree&left, BinaryTree& 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*root;private:int i;void PreOrder(void(*Visit)(T&x), BTNode*t);void InOrder(void(*Visit)(T&x), BTNode*t);void Create_code(BTNode*t);void Create_code_out(BTNode*t);void Code(BTNode*t);void Make(BTNode*t, char a);void Compile(BTNode*t)ifstream inf(codefile.txt);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 in(codefile.txt);if (!in)cout Cannot open the filen;return;while (in.get(tmp)ren2 = tmp; /将字符读入一位数组n2+;BTNode *c = NULL;cout 译码为 :;int n3 = 0;while (n3 lChild;elset = t-rChild;n3+;ofstream outs(result.txt, ios:app);if (!outs)cout Cannot open the filen;return;cout ch; /输出字符outs ch; /将结果写进文件outs.close();t = root;n3-;cout endl;templatevoid BinaryTree:MakeTree(const T&x, const char &y, BinaryTree&left, BinaryTree& right) /建树if (root | &left = &right)return;root = new BTNode(x, y, left.root, right.root);if (left.root != right.root)left.root-parent = root;right.root-parent = root;left.root-val = 0;right.root-val = 1;left.root = right.root = NULL;template /Visit函数void Visit(T&x)cout x ;templatevoid BinaryTree:PreOrder(void(*Visit)(T&x) /先序遍历cout 先序遍历为: ;PreOrder(Visit, root);cout endl;templatevoid BinaryTree:PreOrder(void(*Visit)(T&x), BTNode*t)if (t)Visit(t-element);PreOrder(Visit, t-lChild);PreOrder(Visit, t-rChild);templatevoid BinaryTree:InOrder(void(*Visit)(T&x) cout 中序遍历为: ;InOrder(Visit, root);cout endl;templatevoid BinaryTree:InOrder(void(*Visit)(T&x), BTNode*t)if (t)InOrder(Visit, t-lChild);Visit(t-element);InOrder(Visit, t-rChild);templateclass HfmTree : public BinaryTree public:operator T() const return weight; T getW() return weight; void putW(const T&x) weight = x; void SetNull() root = NULL; private:T weight;templateHfmTree CreateHfmTree(T w, char q, int n) PrioQueueHfmTree pq(n);HfmTree x, y, z, zero;for (int i = 0; i n; 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 -欢迎使用哈夫曼编码和译码系统- endl;cout * 请选择下列序号进行运算: * endl;cout * B-建树 * endl;cout * T-遍历 * endl;cout * E-生成编码 * endl;cout * C-编码 * endl;cout * D-译码 * endl;cout * P-打印 * endl;cout * X-退出 * endl endl;cout - 输入操作项- endl;HfmTree Ht;int num;void Make_Ht()char str100;int weight100;cout num; cout 请输入权值 :;for (int i = 0; i weighti;cout str;Ht = CreateHfmTree(weight, str, num);void Traversal_Ht()Ht.PreOrder(Visit);Ht.InOrder(Visit);templatevoid BinaryTree:Create_code()Create_code(root);templatevoid BinaryTree:Create_code(BTNode*t)if (t)if (t-parent)for (int j = 0; j zj = t-parent-zj; i+;t-zi = t-val; Create_code(t-lChild); Create_code(t-rChild); i-;templatevoid BinaryTree:Create_code_out() Create_code_out(root);templatevoid BinaryTree:Create_code_out(BTNode*t)if (t) if (t-lChild = t-rChild) cout ch zi != -1) cout zi; i+;cout lChild);Create_code_out(t-rChild);templatevoid BinaryTree:Code()Code(root);templatevoid BinaryTree:Code(BTNode*t) ofstream outf(textfile.txt);if (!outf)cout Cannot open the filen;return;ofstream outs(codefile.txt, ios:trunc);if (!outs)cout Cannot open the filen;return;outs.close();char str2100;cout str2;outf str2; outf.close();int l = strlen(str2);cout 编码为 : endl;for (int i = 0; i l; i+)Make(root, str2i);cout endl;templatevoid BinaryTree:Make(BTNode *t, char a)int i = 0;if (t)if (t-ch = a) ofstream out