南邮数据结构实验一

1、实 验 报 告（2014 / 2015 学年 第 一 学期）课程名称数据结构实验名称二叉树基本操作以及哈夫曼编码译码系统实验时间 年月日指导单位指导教师学生姓名班级学号学院(系)专 业二叉树的基本运算：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,BinaryTree<T>& left,BinaryTree<

3、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>* Copy(BTNode<T>* t)-void Clear(BTNode&

4、lt;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(const T& x,BinaryTree<T>&

5、left,BinaryTree<T>& right)和计算叶子节点的int Size();3. 算法分析删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树等都是用递归的方法实现。4、 程序代码建立二叉树树 遍历二叉树叶子节点数量树的高度 左右交换复制二叉树删除二叉树 流程图 #include<iostream.h>template<class T>struct BTNodeBTNode()lChild=rChild=NULL;BTNode(const T &x)element=x;lChild=rChild=NULL

6、;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 BinaryTreepublic:BinaryTree()root=NULL;BinaryTree()Clear();void Copy(BinaryTree<T> &r) const;bool IsEmpty()constreturn root = NUL

7、L;void Clear();void Exchange();bool Root(T& x)const;int GetHeight();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 LevelOrd

8、er(void (*Visit)(T& x);int Size();BinaryTree<T>(BinaryTree<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&

9、lt;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);/void InOrder(void (*Visit)(T &x),BTNode<T>* t);/ void Po

10、stOrder(void (*Visit)(T &x),BTNode<T>* t);template <class 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(

11、BTNode<T>* &t)if(t)Clear(t->lChild);Clear(t->rChild);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.r

12、oot);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.root|right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;delete roo

13、t;root=NULL;template <class T>BTNode<T>* BinaryTree<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&l

14、t;<" "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(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rC

15、hild);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->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild)

16、;template <class T>int BinaryTree<T>:GetHeight()return GetHeight(root);template <class T>int BinaryTree<T>:GetHeight(BTNode<T>* t)int templ;int tempr;if(!t)return 0;templ=GetHeight(t->lChild);tempr=GetHeight(t->rChild);if(templ+>tempr+)return templ;elsereturn t

17、empr;template <class T>int BinaryTree<T>:number=0;template <class T>int BinaryTree<T>:Size()Size(root);return number;template <class T>int BinaryTree<T>:Size(BTNode<T>* t)if(t!=NULL)Size(t->lChild);if(t->lChild =NULL&&t->rChild =NULL)number+

18、;Size(t->rChild);return number;template <class T>void BinaryTree<T>:LevelOrder(void (*Visit)(T& x)PreOrder(Visit,root);template <class T>void BinaryTree<T>:LevelOrder(void (*Visit)(T& x),BTNode<T>* t)BTNode *quene50,*p;int pre=1,rear=1;quene+pre=t;while(pre!=

19、0)p=quene+rear;cout<<p->element<<" "if(p->lChild !=NULL)quene+pre=p->rChild ;if(p->rChild !=NULL)quene+pre=p->lChild ;void main()BinaryTree <char> a,b,x,y,z;y.MakeTree('E',a,b);z.MakeTree('F',a,b);x.MakeTree('C',y,z);y.MakeTree('

20、D',a,b);z.MakeTree('B',y,x);cout<<"二叉树z的先序遍历:"<<endl;z.PreOrder(Visit);cout<<endl;cout<<"层次遍历二叉树:"z.LevelOrder(Visit);cout<<endl;BinaryTree<char> q(z);cout<<"复制的二叉树q的先序遍历:"<<endl;q.PreOrder(Visit);cout<<e

21、ndl;cout<<"树的高度:"cout<<z.GetHeight()<<endl;cout<<"叶子节点数量:"cout<<z.Size()<<endl;z.Exchange();cout<<"二叉树左右子树交换后的先序遍历:"<<endl;z.PreOrder(Visit);cout<<endl;五、测试用例和运行结果测试用例如main函数中所示，结果如下图所示。哈夫曼编码和译码系统：一、问题描述1.所设计的系统重复显示以

22、下菜单B-建树：读入字符集和各字符频度T-遍历：先序和中序遍历二叉树E-生成代码：根据已经简称的哈夫曼数生成代码，产生各字符的哈夫曼树C-编码：输入由字符集中字符组成的任意字符串，利用已经生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中D-译码：读入codefile.txt，利用已经建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txtP-打印：屏幕显示文件textfile.txt 、codefile.txt、 resultfile.txtX-退出二、系统分析和概要设计主要包括实现主菜单以及

23、菜单里每个函数的功能（创建函数实现接收字符，接收权值，构建哈夫曼树并保存文件，编码函数实现对用户输入的秘文进行哈夫曼编码，即对每个字符翻译出其密文代码并保存文件，译码函数实现译码即输出密文的源码）。三、详细设计T1. 类和类的层次结构BinaryTree#BTNode<T> * root-static int number+BinaryTree()+BinaryTree()+bool IsEmpty()const+void Clear()+bool Root(T& x)const;+voidMakeTree(const T& x,BinaryTree<T>

24、;& left,BinaryTree<T>& right)+void BreakTree(T&x,BinaryTree<T>& left,BinaryTree<T>& right)+void PreOrder()+void inOrder() +void leaf()+void visit(T& x) +-void postOrder() -void Clear(BTNode<T>* &t)-void PreOrder(,BTNode<T>* t)-void prePrint(B

25、TNode<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() const+bool IsFull() const+void Append(const T &x)+void Serve(T& x)-void AdjustDown (int r, int j)-void AdjustUp (int j)T THf

26、mTree-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& c)2. 核心算法TT实现优先权队列的Append(x)以及Serve(x)函T数以及AdjustUp() 、AdjustDown()函数3. 算法分析时间复杂度均为O(n)四、程序代码#include <iostream>#include

27、 <string>using namespace std;int *weightArray;string s;string *codeArray;template <class T>struct BTNode BTNode() 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; rC

28、hild = r; T element; BTNode<T> *lChild, *rChild;template<class T>class BinaryTree public:BinaryTree()root = NULL;BinaryTree() Clear();bool isEmpty() const return root = NULL;void Clear()Clear(root);bool Root(T& x) const;void makeTree(const& x, BinaryTree<T>& left, Binar

29、yTree<T>& right);void breakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right);void preOrder() preOrder(root);void inOrder() inOrder(root);void postOrder() postOrder(root);void leaf()prePrint(root);void visit(T& x) cout << x << " "protect

30、ed:BTNode<T>* root;private:void Clear(BTNode<T>* t);void prePrint(BTNode<T>* t);void preOrder(BTNode<T>* t);void inOrder(BTNode<T>* t);void postOrder(BTNode<T>* t);template <class T> bool BinaryTree<T>:Root(T& x) constif (root) x = root -> eleme

31、nt;return true;elsereturn false;template <class T> void BinaryTree<T>:makeTree(const& 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

32、 <class T> void BinaryTree<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

33、;template <class T>void BinaryTree<T>:preOrder(BTNode<T>* t) if (t)visit(t -> element);preOrder(t -> lChild);preOrder(t -> rChild);template <class T>void BinaryTree<T>:inOrder(BTNode<T>* t)if (t)inOrder(t -> lChild);visit(t -> element);inOrder(t -&g

34、t; rChild);template <class T>void BinaryTree<T>:postOrder(BTNode<T>* t) if (t) postOrder(t -> lChild);postOrder(t -> rChild);visit(t -> element);template <class T>void BinaryTree<T>:Clear(BTNode<T>* t) if(t)Clear(t->lChild);Clear(t->rChild);delete t

35、;t=NULL;template <class T>void BinaryTree<T>:prePrint(BTNode<T>* t)if (t) if (t -> lChild = NULL) && (t -> rChild = NULL) visit(t -> element);return;prePrint(t -> lChild);prePrint(t -> rChild);template<class T>class PrioQueue public:PrioQueue(int mSize=

36、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 <class T>PrioQueue<T>:PrioQueue(int mSize) maxSize=mSize; n

37、=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; qi=temp;template <class T>void PrioQueue<T>:Append(const T &x)if(IsFull() cout<< "Overflow"return;qn+

38、=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);template <class T>void PrioQueue<T>:AdjustDown (int r, int j) int child = 2 * r + 1;T temp = qr;while (child <= j) if (c

39、hild < j) && (qchild > qchild + 1) child+;if (temp <= qchild) break;q(child - 1) / 2 = qchild;child = 2 * child + 1;q(child - 1) / 2 = temp;template <class T>class HfmTree: public BinaryTree<T>public:operator T()const return weight;T getW()return weight;void putW(const T

40、& 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);template <class T>void HfmTree<T>:decode(string decodeString)if (codeArray = NULL) cout << "尚未编码！" <&l

41、t; endl;return;BTNode<T>* searchNode = root;for (int i = 0; i < decodeString.length(); i+) if (decodeStringi != '0' && decodeStringi != '1') cout << "码格式不正确！" << endl;return;if (searchNode -> lChild = NULL && searchNode -> rChild =

42、 NULL)T value = searchNode -> element;for (int j = 0; j < s.length(); j+)if (value = weightArrayj) cout << sj;break;searchNode = root;if (decodeStringi = '0') searchNode = searchNode -> lChild;if (decodeStringi = '1') searchNode = searchNode -> rChild;if (searchNode

43、 -> 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 <class T>void HfmTree<T>:code(BTNode<T>* t, string& c) if (t) if

44、(t -> lChild = NULL && t -> rChild = NULL) for (int i = 0; i < s.length(); i+) if (t -> element = weightArrayi) codeArrayi = c;/cout << "NO" << i << " "cout << "字符" << si << "的权重是" << weightArrayi &

45、lt;< ", 哈弗曼编码是" << codeArrayi << endl; break;if (t -> lChild != NULL) string ls;ls.assign(c);ls.append("0");code(t -> lChild, ls);if (t -> rChild != NULL) string rs;rs.assign(c);rs.append("1");code(t -> rChild, rs);template <class T>HfmT

46、ree<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.Append(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.App

47、end(z); z.SetNull(); pq.Serve(z); return z; void input(HfmTree<int>& p)cout << "请输入需要编码的字符组成的字符串: "cin >> s;weightArray = new ints.length();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 (codeArra