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

实验报告

（ / 学年第一学期）

课程名称

数据结构A

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

实现

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

学生姓名 学院(系)

年

月 日

班级学号 专业

实验报告

实验名称 二叉树的基本操作及哈夫曼编码译码系统的实现 实验类型 上机 实验学时 实验时间 指导教师 一、 实验目的和要求 实验目的： 1、掌握二叉链表上实现二叉树基本运算的方法。 2、学会设计基于遍历的求解二叉树应用问题的递归算法。 3、理解哈夫曼树的构造算法，学会设计哈夫曼编码和译码系统。 内容和要求： 1、在二叉链表上实现二叉树运算 1设计递归算法，实现下列算法：删除一棵二叉树，求一棵二叉树的高度，○求一棵二叉树中叶子结点的个数，复制一棵二叉树，交换一颗二叉树的左右子树。 2设计算法，按自上到下，自左向右的次序，即按层次遍历一颗二叉树。 ○3设计main函数，测试上述每个运算。 ○2、哈夫曼编码和译码系统 设计的系统重复显示以下菜单项：建树、遍历、生成编码、编码、译码、打印、退出并且实现这些功能。 2

二、实验环境(实验设备) 硬件：PC 软件：Code::Blocks (C++) 3

三、实验原理及内容 1、线性表的基本运算 （1）核心算法 1删除一颗二叉树： ○思路：将一颗二叉树拆分成三部分，执行语句“delete root; root=NULL”,将原二叉树的根结点回收。 代码： template void &x,BinaryTree&left,BinaryTree&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; } 4

BinaryTree::BreakTree(T