南邮实验报告2二叉树及哈夫曼编码.doc

实 验 报 告 （ 2013/ 2014 学年 第 二 学期） 课程名称 数据结构A 实验名称 实验二 二叉树的基本操作及哈夫曼编码译码系统的实现 实验时间 2014 年 4 月 8 日 指导单位 计算机学院计算机软件教学中心 指导教师 朱立华 学生姓名 班级学号 学院(系) 专 业 实 验 报 告 实验名称 实验二 二叉树的基本操作及哈夫曼编码译码系统的实现 指导教师 朱立华 实验类型 设计 实验学时 2 实验时间 2014.4.8 实验目的和要求 （1）掌握二叉链表上实现二叉树基本去处的方法。 （2）学会设计基于遍历的求解二叉树应用问题的递归算法。 （3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。 二、实验环境(实验设备) 硬件: 微型计算机 软件: Microsoft Visual C++6.0 三、实验原理及内容 实验题一：在二叉链表上实现二叉树运算 （1）设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。 （2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。 （3）设计main函数，测试上述每个运算。 实 验 报 告 #include iostream 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(){Clear(root);} bool IsEmpty()const; void Clear(); bool Root(T x)const; BTNodeT* Root(); void MakeTree(const T e, BinaryTreeT left, BinaryTreeT right); void BreakTree(T e, BinaryTreeT left, BinaryTreeT right); void PreOrder(void(*Visit)(T x)); void InOrder(void(*Visit)(T x)); void PostOrder(void(*Visit)(T x)); int Size(); int Leaves(); BTNodeT* Copy(BTNodeT* t); int Count(){ return Count(root);} void Exchange(); protected: BTNodeT* root; private: void Exch(BTNodeT* p); 实 验 报 告 void Leaves(BTNodeT* t, int count); int Size(BTNodeT* t); int Count(BTNodeT* t){ if(!t) return 0; if(((t-lChild) (!t-rChild))||((!t-lChild) (t-rChild))) return 1; return Count(t-lChild) + Count(t-rChild); } void Clear(BTNodeT* t); void PreOrder(void(*Visit)(T x),BTNodeT* t); void InOrder(void(*Visit)(T x), BTNodeT* t); void PostOrder(void(*Visit)(T x), BTNodeT* t); }; template class T void BinaryTreeT::Exchange(){ Exch(root); } te