南邮数据结构上机实验二二叉树的基本操作及哈夫曼编码译码系统的实现

《南邮数据结构上机实验二二叉树的基本操作及哈夫曼编码译码系统的实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、（2015/2016学年第二学期）课程名称实验名称实验时间指导单位指导教师学生姓名学院（系）数据结构A二叉树的基本操作及哈夫曼编码译码系统的实现2016年4月14曰计算机科学与技术系班级学号管理学院专业信息管理与信息系统骆健实习题名:二叉树的基本操作班级_姓名学号—円期2016.04.14一、问题描述设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树屮叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。设汁算法,按白上到下，从左到右的顺序，按层次遍历一棵二叉树。设计main函数，测试上

2、述每个运算。二、概要设计文件tree,cpp屮在该文件屮定义二义树的链式存储结构，川队列实现二义树的层次遍历，并且编写实现二叉树的各种基本楝作函数。其中乜括结点类BTNode,循环队列类SeqQueue,二叉树类BinaryTree、主函数main的代码如图所示。三、详细设计1.类和类的层次设计程序定义/循环队列SeqQueue炎和二义树Binar*yTree炎。SeqQueue炎主要是用队列实现，层次遍历。运用后序遍历思想，把树分解为左右子树和跟结点再进行左右交换并计算树的高度，最后删除二叉树。SeqQueue-in

3、tfront,rear;-intmaxSize;-BTNode**q;+SeqQueue(intmSize);+〜SeqQueue(){delete[]q;}+boolIsEmptyOconst{returnfront二二rear;}+boolIsFull()const{return(rear+1)%maxSize==front;}+boolFront(BTNode*&x)const;+boolEnQueue(BTNode*x);+boolDcQucuc();+vnidClearfVfront=rea

4、r=(V1(a)循环队列类TBinaryTree+BinaryTree():s(l(X)){root=NULL;)+-BinaryTree(){delete[]root;}+boolClear();+voidMakeTree(constT&x,BinaryTree&left,BinaryTree&right);+intHigh(BTNode*p);+intNode_num(BTNode*p);+BTNode*Copy(BTNode*t);+voidExchange(BTNode

5、*&t);十voidLevel_traversal(void(*Visit)(T&x));#SeqQueues;-voidClear(BTNode*&t);-voidLevel_traversal(void(*Visit)(T&x),BTNode*t);(b)二叉树类1.核心算法程序利川循环队列SeqQueue类通过不断出队#•输出节点的值，将左右孩子入队直到队列为空实现二义树的层次遍历。并运用后序遍历思想，将二义树树分解为左右子树和根结点,利用(P-〉IChild)和(p-〉rChild)计算结点数

6、鬥，并通过交换结点的左右子树实现左右交换，计算树的高度，最后删除二叉树。核心算法主要是二叉树BinaryTree炎中的High,Nodenum，Exchange,Leveltraversal网个函数，其设计流程图如下：P==NULLNExchange()BTNodeT--Level_traversal0四、程序代码templateintBinaryTree::Node_num(BTNode*p)//叶子结点{if(p){if(p->IChild==NULL&&p->rChild==NULL)

7、return1;elsereturnNode_num(p->IChild)+Node一num(p-〉rChild);}elsereturn0;}tcmplatcvoidBinaryTree::Exchange(BTNode*&t)//左右子树交换{if(t){BTNode*q=t->IChild;t->IChild=t->rChild;t->rChild=q;Exchange(t->IChild);Exchange(t->rChild);}}templatevoidBi

8、naryTree::Level_traversal(void(*Visit)(T&x))//层次遍历{Lcvcl_travcr$al(Visit,root);cout«endl;//S次遍历templatevoidBinaryTree::Level_traversal(void(*Visit)(T&x)