大数据结构实验三邵彬彬.doc

《大数据结构实验三邵彬彬.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三二叉树一、实验目的1．掌握二叉树的链式存储结构及其相关操作的实现。2．掌握二叉树的先序、中序、后序的递归遍历算法。3．理解二叉树的各种非递归遍历算法的实现。二、实验要求1．实验前做好充分准备，包括复习第六章所学容，事先预习好本次实验容。2．实验时记录实验结果，按要求完成各题。3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验容实验要求实验类型二叉树4（1）二叉树的创建、递归遍历及其它基本操作的实现。必做设计性（2）二叉树非递归遍历算法的实现。选做设计性（3）哈夫曼树及哈夫

2、曼编码的算法实现。选做综合性说明：（1）实验容1）为必做容。（2）实验容2）与实验容3）为选做容。四、实验容与要求1、实验题目一：（1）二叉树的创建、递归遍历及其它基本操作的实现。要求：定义用二叉链表表示的二叉树，并实现二叉树的创建、遍历（先序、中序后序）的递归算法及求深度操作等，并对其进行验证。2、实验题目二：二叉树非递归遍历算法的实现要求：在题目一的基础上，实现二叉树的非递归遍历算法（先序、中序、后序或按层），并对其进行验证。3、实验题目三：哈夫曼树及哈夫曼编码的算法实现要求：编程实现哈夫曼树的创建及利用哈夫曼树求解哈夫曼编码。五、实验步骤源代码：

3、#include#includeusingnamespacestd;templatestructBinTreeNode//二叉树结点类定义{Tdata;//数据域BinTreeNode*leftChild,*rightChild;//左子女、右子女域BinTreeNode(Tx=T(),BinTreeNode*l=NULL,BinTreeNode*r=NULL):data(x),leftChild(l),rightChild(r){}//可选择参数的默认构造函数};//--------

4、-----------------------------------------------------------------templatevoidPreOrder_2(BinTreeNode*p)//非递归前序遍历{stack*>S;while(p!=NULL

5、

6、!S.empty()){while(p!=NULL){cout<data;//访问根结点S.push(p);p=p->leftChild;//遍历指针进到左子女结点}if(!S.empty())//栈不空时退栈{p=S.top

7、();S.pop();p=p->rightChild;//遍历指针进到右子女结点}}}//----------------------------------------------------------------templatevoidInOrder_2(BinTreeNode*p)//非递归中序遍历{stack*>S;do{while(p!=NULL)//遍历指针未到最左下的结点，不空{S.push(p);p=p->leftChild;}if(!S.empty())//栈不空时退栈{p=S.t

8、op();S.pop();cout<data;p=p->rightChild;}}while(p!=NULL

9、

10、!S.empty());}//------------------------------------------------------------------templatevoidPostOrder_2(BinTreeNode*p)//非递归后序遍历{stack*>S;stacktag;//定义一个新的栈用来保存tag域判别根结点的左右子树是否均遍历过while(p!

11、=NULL

12、

13、!S.empty())//左子树经过结点加L进栈{while(p!=NULL){S.push(p);//首先将t和tag为0入栈，遍历左子树tag.push(0);//遍历左子树前的现场保护p=p->leftChild;}while(!S.empty()&&tag.top()==1){p=S.top();S.pop();tag.pop();cout<data;//最后访问根结点。}if(!S.empty()){tag.pop();tag.push(1);//遍历右子树前的现场保护,修改栈顶tag为1，遍历右子树p=S.top();

14、//取栈顶保存的指针p=p->rightChild;}elsebreak;}}//------