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

的

实 验 报 告

（ 2021 / 2021学年 第二学期）

课程名称 实验名称

数据结构A

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

2021

实验时间 指导单位 指导教师

年 4 月 14 日

计算机科学与技术系

骆健

学生姓名 学院(系)

管理学院

班级学号 专 业

信息管理与信息系统

实习题名:二叉树的基本操作

班级 姓名 学号 日期2021.04.14 一、 问题描述 设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。设计main函数，测试上述每个运算。

二、 概要设计

文件tree.cpp中在该文件中定义二叉树的链式存储结构，用队列实现二叉树的层次遍历，并且编写实现二叉树的各种基本操作函数。其中包括结点类BTNode，循环队列类SeqQueue，二叉树类BinaryTree。主函数main的代码如图所示。

三、 详细设计

1. 类和类的层次设计

程序定义了循环队列SeqQueue类和二叉树BinaryTree类。SeqQueue类主要是用队列实现，层次遍历。运用后序遍历思想，把树分解为左右子树和跟结点再进行左右交换并计算树的高度，最后删除二叉树。

SeqQueue -int front, rear; -int maxSize; -BTNode **q; +SeqQueue(int mSize); +~SeqQueue(){delete []q;} +bool IsEmpty() const{return front == rear;} T +bool IsFull() const{return (rear + 1) % maxSize == front;} +bool Front(BTNode *&x)const; +bool EnQueue(BTNode *x); +bool DeQueue(); +void Clear(){front = rear = 0;} （a）循环队列类 T BinaryTree +BinaryTree():s(100){root = NULL;} +~BinaryTree(){delete

[]root;}

+bool

Clear();

+void

MakeTree(constT&x,BinaryTree&left,BinaryTree& +int High(BTNode*p); +int Node_num(BTNode*p);

+void

Exchange(BTNode

*&t);

+void

Level_traversal(void(*Visit)(T&x)); #SeqQueue s; -void Clear(BTNode* &t); -void Level_traversal(void(*Visit)(T&x),BTNode*t); （b）二叉树类

right); +BTNode*Copy (BTNode*t); 2. 核心算法

程序利用循环队列SeqQueue类通过不断出队并输出节点的值，将左右孩子入队直到队列为空实现二叉树的层次遍历。并运用后序遍历思想，将二叉树树分解为左右子树和根结点，利用(p -> lChild)和(p -> rChild)计算结点数目，并通过交换结点的左右子树实现左右交换，计算树的高度，最后删除二叉树。核心算法主要是二叉树BinaryTree类中的High，Node_num，Exchange，Level_traversal四个函数，其设计流程图如下：

High()

Node_num()

Exchange（）

Level_traversal()

四、程序代码

template

int BinaryTree::Node_num(BTNode*p) //叶子结点 { if(p) { if(p -> lChild == NULL && p -> rChild == NULL) return 1; else return Node_num(p -> lChild) + Node_num(p -> rChild); } else

return 0; }

template

感谢您的阅读，祝您生活愉快。