二叉树与哈夫曼编码.doc

《二叉树与哈夫曼编码.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告（2014/2015学年第二学期）课程名称数据结构实验名称实验二二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2015年10月31日指导单位计算机软件学院指导教师骆健学生姓名陈兵班级学号B14041126学院(系)计软院专业软嵌NIIT实验报告实验名称实验二二叉树的基本操作及哈夫曼编码译码系统的实现指导教师骆健实验类型设计实验学时2实验时间一、实验目的和要求（1）掌握二叉链表上实现二叉树基本去处的方法。（2）学会设计基于遍历的求解二叉树应用问题的递归算法。（3）理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统。二、实验环境(实验设备)硬件:

2、微型计算机软件:MicrosoftVisualC++6.0三、实验原理及内容实验题一：在二叉链表上实现二叉树运算（1）设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。（2）设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。（3）设计main函数，测试上述每个运算。内容：1、建立头文件BTree.H，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件Test.cpp，编译并调试程序，直到正确运行。注意：

3、需要用到队列的有关操作。实验报告32（一）概要设计1.流程图及设计思想用maketree构造一棵二叉树创建二叉树删除二叉树先删除左子树再删除右子树，最后删除根节点，再释放结点空间左右子树高度之和进行比较，谁大谁就是树的高度树的高度本质就是交换每个结点的左右子树左右交换用队列实现，将跟结点入队。一：出队并输出节点的值。二：若存在左右孩子，则将其入队。循环以上两个步骤，直到队列为空。运用后序遍历思想，把树分解为左右子树和跟结点节点数量层次遍历二叉树根据二叉树的定义和遍历算法的定义，和很容易实现递归遍历二叉树实验报告32代码：#include

4、usingnamespacestd;templatestructBTNode{BTNode(){lChild=rChild=NULL}BTNode(constT&x){element=x;lChild=rChild=NULL;}BTNode(constT&x,BTNode*l,BTNode*r){element=x;lChild=l;rChild=r;}Telement;BTNode*lChild,*rChild;};templateclassBinaryTree{public:BinaryTree(){r

5、oot=NULL;}~BinaryTree(){};boolIsEmpty()const;voidClear();32boolRoot(T&x)const;voidMakeTree(constT&x,BinaryTree&left,BinaryTree&right);voidMakeTree(BTNode*r);voidBreakTree(T&x,BinaryTree&left,BinaryTree&right);voidDeleteTree();voidPreOrder(void(*Visit)(T&x));intGetTr

6、eeHeight()const;intGetLeavesNumber()const;BTNode*CopyTree()const;voidExchangeChildTree();protected:BTNode*root;private:voidClear(BTNode*&t);voidPreOrder(void(*Visit)(T&x),BTNode*t);voidDeleteTree(BTNode*t);intGetTreeHeight(BTNode*t)const;intGetLeavesNumber(BTNode

7、*t)const;BTNode*CopyTree(constBTNode*t)const;voidExchangeChildTree(BTNode*t);};templateboolBinaryTree::Root(T&x)const{if(root){x=root->element;returntrue;}else{32returnfalse;}}templatevoidBinaryTree::MakeTree(constT&x,BinaryTree&left,BinaryTree

8、&right){if(root

9、

10、&left==&right