1 / 20 实 验 报 告（ 2015 / 2016 学年 第二学期）课程名称数据结构 A 实验名称二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2016 年4 月14 日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院 (系) 管理学院专业信息管理与信息系统实习题名 : 二叉树的基本操作班级 姓名学号日期 2016.04.14 一、问题描述设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。设计main 函数，测试上述每个运算。二、概要设计文件 tree.cpp中在该文件中定义二叉树的链式存储结构，用队列实现二叉树的层次遍历，并且编写实现二叉树的各种基本操作函数。其中包括结点类BTNode，循环队列类SeqQueue，二叉树类 BinaryTree 。主函数 main 的代码如图所示。2 / 20 三、详细设计1.类和类的层次设计程序定义了循环队列SeqQueue类和二叉树BinaryTree类。 SeqQueue类主要是用队列实现，层次遍历。运用后序遍历思想，把树分解为左右子树和跟结点再进行左右交换并计算树的高度，最后删除二叉树。（a）循环队列类SeqQueue -int front, rear; -int maxSize; -BTNode **q; +SeqQueue(int mSize); +~SeqQueue(){delete []q;} +bool IsEmpty() const{return front == rear;} +bool IsFull() const{return (rear + 1) % maxSize == front;} +bool Front(BTNode *&x)const; +bool EnQueue(BTNode *x); +bool DeQueue(); +void Clear(){front = rear = 0;} T T 3 / 20 （ b）二叉树类2.核心算法程序利用循环队列SeqQueue类通过不断出队并输出节点的值，将左右孩子入队直到队列为空实现二叉树的层次遍历。 并运用后序遍历思想，将二叉树树分解为左右子树和根结点，利用 (p -> lChild)和(p -> rChild)计算结点数目，并通过交换结点的左右子树实现左右交换，计算树的高度，最后删除二叉树。核心算法主要是二叉树 BinaryTree类中的 High ，Node_num，Exchange，Level_traversal四个函数，其设计流程图如下：High() Node_num() BinaryTree +BinaryTree():s(100){root = NULL;} +~BinaryTree(){delete []root;} +bool Clear(); +void MakeTree(constT&x,BinaryTree&left,BinaryTree& righ...
VIP
