二叉树与哈夫曼编码.docxVIP

实 验 报 告 （ 2014/ 2015 学年 第 二 学期） 课程名称数据结构实验名称实验二 二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2015年10月31日指导单位计算机软件学院指导教师骆健 学生姓名陈兵班级学号学院(系)计软院专 业软嵌NIIT  PAGE 32 实 验 报 告 实验名称 实验二 二叉树的基本操作及哈夫曼编码译码系统的实现指导教师骆健实验类型 设计实验学时 2实验时间实验目的和要求 （1）掌握二叉链表上实现二叉树基本去处的方法。 （2）学会设计基于遍历的求解二叉树应用问题的递归算法。 （3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。 二、实验环境(实验设备) 硬件: 微型计算机 软件: Microsoft Visual C++6.0 三、实验原理及内容 实验题一：在二叉链表上实现二叉树运算 （1）设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。 （2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。 （3）设计main函数，测试上述每个运算。 内容：1、建立头文件BTree.H，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件Test.cpp，编译并调试程序，直到正确运行。注意：需要用到队列的有关操作。 实 验 报 告 （一）概要设计 1.流程图及设计思想 用maketree构造一棵二叉树 创建二叉树 删除二叉树 先删除左子树再删除右子树，最后删除根节点，再释放结点空间 左右子树高度之和进行比较，谁大谁就是树的高度 树的高度 本质就是交换每个结点的左右子树 左右交换 用队列实现，将跟结点入队。一：出队并输出节点的值。 二： 若存在左右孩子，则将其入队。 循环以上两个步骤，直到队列为空。运用后序遍历思想，把树分解为左右子树和跟结点 节点数量 层次遍历二叉树 根据二叉树的定义和遍历算法的定义，和很容易实现 递归遍历二叉树 实 验 报 告 代码： #includeiostream using namespace std; templateclass T struct BTNode { BTNode(){ lChild = rChild = NULL } BTNode(const T x) { element = x; lChild = rChild = NULL; } BTNode(const T x, BTNodeT* l, BTNodeT* r) { element = x; lChild = l; rChild = r; } T element; BTNodeT *lChild, *rChild; }; templateclass T class BinaryTree { public : BinaryTree(){ root = NULL; } ~BinaryTree(){}; bool IsEmpty()const; void Clear(); bool Root(T x)const; void MakeTree(const T x, BinaryTreeT left, BinaryTreeT right); void MakeTree(BTNodeT* r); void BreakTree(T x, BinaryTreeT left, BinaryTreeT right); void DeleteTree(); void PreOrder(void(*Visit)(T x)); int GetTreeHeight()const; int GetLeavesNumber()const; BTNodeT* CopyTree()const; void ExchangeChildTree(); protected: BTNodeT* root; private: void Clear(BTNodeT* t); void PreOrder(void(*Visit)(T x),BTNodeT* t); void DeleteTree(BTNodeT *t); int GetTreeHeight(BTNodeT *t)const; int GetLeavesNumber(BTNodeT *t)const; BTNodeT* CopyTree(const BTNodeT *t)cons