2012《数据结构》上机实验报告二叉树遍历

《2012《数据结构》上机实验报告二叉树遍历》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、西华大学数计学院学生上机实践报告西华数学与计算机学院上机实践报告课程名称：数据结构年级：2011上机实践成绩：指导教师：唐剑梅姓名：蒋俊上机实践名称：学号：312011080611118上机实践日期：2012-11-20上机实践编号：2上机实践时间：8:00-9:30一、实验目的1.熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解二叉树的按层遍历、先序非递归遍历及后序非递归遍历。2.用树解决实际问题，如哈夫曼编码等。加深对“数据结构+算法=程序”的

2、理解和认识，提高编写较复杂程序的能力。二、实验内容建立一棵二叉树，分别用“先根非递归”方法、“按层遍历”的方法遍历。三、实验环境硬件:微型计算机P4软件:WindowsXP+MicrosoftVisualC++6.0四、程序源码及调试过程#include#include"2.h"#include"3.h"typedefintElemType;structNodeType//定义结点结构体{ElemTypedata;NodeType*lch,*rch;};classBiTree//

3、定义二叉树类{public:BiTree(){root=NULL;};//构造函数~BiTree(){destroy(root);}//析构函数voidinorder()//中序遍历{inorder(root);}voidpreordertswap()//利用先序遍历方法交换左右子树{preorderswap(root);}第10页共10页西华大学数计学院学生上机实践报告inttheight()//求二叉树高度{returnheight(root);}voidcreat0();voidpreoder()

4、;//先根遍历非递归voidlevelorder();//按层遍历二叉树private:NodeType*root;//数据成员，树根NodeType*creat();//建立二叉树递归方法voidinorder(NodeType*p);//中序遍历voidpreorderswap(NodeType*p);//利用先序遍历方法交换左右子树intheight(NodeType*p);//求二叉树高度递归算法voiddestroy(NodeType*&p);//删除二叉树所有结点};voidBiTree::

5、creat0()//建立树函数，{cout<<"请按照树的先序遍历顺序组织数据"<>x;if(x==0)p=NULL;else{p=ne

6、wNodeType;p->data=x;p->lch=creat();//递归调用自身p->rch=creat();}returnp;}voidBiTree::preoder()//先根遍历非递归{NodeType*q;SqStacks;q=root;intboo=1;cout<<"先根非递归遍历"<data;s.push(q);q=q->lch;}if(s.IsEmp

7、ty())boo=0;else{q=s.pop();q=q->rch;}}while(boo);cout<lch);cout<data<<"";inorder(p->rch);}}voidBiTree::preorderswap(NodeType*p)//利用先序遍历方法交换左右子树{if(p!=NULL){NodeType*r;r=p->lch;p->lch=

8、p->rch;p->rch=r;//上面几条语句可以认为对结点的访问（交换左右孩子）//替换了原来的：cout<data<<"";语句preorderswap(p->lch);preorderswap(p->rch);}}voidBiTree::destroy(NodeType*&p)//删除二叉树所有结点{if(p!=NULL){destroy(p->lch);destroy(p->rch);deletep;p=NULL;}}in