B11041309数据结构试验二

1、AU点曙/身（2012/2013学年第二学期）题目：二叉树的基本操作及哈夫曼编专业服务外包学生姓名王翰林班级学号B11041209指导教师邹志强指导单位计算机软件学院日期2012.10.26简短评语教师签名：年月日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格一.实验目的和要求目的：1、掌握二叉链表上实现二叉树基本操作。2、学会设计基于遍历的求解二叉树应用问题的递归算法。3、理解哈夫曼树的构造算法，学习设计哈夫曼编码和译码系统要求：能成功演示二叉树的有关算法，运算完毕后能成功释放二叉树所有结点占用的系统类存。二.实验环境(实验设备)学校机房电脑设备硬件，VC+6.0软件三.实验原理

2、及内容原理：(1)在二叉树上实现二叉树运算1:设计递归算法，实现下列二叉树运算：删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子结点数，复制一棵二叉树，交换一棵二叉树的左右子树。2:设计算法，按自上到下，自左向右的次序，即按层次遍历一棵二叉树。3:设计main函数，测试上述每个运算。(2)哈夫曼编码和译码系统1:所设计的系统重复显示以下菜单项。B一建树：读入字符集和各字符频度，建立哈夫曼树。T一遍历：先序和中序遍历二叉树。E一生成编码：根据已建成的哈夫曼树，产生个字符的哈夫曼编码。C一编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼树进行编码，显示编码结果，并将输入的字符串及

3、其编码结果保存在磁盘文件中。D译码：读入文件，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件P一打印：屏幕显示文件。X一退出。内容：1、建立头文件BTree.H,在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件Test.cpp,编译并调试程序，直到正确运行。注意：需要用到队列的有关操作。说明：二叉树的基本操作可包括：(1)voidClear(BTreeNode*BT)/消除一棵二叉树，并释放结点空间(2) voidMakeTree(BTreeNode*BT)(3) voidBreakTree(BTreeNode*BT)(4)v

4、oidPreOrder(BTreeNode*BT)(5)voidInOrder(BTreeNode*BT)(6)voidPostOrder(BTreeNode*BT)(7)voidFloorOrder(BTreeNode*BT)(8)intSize(BTreeNode*BT)/(9)voidExchange(BTreeNode*BT)(10)intGetHeight(BTreeNode*BT)四.概要设计/构造一棵二叉树BT/撤销一棵二叉树BT/先序遍历二叉树BT/中序遍历二叉树BT/后序遍历二叉树BT/层次遍历二叉树BT求二叉树BT的结点数量/把二叉树BT的左右子树进行交换/求二叉树BT的高

5、度1.流程图及设计思想求树的高度左右子树高度之和进行比较，谁大谁就是树的高度删除二叉树先删除左子树，再删-除右子树，最后删除根节点，再释放结点空间2,本程序包含的模块(1)主程序模块Voidmain()(初始化；构造一棵二叉树；各种遍历二叉树；对二叉树进行各种常见运算；删除二叉树；)(2)二叉树模块一一实现二叉树的抽象数据类型和基本操作(3)队列模块一一实现队列的抽象数据类(4)二叉树运算模块一一求二叉树的结点，叶子数目五.详细设计一.先序遍历：A.自然语言描述：1,判断根节点会否为空，如果为空，返回2.如果根节点不为空3,先输出根节点，再递归调用自身依次输出左孩子和右孩子B.代码详细分析te

6、mplate<classT>voidBinaryTree<T>:PreOrder(void(*Visit)(T&x)(PreOrder(Visit,root);)template<classT>voidBinaryTree<T>:PreOrder(void(*Visit)(T&x),BTNode<T>*t)(if(t)(Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);二.中序遍历：A.自然语言描述：1 .判断根

7、节点是否为空，如果为空，返回2 .如果根节点不为空3 .递归调用自身输出左孩子，再输出根结点，递归调用输出右孩子B.代码详细分析：template<classT>voidBinaryTree<T>:InOrder(void(*Visit)(T&x)(InOrder(Visit,root);template<classT>voidBinaryTree<T>:InOrder(void(*Visit)(T&x),BTNode<T>*t)(if(t)(InOrder(Visit,t->lChild);Visit(t-&g

8、t;element);InOrder(Visit,t->rChild);三.后序遍历：A.自然语言描述：1 .判断根节点是否为空，如果为空，返回2 .如果根节点不为空3 .递归调用自身输出左孩子和右孩子，再输出根结点B.代码详细分析：template<classT>voidBinaryTree<T>:PostOrder(void(*Visit)(T&x)(PostOrder(Visit,root);template<classT>voidBinaryTree<T>:PostOrder(void(*Visit)(T&x),BT

9、Node<T>*t)(if(t)(PostOrder(Visit,t->lChild);PostOrder(Visit,t->rChild);Visit(t->element);四.层次遍历二叉树：A.自然语言描述：1 .定义头指针和尾指针和空指针p2 .根节点是否为空，如果是，结束3 .如果不是，根节点入队4 .取队首元素，输出队首元素5 .将队首的非空左右结点入队列，删除队首元素6 .循环下去，直到队列为空B.代码详细分析：template<classT>voidBinaryTree<T>:FloorOrder(void(*Visit)

10、(T&x)(FloorOrder(Visit,root);template<classT>voidBinaryTree<T>:;FloorOrder(void(*Visit)(Visit<T>*x),BTNode<T>*t)(SeqQueue<BTNode<T>*>se(100);se.EnQueue(t);BTNode<T>*temp;while(!se.IsEmpty()(se.Front(temp);Visit(temp);se.DeQueue();if(temp->lchild)se.En

11、Queue(temp->lchild);if(temp->child)se.EnQueue(temp->rchild);五.求二叉树的结点数：A.自然语言描述：1：判断根节点是否为空，如果为空，返回02:如果根节点不为空3:递归调用求二叉树的结点数的函数，参数改为根节点的左孩子4:递归调用求二叉树的结点数的函数，参数改为根节点的右孩子5:返回根节点的左右字数的结点数之和B.代码详细分析：template<classT>intBinaryTree<T>:Size()(returnSize(root);template<classT>intBi

12、naryTree<T>:Size(BTNode<T>*t)(if(!t)return0;elsereturnSize(t->lChild)+Size(t->rChild)+1;)六.二叉树的左右交换：A.自然语言描述：1 .判断根节点是否为空，如果为空，返回2 .如果不为空，再判断该节点左右孩子是否同时为空，3 .如果是，返回4 .如果不为空，交换左右孩子5 .返回循环，遍历左右子树B.代码详细分析：template<classT>voidBinaryTree<T>:Exchange()(Exchange(root);)templat

13、e<classT>voidBinaryTree<T>:Exchange(BTNode<T>*t)(if(!t)return;BTNode<T>*temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);)七.求二叉树的深度：A.自然语言描述：1：判断根节点是否为空，如果根节点为空，返回02:如果根节点不为空但是根节点的左右孩子同时为空，返回13:如果以上两个条件都不成立4:递归调用

14、求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为15:递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为06:返回4与5步中得出深度较大的那个数作为二叉树的深度数B.代码详细分析：template<classT>intBinaryTree<T>:GetHeight(BTNode<T>*t)(inttempl;inttempr;if(!t)return0;templ=GetHeight(t->lChild);tempr=GetHeight(t->rChild);if(templ+>tempr+)returnt

15、empl;elsereturntempr;六.实验总结：在刚进行编写这个程序的时候，只是机械的将课本上的算法敲上去，然后执行，可是在后面的几个功能中，在需要在前面的基础上进行改变，例如：在求深度的时候，则和遍历有点类似，只不过，深度是分别遍历左子树和右子树，然后比较；最难的则是层次遍历了，最初的时候一点儿思绪也没有，后来在同学的帮助下和上网查了相关的资料，才编写出来,真可谓几经波折。实验任务要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力，让更加了解编程思想和编程技巧。这次实验设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往

16、往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。例如：在撤销一棵二叉树时删除根节点，没有把根节点置为空，又或者中请了一个新的结点空间，却没有把它释放等等。这次实验让我收获不少，我认识到了，大一的课程确实没有学好，一定程度上影响到了这次程序设计，不过我的确把二叉树的一些基本概念掌握得更牢固了，学到了二叉树的一些基本运算，多多少少给我积累了编程的经验，更加激发了我对数据结构的兴趣，让我更有信心把这门课学好，让我更有信心把这门专业学好。谢谢老师！七.测试结果：C:UserssaoxueerDesktopDSA-Exp-2-only_BTreeTest.exe前序遍历BDCEF中序遍历

17、DBECF后序遍历DEFCB结点数和5当右头震后的前序遢历BCFED树的图度曲八.“二叉树基本运算”源代码:BTree.h:#include<iostream>usingnamespacestd;template<classT>structBTNode(Telement;BTNode<T>*lChild,*rChild;BTNode()(lChild=rChild=NULL;BTNode(constT&x)(element=x;lChild=rChild=NULL;BTNode(constT&x,BTNode<T>*l,BTNod

18、e<T>*r)(element=x;lChild=l;rChild=r;template<classT>classBinaryTree(public:BinaryTree()root=NULL;BinaryTree()Clear(root);boolIsEmpty()const;voidClear();boolRoot(T&x)const;intSize();voidMakeTree(constT&e,BinaryTree<T>&left,BinaryTree<T>&right);voidBreakTree(T&a

19、mp;e,BinaryTree<T>&left,BinaryTree<T>&right);voidLevelOrder(void(*Visit(T&x);voidPreOrder(void(*Visit)(T&x);voidInOrder(void(*Visit)(T&x);voidPostOrder(void(*Visit)(T&x);voidExchange();intGetHeight();protected:BTNode<T>*root;private:voidClear(BTNode<T>

20、*t);intSize(BTNode<T>*t);voidLevelOrder(void(*Visit)(T&x),BTNode<T>*t);voidPreOrder(void(*Visit)(T&x),BTNode<T>*t);voidInOrder(void(*Visit)(T&x),BTNode<T>*t);voidPostOrder(void(*Visit)(T&x),BTNode<T>*t);voidExchange(BTNode<T>*t);intGetHeight(BTNode

21、<T>*t);template<classT>voidBinaryTree<T>:Clear(BTNode<T>*t)if(!t)return;Clear(t->lChild);Clear(t->rChild);deletet;template<classT>boolBinaryTree<T>:Root(T&x)constif(root)x=root->element;returntrue;elsereturnfalse;template<classT>voidBinaryTree&l

22、t;T>:MakeTree(constT&e,BinaryTree<T>&left,BinaryTree<T>&right)if(root|&left=&right)return;root=newBTNode<T>(e,left.root,right.root);left.root=right.root=NULL;template<classT>voidBinaryTree<T>:BreakTree(T&x,BinaryTree<T>&left,BinaryTr

23、ee<T>&right)if(!root|&left=&right|left.root|right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;deleteroot;root=NULL;template<classT>voidVisit(T&x)cout<<x<<""template<classT>voidBinaryTree<T>:PreOrder

24、(void(*Visit)(T&x)PreOrder(Visit,root);template<classT>voidBinaryTree<T>二PreOrder(void(*Visit)(T&x),BTNode<T>*t)if(t)Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);template<classT>voidBinaryTree<T>:InOrder(void(*Visit)(T&x)InO

25、rder(Visit,root);template<classT>voidBinaryTree<T>:InOrder(void(*Visit)(T&x),BTNode<T>*t)if(t)InOrder(Visit,t->lChild);Visit(t->element);InOrder(Visit,t->rChild);template<classT>voidBinaryTree<T>:PostOrder(void(*Visit)(T&x)PostOrder(Visit,root);)templat

26、e<classT>voidBinaryTree<T>:PostOrder(void(*Visit)(T&x),BTNode<T>*t)if(t)PostOrder(Visit,t->lChild);PostOrder(Visit,t->rChild);Visit(t->element);)template<classT>voidBinaryTree<T>:FloorOrder(void(*Visit)(T&x)FloorOrder(Visit,root);)template<classT>

27、voidBinaryTree<T>:FloorOrder(void(*Visit)(T&x),BTNode<T>*t)SeqQueue<BTNode<T>*>se(100);se.EnQueue(t);BTNode<T>*tmp;while(!se.IsEmpty()se.Front(tmp);Visit(tmp);se.DeQueue();if(tmp->lChild)se.EnQueue(tmp->lChild);if(tmp->Child)se.EnQueue(tmp->rChild);)temp

28、late<classT>intBinaryTree<T>:Size()(returnSize(root);)template<classT>intBinaryTree<T>:Size(BTNode<T>*t)(if(!t)return0;elsereturnSize(t->lChild)+Size(t->rChild)+1;)template<classT>voidBinaryTree<T>:Exchange()(Exchange(root);)template<classT>voidBinaryTree<T>:Exchange(BTNode<T>*t)(if(!t)return;BTNode<T>*temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);)template<classT>intBinaryTree<T>:GetHeight()(return