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

西华大学数计学院学生上机实践报告 西华数学与计算机学院上机实践报告课程名称：数据结构年级： 2011上机实践成绩：指导教师：唐剑梅姓名：蒋俊上机实践名称： 学号：312011080611118上机实践日期：2012-11-20上机实践编号：2上机实践时间：8:00-9:30一、实验目的1. 熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解二叉树的按层遍历、先序非递归遍历及后序非递归遍历。2. 用树解决实际问题，如哈夫曼编码等。加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。二、实验内容 建立一棵二叉树，分别用“先根非递归”方法、“按层遍历”的方法遍历。三、实验环境 硬件: 微型计算机P4软件: Windows XP+Microsoft Visual C+6.04、 程序源码及调试过程#include #include 2.h#include 3.htypedef int ElemType;struct NodeType /定义结点 结构体 ElemType data; NodeType *lch,*rch;class BiTree /定义 二叉树类 public: BiTree()root=NULL; /构造函数 BiTree()destroy(root) ; /析构函数 void inorder() /中序遍历 inorder(root); void preordertswap() /利用先序遍历方法交换左右子树 preorderswap(root); int theight() /求二叉树高度 return height(root); void creat0(); void preoder(); /先根遍历非递归 void levelorder(); /按层遍历二叉树 private: NodeType *root; /数据成员，树根 NodeType *creat(); /建立二叉树递归方法 void inorder(NodeType *p); /中序遍历 void preorderswap(NodeType *p); /利用先序遍历方法交换左右子树 int height(NodeType *p); /求二叉树高度递归算法 void destroy(NodeType* &p); /删除二叉树所有结点 ;void BiTree:creat0() /建立树函数， cout请按照树的先序遍历顺序组织数据endl; cout若结点信息是int，把每个结点的空孩子以0输入;endl; cout例如一个结点的二叉树11，输入：11 0 0;endl; root=creat(); /调用私有creat(); NodeType * BiTree:creat() /递归建立二叉树算法 NodeType *p; ElemType x; coutx; if( x=0) p=NULL; else p=new NodeType; p-data=x;p-lch=creat(); /递归调用自身p-rch=creat(); return p; void BiTree:preoder() /先根遍历非递归NodeType *q;SqStack s;q=root;int boo=1;cout先根非递归遍历endl;dowhile(q!=NULL)coutdata;s.push(q);q=q-lch;if(s.IsEmpty()boo=0;elseq=s.pop();q=q-rch;while(boo);coutlch); coutdatarch);void BiTree:preorderswap(NodeType *p) /利用先序遍历方法交换左右子树 if(p != NULL) NodeType *r; r=p-lch; p-lch=p-rch; p-rch=r;/上面几条语句可以认为对结点的访问（交换左右孩子）/替换了原来的： coutdatalch); preorderswap(p-rch);void BiTree:destroy(NodeType* &p) /删除二叉树所有结点if(p != NULL) destroy(p-lch);destroy(p-rch);delete p;p = NULL;int BiTree:height(NodeType *p) /求二叉树高度(递归) if(p = NULL) return 0; else int hl=height(p-lch); int hr=height(p-rch); return 1 + (hlhr?hl:hr); /1加上hl和hr的较大值 void BiTree:levelorder() /按层遍历SqQueueq;NodeType *p;p=root;if(p!=NULL) q.EnQueue(p);while(!q.IsEmpty()p=q.DeQueue();coutdatalch!=NULL) q.EnQueue(p-lch);if(p-rch!=NULL) q.EnQueue(p-rch);/-int main() int k; BiTree root0; /声明创建二叉树对象，调用构造函数 do coutnn; coutnn 1. 建立二叉树; coutnn 2. 交换左右子树; coutnn 3. 求二叉树深度; coutnn 4.先根非递归遍历; coutnn 5.按层遍历二叉树; coutnn 6. 结束程序运行; coutn=; coutk; switch(k) case 1: coutn 建立二叉树：; root0.creat0(); coutn 中根遍历结果：; root0.inorder(); break; case 2: root0.preordertswap(); coutn 交换左右子树后中根遍历结果：; root0.inorder(); break; case 3: int deep; deep=root0.theight(); coutn 树的深度是：deep; break; case 4: coutn 先根遍历的结果：; root0.preoder(); break; case 5: coutn 按层遍历二叉树的结果 ：; root0.levelorder(); break; case 6: break; cout=1 & k6);return 0;/栈的顺序存储结构，顺序栈类#include#include /-栈的顺序存储结构-/typedef int ElemType; / 数据元素的类型/const int MAXSIZE=100; / 数组的容量template class SqStack private: T *elem; int maxSize; int top; public: SqStack(int s=30); SqStack()deleteelem; void push(T item); T pop(); void PrintOut(); int IsEmpty()return top=-1; int IsFull()return top=maxSize-1;/-templateSqStack:SqStack(int s)top=-1;maxSize=s;elem=new TmaxSize;for(int i=0;imaxSize;i+)elemi=0; templatevoid SqStack:push(T item) if(!IsFull()top+;elemtop=item;templateT SqStack:pop() T x;if(!IsEmpty() x=elemtop;top-;return x;templatevoid SqStack:PrintOut() int t; if(!IsEmpty()cout栈已空endl;elsei=top;while(i!=-1)coutdata=elemi;i-;队列的顺序存储结构#includetemplateclass SqQueuepublic:SqQueue(int sz=30); SqQueue()deleteelem; void EnQueue(T item); T DeQueue(); T GetFront(); int IsEmpty()return front=rear; int IsFull()return (rear+1)%maxSize=front; int Length()return (rear-front+maxSize)%maxSize; void PrintOut();private:int front,rear;T*elem;int maxSize;templateSqQueue:SqQueue(int sz)front=rear=0;maxSize=sz;elem=new TmaxSize;for(int i=0;imaxSize;i+)elemi=0;templatevoid SqQueue:EnQueue(T item)if(!IsFull()rear=(rear+1)%maxSize;elemrear=item;templateT SqQueue:DeQueue()if(!IsEmpty()front=(front+1)%maxSize;return elemfront;templateT SqQueue:GetFront()if(!IsEmpty()return elem(front+1)%maxSize;templatevoid SqQueue:PrintOu