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

实验报告（/学年第一学期）课程名称数据结构A实验名称二叉树的基本操作及哈夫曼编码译码系统的实现实验时间年月日指导单位指导教师学生姓名班级学号学院(系)专业2实验报告实验名称二叉树的基本操作及哈夫曼编码译码系统的实现指导教师实验类型上机实验学时实验时间一、实验目的和要求实验目的：1、掌握二叉链表上实现二叉树基本运算的方法。2、学会设计基于遍历的求解二叉树应用问题的递归算法。3、理解哈夫曼树的构造算法，学会设计哈夫曼编码和译码系统。内容和要求：1、在二叉链表上实现二叉树运算○1设计递归算法，实现下列算法：删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子结点的个数，复制一棵二叉树，交换一颗二叉树的左右子树。○2设计算法，按自上到下，自左向右的次序，即按层次遍历一颗二叉树。○3设计main函数，测试上述每个运算。2、哈夫曼编码和译码系统设计的系统重复显示以下菜单项：建树、遍历、生成编码、编码、译码、打印、退出并且实现这些功能。3二、实验环境(实验设备)硬件：PC软件：Code::Blocks(C++)4三、实验原理及内容1、线性表的基本运算（1）核心算法○1删除一颗二叉树：思路：将一颗二叉树拆分成三部分，执行语句“deleteroot;root=NULL”,将原二叉树的根结点回收。代码：templateclassTvoidBinaryTreeT::BreakTree(T&x,BinaryTreeT&left,BinaryTreeT&right){if(!root||&left==&right||left.root||right.root){return;}x=root-element;left.root=root-lChild;right.root=root-rChild;deleteroot;root=NULL;}5○2求一棵二叉树的高度：思路：递归搜索二叉树，不断返回高度。代码：templateclassTintBinaryTreeT::High(){inth=High2(root);returnh;}templateclassTintBinaryTreeT::High2(BTNodeT*p){if(!p){return0;}inth1,h2;h1=High2(p-lChild);h2=High2(p-rChild);if(h1h2)6{returnh1+1;}else{returnh2+1;}}○3求一棵二叉树中叶子结点的个数：思路：递归搜索二叉树的叶子结点，不断累加。代码：templateclassTintBinaryTreeT::Leaves(){intnumber=0;Leaf(root,number);returnnumber;}templateclassTvoidBinaryTreeT::Leaf(BTNodeT*p,int&a)7{if(p){if(p-lChild==0&&p-rChild==0){a++;}Leaf(p-lChild,a);Leaf(p-rChild,a);}}○4复制一棵二叉树：思路：用q指针指向复制的二叉树的根结点，递归调用Copy()，不断复制左子树和右子树。代码：templateclassTvoidBinaryTreeT::Copy(BinaryTreeT&p){BTNodeT*q=Copy(root);p.root=q;}8templateclassTBTNodeT*BinaryTreeT::Copy(BTNodeT*t){if(!t){returnNULL;}BTNodeT*q=newBTNodeT(t-element);q-lChild=Copy(t-lChild);q-rChild=Copy(t-rChild);returnq;}○5交换一颗二叉树的左右子树：思路：递归调用Change(),不断交换左、右子树。代码：templateclassTvoidBinaryTreeT::Exchange(){Change(root);}9templateclassTvoidBinaryTreeT::Change(BTNodeT*t){if(t){BTNodeT*temp=t-lChild;t-lChild=t-rChild;t-rChild=temp;Change(t-lChild);Change(t-rChild);}}○6按自上到下，自左向右的次序的层次遍历：思路：利用队列作为辅助数据结构，队列的元素类型是指向二叉树中结点的指针类型，首先让根结点入队，接着做一个循环：每当一个元素出队，则它的左右子树依次入队。代码：templateclassTclassSeqQueue{10private:intfront,rear;intmaxSize;T*q;public:SeqQueue(intm);~SeqQueue(){delete[]q;}boolEnQueue(constTx);boolDeQueue();boolFront(T&x)const;boolIsEmpty(){returnfront==rear;};boolIsFull(){return(rear+1)%maxSize==front;};voidClear(){front=rear=0;}};templateclassTSeqQueueT::SeqQueue(intm){maxSize=m;q=newT[m];front=rear=0;}11templateclassTboolSeqQueueT::Front(T&x)const{x=q[(front+1)%maxSize];returntrue;}templateclassTboolSeqQueueT::EnQueue(constTx){if(IsFull()){coutfullendl;returnfalse;}q[(rear=(rear+1)%maxSize)]=x;returntrue;}templateclassTboolSeqQueueT::DeQueue()12{if(IsEmpty()){coutUnderFlowendl;returnfalse;}front=(front+1)%maxSize;returntrue;}templateclassTvoidBinaryTreeT::LayerOrder(){if(root==0){coutThistreeisempty!endl;return;}BTNodeT*p=root;BTNodeTt;SeqQueueBTNodeTq(30);q.EnQueue(*p);while(!q.IsEmpty())13{q.Front(t);Visit(t.element);if(t.lChild){q.EnQueue(*t.lChild);}if(t.rChild){q.EnQueue(*t.rChild);}q.DeQueue();}}（2）程序流程图1415（3）完整代码：#includeiostreamusingnamespacestd;templateclassTclassSeqQueue{private:intfront,rear;intmaxSize;T*q;public:SeqQueue(intm);~SeqQueue(){delete[]q;}boolEnQueue(constTx);boolDeQueue();boolFront(T&x)const;boolIsEmpty(){returnfront==rear;};boolIsFull(){return(rear+1)%maxSize==front;};voidClear(){front=rear=0;}};templateclassT16SeqQueueT::SeqQueue(intm){maxSize=m;q=newT[m];front=rear=0;}templateclassTboolSeqQueueT::Front(T&x)const{x=q[(front+1)%maxSize];returntrue;}templateclassTboolSeqQueueT::EnQueue(constTx){if(IsFull()){coutfullendl;returnfalse;}17q[(rear=(rear+1)%maxSize)]=x;returntrue;}templateclassTboolSeqQueueT::DeQueue(){if(IsEmpty()){coutUnderFlowendl;returnfalse;}front=(front+1)%maxSize;returntrue;}templateclassTstructBTNode{BTNode(){lChild=rChild=NULL;}BTNode(constT&x){18element=x;lChild=rChild=NULL;}BTNode(constT&x,BTNodeT*l,BTNodeT*r){element=x;lChild=l;rChild=r;}Telement;BTNodeT*lChild,*rChild;};templateclassTclassBinaryTree{public:BinaryTree(){root=NULL;}~BinaryTree();boolIsEmpty()const;//判断二叉树是否为空voidClear();//释放二叉链表中的所有节点boolRoot(T&x)const;//获取根的元素voidMakeTree(constT&x,BinaryTreeT&left,BinaryTreeT&right);//19创建二叉树voidBreakTree(T&x,BinaryTreeT&left,BinaryTreeT&right);//删除二叉树voidPreOrder(void(*Visit)(T&x));//先序遍历voidInOrder(void(*Visit)(T&x));//中序遍历voidPostOrder(void(*Visit)(T&x));//后序遍历voidLayerOrder();//自上到下、从左到右的层次遍历intHigh();//求二叉树的高度intLeaves();//求二叉树中叶子结点的数目voidExchange();//交换二叉树的左右子数voidCopy(BinaryTreeT&p);//二叉树的复制（复制给p）protected:BTNodeT*root;private:voidClear(BTNodeT*&t);voidPreOrder(void(*Visit)(T&x),BTNodeT*t);voidInOrder(void(*Visit)(T&x),BTNodeT*t);voidPostOrder(void(*Visit)(T&x),BTNodeT*t);intHigh2(BTNodeT*p);voidLeaf(BTNodeT*p,int&a);BTNodeT*Copy(BTNodeT*t);voidChange(BTNodeT*t);20};templateclassTboolBinaryTreeT::Root(T&x)const{if(root){x=root-element;returntrue;}else{returnfalse;}}templateclassTvoidBinaryTreeT::MakeTree(constT&x,BinaryTreeT&left,Bin