二叉树基本操作以及哈夫曼编码译码系统

1、实 验 报 告（2015 / 2016 学年 第 二 学期）课程名称数据结构实验名称二叉树基本操作以及哈夫曼编码译码系统实验时间 2016年4月14日指导单位南京邮电大学指导教师骆健学生姓名吴佳瑶班级学号B14111708学院(系) 管理学院专 业信息管理与信息系统二叉树的基本运算：1、 问题描述1. 设计递归算法，实现二叉树的运算：删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树，交换一棵二叉树的左右子树2. 设计算法，自上而下，自左向右即按层次遍历一棵二叉树3. 设计main函数，测试上述每个运算二、系统分析和概要设计首先用maketree构造一棵二叉树，然后遍

2、历二叉树，然后交换每个结点的左右子树，接着算出输得高度和叶子节点，最后删除。三、详细设计T1. 类和类的层次结构BinaryTree#BTNode<T> * root-static int number+BinaryTree()+BinaryTree()+void Copy(BinaryTree<T> &r) const+bool IsEmpty()const+void Clear()+void Exchange()+bool Root(T& x)const;+int GetHeight()+voidMakeTree(const T& x,Bin

3、aryTree<T>& left,BinaryTree<T>& right)+void BreakTree(T&x,BinaryTree<T>& left,BinaryTree<T>& right)+void PreOrder(void (*Visit)(T &x)+void LevelOrder(void (*Visit)(T& x)+int Size()+BinaryTree<T>(BinaryTree<T> &t)+BTNode<T>* Co

4、py(BTNode<T>* t)-void Clear(BTNode<T>* &t)-void Exchange(BTNode<T>* t)-int GetHeight(BTNode<T>* t)-int Size(BTNode<T>* t)-void PreOrder(void (*Visit)(T &x),BTNode<T>* t)-void LevelOrder(void (*Visit)(T& x),BTNode<T>* t) 2. 核心算法建立二叉树的void MakeTree

5、(const T& x,BinaryTree<T>& left,BinaryTree<T>& right)和计算叶子节点的int Size();3. 算法分析删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树等都是用递归的方法实现。四、 程序代码建立二叉树树用maketree构造一棵二叉树递归遍历二叉树根据二叉树的定义和遍历算法的定义，和很容易实现层次遍历二叉树节点数量用队列实现，将跟结点入队。一：出队并输出节点的值。二： 若存在左右孩子，则将其入队。循环以上两个步骤，直到队列为空。运用后序遍历思想，把树分解为左右子树和

6、跟结点左右交换本质就是交换每个结点的左右子树树的高度左右子树高度之和进行比较，谁大谁就是树的高度删除二叉树先删除左子树，再删除右子树，最后删除根节点，再释放结点空间一先序遍历：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),BTNode<T>* t)if(t)Visit

7、(t->element);PreOrder(Visit,t->lChild)；PreOrder(Visit,t->rChild);二中序遍历：template <class T>void BinaryTree<T>:InOrder(void (*Visit)(T& x)InOrder(Visit,root);template<class T>void BinaryTree<T>:InOrder(void (*Visit)(T& x),BTNode<T>* t)if(t)InOrder(Visit,t-

8、>lChild);Visit(t->element);InOrder(Visit,t->rChild);三后序遍历：template <class T>void BinaryTree<T>:PostOrder(void (*Visit)(T& x)PostOrder(Visit,root);template <class T>void BinaryTree<T>:PostOrder(void (*Visit)(T& x),BTNode<T>* t)if(t)PostOrder(Visit,t->

9、lChild);PostOrder(Visit,t->rChild);Visit(t->element);四层次遍历二叉树：template <class T>void BinaryTree<T>:FloorOrder(void (*Visit)(T &x) FloorOrder(Visit,root);template <class T>void BinaryTree<T>:;FloorOrder(void(*Visit)(Visit<T>*x),BTNode<T>*t) SeqQueue<BT

10、Node<T>*>se(100); se.EnQueue(t); BTNode<T>*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); 五求二叉树的结点数：template <class T>int BinaryTree<T>:Size()return Size(

11、root);template <class T>int BinaryTree<T>:Size(BTNode<T>* t)if(!t)return 0;elsereturn Size(t->lChild)+Size(t->rChild)+1;六二叉树的左右交换:template <class T>void BinaryTree<T>:Exchange()Exchange(root);template <class T>void BinaryTree<T>:Exchange(BTNode<T>

12、;* t)if(!t)return;BTNode<T>* temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);七求二叉树的深度：template <class T>int BinaryTree<T>:GetHeight(BTNode<T>* t)int templ;int tempr;if(!t)return 0;templ=GetHeight(t->lChild);t

13、empr=GetHeight(t->rChild);if(templ+>tempr+)return templ;elsereturn tempr;五、测试用例和运行结果测试用例结果如下图所示。哈夫曼编码和译码系统：一、问题描述1.所设计的系统重复显示以下菜单B-建树：读入字符集和各字符频度T-遍历：先序和中序遍历二叉树E-生成代码：根据已经简称的哈夫曼数生成代码，产生各字符的哈夫曼树C-编码：输入由字符集中字符组成的任意字符串，利用已经生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中D-译码：

14、读入codefile.txt，利用已经建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txtP-打印：屏幕显示文件textfile.txt 、codefile.txt、 resultfile.txtX-退出二、系统分析和概要设计主要包括实现主菜单以及菜单里每个函数的功能（创建函数实现接收字符，接收权值，构建哈夫曼树并保存文件，编码函数实现对用户输入的秘文进行哈夫曼编码，即对每个字符翻译出其密文代码并保存文件，译码函数实现译码即输出密文的源码）。三、详细设计T1. 类和类的层次结构BinaryTree#BTNode<T> * root-static int number

15、+BinaryTree()+BinaryTree()+bool IsEmpty()const+void Clear()+bool Root(T& x)const;+voidMakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right)+void BreakTree(T&x,BinaryTree<T>& left,BinaryTree<T>& right)+void PreOrder()+void inOrder() +void le

16、af()+void visit(T& x) +-void postOrder() -void Clear(BTNode<T>* &t)-void PreOrder(,BTNode<T>* t)-void prePrint(BTNode<T>* t)-void inOrder(BTNode<T>* t)-void postOrder(BTNode<T>* t)PrioQueue-T* q;-int n,maxSize;+PrioQueue(int mSize=20)+PrioQueue()+bool IsEmpty()

17、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>* t, string

18、& c)2. 核心算法TT实现优先权队列的Append(x)以及Serve(x)函T数以及AdjustUp() 、AdjustDown()函数3. 算法分析时间复杂度均为O(n)四、程序代码#include <iostream>#include <string>using namespace std;int *weightArray;string s;string *codeArray;template <class T>struct BTNode BTNode() lChild = rChild = NULL; BTNode(const T&

19、; 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 public:BinaryTree()root = NULL;BinaryTree() Clear();bool isEmpty() const r

20、eturn root = NULL;void Clear()Clear(root);bool Root(T& x) const;void makeTree(const& x, BinaryTree<T>& left, BinaryTree<T>& right);void breakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right);void preOrder() preOrder(root);void inOrder() inOrder

21、(root);void postOrder() postOrder(root);void leaf()prePrint(root);void visit(T& x) cout << x << " "protected:BTNode<T>* root;private:void Clear(BTNode<T>* t);void prePrint(BTNode<T>* t);void preOrder(BTNode<T>* t);void inOrder(BTNode<T>* t);voi

22、d postOrder(BTNode<T>* t);template <class T> bool BinaryTree<T>:Root(T& x) constif (root) x = root -> element;return true;elsereturn false;template <class T> void BinaryTree<T>:makeTree(const& x, BinaryTree<T>& left, BinaryTree<T>& right)i

23、f (root | &left = &right) return;root = new BTNode<T>(x, left.root, right.root);left.root = right.root = NULL;template <class T> void BinaryTree<T>:breakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right) if (!root | &left = &right | left.r

24、oot | right.root) return;x = root -> element;left.root = root -> lChild;right.root = root -> rChild;delete root;root = NULL;template <class T>void BinaryTree<T>:preOrder(BTNode<T>* t) if (t)visit(t -> element);preOrder(t -> lChild);preOrder(t -> rChild);template &

25、lt;class T>void BinaryTree<T>:inOrder(BTNode<T>* t)if (t)inOrder(t -> lChild);visit(t -> element);inOrder(t -> rChild);template <class T>void BinaryTree<T>:postOrder(BTNode<T>* t) if (t) postOrder(t -> lChild);postOrder(t -> rChild);visit(t -> eleme

26、nt);template <class T>void BinaryTree<T>:Clear(BTNode<T>* t) if(t)Clear(t->lChild);Clear(t->rChild);delete t;t=NULL;template <class T>void BinaryTree<T>:prePrint(BTNode<T>* t)if (t) if (t -> lChild = NULL) && (t -> rChild = NULL) visit(t ->

27、element);return;prePrint(t -> lChild);prePrint(t -> rChild);template<class T>class 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

28、 r, int j);void 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)/2; q

29、i=temp;template <class T>void PrioQueue<T>:Append(const T &x)if(IsFull() cout<< "Overflow"return;qn+=x;AdjustUp(n-1);template <class T>void PrioQueue<T>:Serve(T& x)if(IsEmpty()cout<< "Underflow"return;x=q0;q0=q-n;AdjustDown (0, n-1);tem

30、plate <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 = qchild;child = 2 * child + 1;q(child - 1) / 2 = temp;template &l

31、t;class T>class HfmTree: public BinaryTree<T>public: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>* t, string& c);t

32、emplate <class T>void HfmTree<T>:decode(string decodeString)if (codeArray = NULL) cout << "尚未编码！" << endl;return;BTNode<T>* searchNode = root;for (int i = 0; i < decodeString.length(); i+) if (decodeStringi != '0' && decodeStringi != '1&

33、#39;) cout << "码格式不正确！" << endl;return;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;searchNode = root;if (decodeStringi = &#

34、39;0') searchNode = searchNode -> 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 &

35、lt;< sj;break;cout << endl;template <class T>void HfmTree<T>:code(BTNode<T>* t, string& c) if (t) if (t -> lChild = NULL && t -> rChild = NULL) for (int i = 0; i < s.length(); i+) if (t -> element = weightArrayi) codeArrayi = c;/cout << "

36、NO" << i << " "cout << "字符" << si << "的权重是" << weightArrayi << ", 哈夫曼编码是" << codeArrayi << endl; break;if (t -> lChild != NULL) string ls;ls.assign(c);ls.append("0");code(t -> lChild, l

37、s);if (t -> rChild != NULL) string rs;rs.assign(c);rs.append("1");code(t -> rChild, rs);template <class T>HfmTree<T> CreateHfmTree (T *w,int n)PrioQueue <HfmTree<T> > pq(n); HfmTree<T> x,y,z; for (int i=0;i<n;i+) z.makeTree(wi,x,y); z.putW(wi); pq.App

38、end(z); z.SetNull(); for (i=1;i<n;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; void input(HfmTree<int>& p)cout << "请输入需要编码的字符组成的字符串: "cin >> s;weightArray = new ints.lengt

39、h();codeArray = new strings.length();for (int i = 0; i < s.length(); i+) cout << "请输入第" << (i + 1) << "个字符的权值：" << endl;cin >> weightArrayi;p = CreateHfmTree(weightArray, s.length();/p.postOrder();void createCode(HfmTree<int>& p) if (cod

40、eArray = NULL) cout << "树为空！" << endl;return;string c;p.code(c);void encode()if (codeArray = NULL) cout << "尚未编码！" << endl;return;string encodeString;cout << "请输入需要编码的字符串: "cin >> encodeString;cout << "n经过编码的码值为："for (

41、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<int> p;string decodeString;while (flag) cout<<"*B建树*"<<endl;cout<<"

42、;*T遍历*"<<endl;cout<<"*E生成编码*"<<endl;cout<<"*C编码*"<<endl;cout<<"*D译码*"<<endl;cout<<"*X退出*"<<endl;cout << "请输入指令："char c;cin >> c;cout << endl;switch (c) case 'B':inpu

43、t(p);break;case 'T':if (p != NULL) cout << "前序遍历："p.preOrder();cout << endl;cout << "中序遍历："p.inOrder();cout << endl;cout << "后序遍历："p.postOrder();cout << endl;else cout << "尚未建树！" << endl;break;case 'E

44、':createCode(p);break;case 'C':encode();break;case 'D':cout << "请输入需要破译的编码："cin >> decodeString;p.decode(decodeString);break;case 'X':flag = false;break;5、 测试用例和运行结六、实验小结通过这次实验，我对一个二叉树以及哈夫曼有着更加全面深刻的认识，会采用不同的数据存储方式，如之前的栈，现在的二叉树等，可以提高了程序的运行效率。在编写这个程序的过

45、程中，对如哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，二叉树的复制及遍历等问题。在这次实验，体会到了编完程序的满足感，也从中发现自己平时学习的不足和薄弱的地方加以改进。程序代码:一、#include<iostream.h>template<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)eleme

46、nt=x;lChild=l;rChild=r;T element;BTNode<T>* lChild,* rChild;template<class T>class BinaryTreepublic:BinaryTree()root=NULL;BinaryTree()Clear();void Copy(BinaryTree<T> &r) const;bool IsEmpty()constreturn root = NULL;void Clear();void Exchange();bool Root(T& x)const;int GetHei

47、ght();void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right);void BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right);void PreOrder(void (*Visit)(T &x);void LevelOrder(void (*Visit)(T& x);int Size();BinaryTree<T>(BinaryTr

48、ee<T> &t)root=Copy(t.root);/void InOrder(void (*Visit)(T &x);/void PostOrder(void (*Visit)(T &x);BTNode<T>* Copy(BTNode<T>* t);protected:BTNode<T> * root;private:static int number;void Clear(BTNode<T>* &t);void Exchange(BTNode<T>* t);int GetHeight(

49、BTNode<T>* t);int Size(BTNode<T>* t);void PreOrder(void (*Visit)(T &x),BTNode<T>* t);void LevelOrder(void (*Visit)(T& x),BTNode<T>* t);/void InOrder(void (*Visit)(T &x),BTNode<T>* t);/ void PostOrder(void (*Visit)(T &x),BTNode<T>* t);template <c

50、lass T>bool BinaryTree<T>:Root(T &x)constif(root)x=root->element;return true;else return false;template <class T>void BinaryTree<T>:Clear()Clear(root);template <class T>void BinaryTree<T>:Clear(BTNode<T>* &t)if(t)Clear(t->lChild);Clear(t->rChil

51、d);delete t;t=NULL;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);left.root=right.root=NULL;template <class T>void Binary

52、Tree<T>:BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& 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 <class T>BTNode<T>* BinaryTree<

53、;T>:Copy(BTNode<T>* t)if(!t)return NULL;BTNode<T>*q=new BTNode<T>(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);return q;template <class T>void Visit(T &x)cout<<x<<" "template <class T>void BinaryTree<T>

54、;:PreOrder(void (*Visit)(T& x)PreOrder(Visit,root);template <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>:Exchange()Exchange(root);template <class T>void BinaryTree<T>:Exchange(BTNode<T>* t)if(!t)return; BTNode<T>* temp;temp=t->lChild;t->lChi