您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 2012《数据结构》上机实验报告-二叉树遍历
西华大学数计学院学生上机实践报告第1页共10页西华数学与计算机学院上机实践报告课程名称:数据结构年级:2011上机实践成绩:指导教师:唐剑梅姓名:蒋俊上机实践名称:学号:312011080611118上机实践日期:2012-11-20上机实践编号:2上机实践时间:8:00-9:30一、实验目的1.熟练掌握二叉树在二叉链表存储结构中的常用遍历方法:先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解二叉树的按层遍历、先序非递归遍历及后序非递归遍历。2.用树解决实际问题,如哈夫曼编码等。加深对“数据结构+算法=程序”的理解和认识,提高编写较复杂程序的能力。二、实验内容建立一棵二叉树,分别用“先根非递归”方法、“按层遍历”的方法遍历。三、实验环境硬件:微型计算机P4软件:WindowsXP+MicrosoftVisualC++6.0四、程序源码及调试过程#includeiostream.h#include2.h#include3.htypedefintElemType;structNodeType//定义结点结构体{ElemTypedata;NodeType*lch,*rch;};classBiTree//定义二叉树类{public:BiTree(){root=NULL;};//构造函数~BiTree(){destroy(root);}//析构函数voidinorder()//中序遍历{inorder(root);}voidpreordertswap()//利用先序遍历方法交换左右子树{preorderswap(root);}西华大学数计学院学生上机实践报告第2页共10页inttheight()//求二叉树高度{returnheight(root);}voidcreat0();voidpreoder();//先根遍历非递归voidlevelorder();//按层遍历二叉树private:NodeType*root;//数据成员,树根NodeType*creat();//建立二叉树递归方法voidinorder(NodeType*p);//中序遍历voidpreorderswap(NodeType*p);//利用先序遍历方法交换左右子树intheight(NodeType*p);//求二叉树高度递归算法voiddestroy(NodeType*&p);//删除二叉树所有结点};voidBiTree::creat0()//建立树函数,{cout请按照树的先序遍历顺序组织数据endl;cout若结点信息是int,把每个结点的空孩子以0输入;endl;cout例如一个结点的二叉树11,输入:1100;endl;root=creat();//调用私有creat();}NodeType*BiTree::creat()//递归建立二叉树算法{NodeType*p;ElemTypex;cout\n输入数据:;cinx;if(x==0)p=NULL;else{p=newNodeType;p-data=x;p-lch=creat();//递归调用自身p-rch=creat();}returnp;}voidBiTree::preoder()//先根遍历非递归{NodeType*q;SqStackNodeType*s;q=root;intboo=1;cout先根非递归遍历endl;do{while(q!=NULL)西华大学数计学院学生上机实践报告第3页共10页{coutq-data;s.push(q);q=q-lch;}if(s.IsEmpty())boo=0;else{q=s.pop();q=q-rch;}}while(boo);coutendl;}voidBiTree::inorder(NodeType*p)//中根遍历{if(p!=NULL){inorder(p-lch);coutp-data;inorder(p-rch);}}voidBiTree::preorderswap(NodeType*p)//利用先序遍历方法交换左右子树{if(p!=NULL){NodeType*r;r=p-lch;p-lch=p-rch;p-rch=r;//上面几条语句可以认为对结点的访问(交换左右孩子)//替换了原来的:coutp-data;语句preorderswap(p-lch);preorderswap(p-rch);}}voidBiTree::destroy(NodeType*&p)//删除二叉树所有结点{if(p!=NULL){destroy(p-lch);destroy(p-rch);deletep;p=NULL;}}intBiTree::height(NodeType*p)//求二叉树高度(递归){if(p==NULL)return0;else{inthl=height(p-lch);inthr=height(p-rch);return1+(hlhr?hl:hr);//1加上hl和hr的较大值}}西华大学数计学院学生上机实践报告第4页共10页voidBiTree::levelorder()//按层遍历{SqQueueNodeType*q;NodeType*p;p=root;if(p!=NULL)q.EnQueue(p);while(!q.IsEmpty()){p=q.DeQueue();coutp-data;if(p-lch!=NULL)q.EnQueue(p-lch);if(p-rch!=NULL)q.EnQueue(p-rch);}}//---------------------------------------------------------------------------intmain(){intk;BiTreeroot0;//声明创建二叉树对象,调用构造函数do{cout\n\n;cout\n\n1.建立二叉树;cout\n\n2.交换左右子树;cout\n\n3.求二叉树深度;cout\n\n4.先根非递归遍历;cout\n\n5.按层遍历二叉树;cout\n\n6.结束程序运行;cout\n======================================;cout\n请输入您的选择(1,2,3,4):;cink;switch(k){case1:{cout\n建立二叉树:;root0.creat0();cout\n中根遍历结果:;root0.inorder();}break;case2:{root0.preordertswap();西华大学数计学院学生上机实践报告第5页共10页cout\n交换左右子树后中根遍历结果:;root0.inorder();}break;case3:{intdeep;deep=root0.theight();cout\n树的深度是:deep;}break;case4:{cout\n先根遍历的结果:;root0.preoder();}break;case5:{cout\n按层遍历二叉树的结果:;root0.levelorder();}break;case6:break;}cout\n----------------;}while(k=1&&k6);return0;}//栈的顺序存储结构,顺序栈类#includeiostream.h#includeiomanip.h//------------------------------栈的顺序存储结构-----------------------------//typedefintElemType;//数据元素的类型//constintMAXSIZE=100;//数组的容量templateclassTclassSqStack{private:T*elem;intmaxSize;inttop;public:SqStack(ints=30);~SqStack(){delete[]elem;}voidpush(Titem);Tpop();西华大学数计学院学生上机实践报告第6页共10页voidPrintOut();intIsEmpty(){returntop==-1;}intIsFull(){returntop==maxSize-1;}};//-------------------------------------------------------------templateclassTSqStackT::SqStack(ints){top=-1;maxSize=s;elem=newT[maxSize];for(inti=0;imaxSize;i++)elem[i]=0;}templateclassTvoidSqStackT::push(Titem){if(!IsFull()){top++;elem[top]=item;}}templateclassTTSqStackT::pop(){Tx;if(!IsEmpty()){x=elem[top];top--;}returnx;}templateclassTvoidSqStackT::PrintOut(){intt;if(!IsEmpty())cout栈已空endl;else{i=top;while(i!=-1){coutdata=elem[i];i--;}}}队列的顺序存储结构#includeiostream.htemplateclassTclassSqQueue{public:SqQueue(intsz=30);~SqQueue(){delete[]elem;}voidEnQueue(Titem);TDeQueue();TGetFront();西华大学数计学院学生上机实践报告第7页共10页intIsEmpty(){returnfront==rear;}intIsFull(){return(rear+1)%maxSize==front;}intLength(){return(rear-front+maxSize)%maxSize;}voidPrintOut();private:intfront,rear;T*elem;intmaxSize;};templateclassTSqQueueT::SqQueue(intsz){front=rear=0;maxSize=sz;elem=newT[maxSize];for(inti=0;imaxSize;i++)elem[i]=0;}templateclassTvoidSqQueueT::EnQueue(Titem){if(!IsFull()){rear=(rear+1)%maxSize;elem[rear]=item;}}templateclassTTSqQueueT::DeQueue(){if(!IsEmpty()){front=(front+1)%maxSize;returnelem[front];}}templateclassTTSqQueueT::GetFront(){if(!IsEmpty())returnelem[(front+1)%maxSize];}templateclassTvoidSqQueueT::PrintOut(){inti;if(!IsEmpty())cout队列已空endl;else{i=rear;while(i!=front){coutdata=elem[i];i=(i-1)%maxSize;}}西华大学数计学院学生上机实践报告第8页共10页}西华大学数计学院学生上机实践报告第9页共10页五、总结通过本次实验,我熟悉了二叉树遍历的操作,巩固了队列的顺序存储结构和栈的顺序存储结构的知识,同
本文标题:2012《数据结构》上机实验报告-二叉树遍历
链接地址:https://www.777doc.com/doc-6285049 .html