大数据结构实验三邵彬彬

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

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

3、ack> using namespace std;template<class T>struct BinTreeNode/二叉树结点类定义T data; / 数据域BinTreeNode<T> *leftChild,*rightChild;/ 左子女、右子女域BinTreeNode(T x=T(),BinTreeNode<T>* l =NULL,BinTreeNode<T>* r = NULL ) :data(x),leftChild(l),rightChild(r)/ 可选择参数的默认构造函数;/template<class T&g

4、t;void PreOrder_2(BinTreeNode<T> *p)/ 非递归前序遍历stack<BinTreeNode<T> * > S;while(p!=NULL | !S.empty()while(p!=NULL)cout<<p->data;S.push(p);p=p->leftChild;if(!S.empty()/访问根结点/遍历指针进到左子女结点/栈不空时退栈p=S.top();/遍历指针进到右子女结点S.pop(); p = p->rightChild;/template<class T>void

5、InOrder_2(BinTreeNode<T> *p)/ 非递归中序遍历stack<BinTreeNode<T>* > S;do while(p!=NULL) S.push(p);p=p->leftChild;if(!S.empty()p=S.top();S.pop();cout<<p->data;p=p->rightChild;while(p !=NULL | !S.empty();/遍历指针未到最左下的结点，不空/栈不空时退栈/template<class T>void PostOrder_2(BinTreeN

6、ode<T> *p) / 非递归后序遍历 stack<BinTreeNode<T> * > S;stack<int> tag;/ 定义一个新的栈用来保存 tag 域判别根结点的左右子树是否均遍历过 while(p != NULL | !S.empty() / 左子树经过结点加 L 进栈while(p!=NULL)S.push(p); / 首先将 t 和 tag 为 0 入栈，遍历左子树tag.push(O);/遍历左子树前的现场保护p=p->leftChild;while( !S.empty() && tag.top()=1

7、)p=S.top();S.pop();tag.pop();cout<<p->data;if( !S.empty()/最后访问根结点。tag.pop();tag.push(1);/ 遍历右子树前的现场保护 ,修改栈顶 tag 为 1，遍历右子树 p=S.top(); / 取栈顶保存的指针p=p->rightChild;elsebreak;/template<class T>void InOrder_1(BinTreeNode<T> * subTree)/ 递归函数：中序次序遍历以subTree 为根的子树。if(subTree !=NULL) /N

8、ULL 是递归终止条件 InOrder_1(subTree->leftChild); /中序遍历根的左子树cout<<subTree->data; /访问根结点 InOrder_1(subTree->rightChild);/中序遍历根的右子树/template<class T>void PreOrder_1(BinTreeNode<T> * subTree)/递归函数：前序遍历以subTree为根的二叉树。if(subTree !=NULL)/递归结束条件cout<<subTree->data; 访问根结点PreOrde

9、r_1(subTree->leftChild);/前序遍历根的左子树PreOrder_1(subTree->rightChild);/前序遍历根的右子树/template<class T>void PostOrder_1(BinTreeNode<T> * subTree)/递归函数：后序次序遍历以subTree为根的子树。if(subTree !=NULL)/NULL 是递归终止条件PostOrder_1(subTree->leftChild); /后序遍历根的左子树PostOrder_1(subTree->rightChild); / 后序遍历

10、根的右子树cout<<subTree->data; /访问根结点/template<class T>void CreateBinTree(BinTreeNode<T> * & subTree)/ 递归方式建立二叉树T item;cin>>item;if(item !=-1) subTree = new BinTreeNode<T>();if(subTree = NULL)cerr<<" 存储分配错！ "<<endl; exit(1);subTree->data = ite

11、m;CreateBinTree(subTree->leftChild); / 递归建立左子树 CreateBinTree(subTree->rightChild); /递归建立右子树 else subTree = NULL;/封闭指向空子树的指针 int main()BinTreeNode<int> * Tree = NULL;cout<<"请输入每个结点，回车确认，并以-1结束:CreateBinTree(Tree);cout<<" 先序遍历二叉树结果:"PreOrder_1(Tree);cout<<e

12、ndl;cout<<" 中序遍历二叉树结果:"InOrder_1(Tree);cout<<endl;cout<<" 后序遍历二叉树结果:"PostOrder_1(Tree); cout<<e ndl;cout<<"非递归前序遍历二叉树结果:PreOrder_2(Tree); cout<<e ndl;cout<<"非递归中序遍历二叉树结果:InO rder_2(Tree); cout<<e ndl;cout<<"非递归后序遍历二叉树结果:PostOrder_2(Tree); cout<<e ndl; return 1;调试图片：E:C + 二叉錚Debug'BinaryTree.exe"-1 1 1 确一 车6! e6果果果nil3結結管那耶应O 回果果M-叉叉叉C ,5结结结二二二to 点4BBS历历历y 结1叉叉叉鲁薯 个二二二 Iwty 每T历历IQ刖中后an 入3遍归归S 输 2S5EO!递递es 请 L 先中 pr并以-1结束