实验报告2_二叉树及哈夫曼编码.doc

实 验 报 告（ 2013/ 2014 学年 第 二 学期）课程名称数据结构A 实验名称实验二 二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2014年4月8日指导单位计算机学院计算机软件教学中心指导教师朱立华学生姓名高怡馨班级学号B12140113学院(系)教育科学与技术学院专 业教育技术学实 验 报 告实验名称 实验二 二叉树的基本操作及哈夫曼编码译码系统的实现指导教师朱立华实验类型 设计实验学时 2实验时间2014.4.8一、 实验目的和要求（1）掌握二叉链表上实现二叉树基本去处的方法。（2）学会设计基于遍历的求解二叉树应用问题的递归算法。（3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。二、实验环境(实验设备) 硬件: 微型计算机 软件: Microsoft Visual C+6.0三、实验原理及内容 实验题一：在二叉链表上实现二叉树运算（1）设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。（2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。（3）设计main函数，测试上述每个运算。内容：1、建立头文件BTree.H，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件Test.cpp，编译并调试程序，直到正确运行。注意：需要用到队列的有关操作。实 验 报 告说明：二叉树的基本操作可包括：(1)void Clear(BTreeNode *BT) /清除一棵二叉树，并释放结点空间（2）void MakeTree(BTreeNode *BT) /构造一棵二叉树BT（3）void BreakTree(BTreeNode *BT) /撤销一棵二叉树BT（4）void PreOrder (BTreeNode *BT) /先序遍历二叉树BT(5）void InOrder(BTreeNode *BT) /中序遍历二叉树BT（6）void PostOrder(BTreeNode *BT) /后序遍历二叉树BT (7) void FloorOrder(BTreeNode *BT) /层次遍历二叉树BT （8）int Size(BTreeNode *BT) /求二叉树BT的结点数量（9）void Exchange(BTreeNode *BT) /把二叉树BT的左右子树进行交换（10）int GetHeight(BTreeNode *BT) /求二叉树BT的高度（一）概要设计1.流程图及设计思想用maketree构造一棵二叉树建立二叉树树删除二叉树先删除左子树，再删除右子树，最后删除根节点，再释放结点空间左右子树高度之和进行比较，谁大谁就是树的高度树的高度本质就是交换每个结点的左右子树左右交换用队列实现，将跟结点入队。一：出队并输出节点的值。二： 若存在左右孩子，则将其入队。循环以上两个步骤，直到队列为空。运用后序遍历思想，把树分解为左右子树和跟结点节点数量层次遍历二叉树根据二叉树的定义和遍历算法的定义，和很容易实现递归遍历二叉树实 验 报 告2.本程序包含的模块（1）主程序模块 Void main（） 初始化； 构造一棵二叉树； 各种遍历二叉树； 对二叉树进行各种常见运算； 删除二叉树； (2) 二叉树模块实现二叉树的抽象数据类型和基本操作(3) 队列模块实现队列的抽象数据类（4）二叉树运算模块求二叉树的结点，叶子数目（二）详细设计一先序遍历：A自然语言描述:1.判断根节点会否为空，如果为空，返回2.如果根节点不为空3.先输出根节点，再递归调用自身依次输出左孩子和右孩子B代码详细分析template void 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);实 验 报 告二中序遍历：A自然语言描述:1.判断根节点是否为空，如果为空，返回2.如果根节点不为空3. 递归调用自身输出左孩子，再输出根结点，递归调用输出右孩子B代码详细分析：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);三后序遍历：A自然语言描述：1.判断根节点是否为空，如果为空，返回2.如果根节点不为空3. 递归调用自身输出左孩子和右孩子，再输出根结点B代码详细分析：template void BinaryTree: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);四层次遍历二叉树：A自然语言描述：1定义头指针和尾指针和空指针p2.根节点是否为空，如果是，结束3.如果不是，根节点入队4. 取队首元素，输出队首元素5.将队首的非空左右结点入队列，删除队首元素6.循环下去，直到队列为空B代码详细分析：template void BinaryTree:FloorOrder(void (*Visit)(T &x) FloorOrder(Visit,root);template void 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); 五求二叉树的结点数：A. 自然语言描述：1：判断根节点是否为空，如果为空，返回02：如果根节点不为空 3：递归调用求二叉树的结点数的函数，参数改为根节点的左孩子 4：递归调用求二叉树的结点数的函数，参数改为根节点的右孩子实 验 报 告5：返回根节点的左右字数的结点数之和B代码详细分析:template int BinaryTree:Size()return Size(root);template int BinaryTree:Size(BTNode* t)if(!t)return 0;elsereturn Size(t-lChild)+Size(t-rChild)+1;六二叉树的左右交换:A自然语言描述：1.判断根节点是否为空，如果为空，返回2.如果不为空，再判断该节点左右孩子是否同时为空，3.如果是，返回4.如果不为空，交换左右孩子5.返回循环，遍历左右子树B代码详细分析：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);Exchange(t-rChild);实 验 报 告七求二叉树的深度：A自然语言描述：1：判断根节点是否为空，如果根节点为空，返回0 2：如果根节点不为空但是根节点的左右孩子同时为空，返回1 3：如果以上两个条件都不成立4：递归调用求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为15：递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为0 6：返回4与5步中得出深度较大的那个数作为二叉树的深度数B 代码详细分析: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;测试结果实 验 报 告二叉树基本运算源代码：BTree.h:#include using namespace std;template struct BTNodeT element;BTNode *lChild,*rChild;BTNode()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;template class BinaryTreepublic:BinaryTree()root=NULL;BinaryTree()Clear(root);bool IsEmpty()const;void Clear();bool Root(T &x)const;int Size();void MakeTree(const T &e,BinaryTree& left,BinaryTree& right);void BreakTree(T &e,BinaryTree& left,BinaryTree& right);void LevelOrder(void (*Visit(T& x);void PreOrder(void (*Visit)(T& x);void InOrder(void (*Visit)(T& x);void PostOrder(void (*Visit)(T& x);实 验 报 告void Exchange();int GetHeight();protected:BTNode* root;private:void Clear(BTNode* t);int Size(BTNode* t);void LevelOrder(void (*Visit)(T& x),BTNode* t);void PreOrder(void (*Visit)(T& x),BTNode* t);void InOrder(void (*Visit)(T& x),BTNode* t);void PostOrder(void (*Visit)(T& x),BTNode* t);void Exchange(BTNode* t);int GetHeight(BTNode* t);template void BinaryTree:Clear(BTNode* t)if(!t)return;Clear(t-lChild);Clear(t-rChild);delete t;template bool BinaryTree:Root(T &x)constif(root)x=root-element;return true;elsereturn false;template void BinaryTree:MakeTree(const T &e,BinaryTree& left,BinaryTree& right)if(root|&left=&right)return;root=new BTNode(e,left.root,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 Visit(T& x)coutx ;template void 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);template void BinaryTree:InOrder(void (*Visit)(T& x)InOrder(Visit,root);emplatevoid BinaryTree:InOrder(void (*Visit)(T& x),BTNode* t)实 验 报 告if(t)InOrder(Visit,t-lChild);Visit(t-element);InOrder(Visit,t-rChild);template void BinaryTree: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 BinaryTree:FloorOrder(void(*Visit)(T& x),BTNode*t) SeqQueueBTNode*se(100); se.EnQueue(t); BTNode *tmp; while(!se.IsEmpty() se.Front(tmp); Visit(tmp); se.DeQueue(); if(tmp-lChild)实 验 报 告 se.EnQueue(tmp-rChild); template int BinaryTree:Size()return Size(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);Exchange(t-rChild);template int BinaryTree:GetHeight()return GetHeight(root);emplate 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;Test.Cpp：#include BTree.hint main() BinaryTree a,b,x,y,z;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);cout前序遍历endl;z.PreOrder(Visit);coutendl;cout中序遍历endl;z.InOrder(Visit);coutendl;cout后序遍历endl;z.PostOrder(Visit);coutendl;cout层次遍历endl;z.LevelOrder(Visit);coutendl;cout结点数量:;coutz.Size()endl;z.Exchange();cout左右交换后的前序遍历endl;实 验 报 告z.PreOrder(Visit);cout树的高度:;coutz.GetHeight()endl;coutendl;return 0;实 验 报 告实验题二：哈夫曼编码和译码系统（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 #include using namespace std;int *weightArray;string s;string *codeArray;template struct BTNode T element;BTNode *lChild, *rChild;BTNode() 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;实 验 报 告templateclass BinaryTree public:BinaryTree() root = NULL;BinaryTree() bool isEmpty() const return root = NULL;void clear() postClear(root);bool retRoot(T& x) const;void makeTree(const& x, BinaryTree& left, BinaryTree& right);void breakTree(T& x, BinaryTree& left, BinaryTree& right);void preOrder() preOrder(root);void inOrder() inOrder(root);void postOrder() postOrder(root);BTNode* copy(BTNode *t);int size() return size(root);void change() change(root);void breathFirst() breathFirst(root);int height() return height(root);void leaf() prePrint(root);实 验 报 告protected:BTNode* root;private:void clear(BTNode* t);void change(BTNode* t);void postClear(BTNode* t);void prePrint(BTNode* t);int size(BTNode* t);int height(BTNode* t);void preOrder(BTNode* t);void inOrder(BTNode* t);void postOrder(BTNode* t);void breathFirst(BTNode* t);void visit(T& x) cout x ;template bool BinaryTree:retRoot(T& x) const if (root) x = root - element;return true;else return false;template void BinaryTree:makeTree(const& x, BinaryTree& left, BinaryTree& right) if (root | &left = &right) return;root = new BTNode(x, left.root, 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 BinaryTree: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(t - element);template void BinaryTree:clear(BTNode* t) delete t;t = NULL;template void BinaryTree:postClear(BTNode* t) if (t) postClear(t - lChild);postClear(t - rChild);delete t;实 验 报 告template BTNode* BinaryTree:copy(BTNode *t) if (!t) return NULL;BTNode* q = new BTNode(t -element);q - lChild = copy(t - lChild);q - rChild = copy(t - rChild);return q;template int BinaryTree:size(BTNode* t) if (!t) return 0;else return size(t - lChild) + size(t - rChild);template void BinaryTree:change(BTNode* t) if (!t) return;BTNode *q = copy(t - rChild);clear(t - rChild);t - rChild = t - lChild;t - lChild = q;change(t - lChild);change(t - rChild);template void BinaryTree:breathFirst(BTNode* t) if (!t) return;queueBTNode* q1;q1.push(t);BTNode *node;while (!q1.empty() node = q1.front();visit(node - element);q1.pop();if (node - lChild) q1.push(node - lChild);if (node- rChild) q1.push(node - rChild);template int BinaryTree:height(BTNode* t) 实 验 报 告 if(t = NULL) return 0; else int m = height( t - lChild ); int n = height(t - rChild); return (m n) ? (m + 1) : (n + 1); 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 public: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 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-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:operator 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 尚未编码！ endl;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 = 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 - rChild = NULL) for (int i = 0; i element =