数据结构二叉树 - 副本.doc

仲恺农业工程学院实验报告纸 （院、系） 专业 班 组 课学号 姓名 实验日期 教师评定 实验三 二叉树的操作及应用一、实验目的 1、掌握二叉树的特点，以及二叉链表的结构 2、熟练掌握二叉树的各种操作，如建立、遍历、查找和输出 3、利用己经掌握的进行实际应用二、实验要求 1、 编写程序实现二叉树的各种运算，并在此基础上设计主函数，使其完成如下功能： （1）按先序建立二叉树，如“ABCDEGF”，（表示空格）。 （2）建立二叉树后，判断二叉树空否，同时输出二叉树的深度。 （3）建立二叉树后，判断二叉树空否，同时输出二叉树的结点数。 （4）建立二叉树后，判断二叉树空否，同时输出二叉树的叶子点数。 2、编写一个子函数，用非递归算法中序遍历二叉树。三、程序运算结果截图四、程序源代码#include#include#includestack.husing namespace std;/#define n 15static int num=0;static int nodenum=0;static int h=0;static int tmp=0;/typedef char ElemType;/typedef struct BItNodeElemType data; struct BItNode *lchild,*rchild;BitNode,*BitTree;/void Init(BitTree *t)(*t)=(BitTree)malloc(sizeof(BitNode); /二叉树初始化if(!t)exit(0);(*t)-lchild=(*t)-rchild=NULL;/BitTree Getlchild(BitTree t)return t-lchild; /获取左子树/BitTree Getrchild(BitTree t)return t-rchild; /获取右子树/bool Empty(BitTree t)if(t) return false; /判断是否为空else return true;/int Create(BitTree *t,ElemType a,int num)(*t)-data=anum;num+;if(anum!= &numlchild);num=Create(&(*t)-lchild),a,num); /创建二叉树num+;if(anum!= &numrchild);num=Create(&(*t)-rchild),a,num);elseh=htmp?h:tmp;tmp-;return num;/void visit(BitTree t)coutdatalchild)PreOrderTraverse(t-lchild); /递归先序遍历二叉树if(t-rchild)PreOrderTraverse(t-rchild);/void InOrderTraverse(BitTree t)if(t-lchild)InOrderTraverse(t-lchild); /递归中序遍历二叉树visit(t);if(t-rchild)InOrderTraverse(t-rchild);/void PosOrderTraverse(BitTree t)if(t-lchild)PosOrderTraverse(t-lchild); /递归后序遍历二叉树if(t-rchild)PosOrderTraverse(t-rchild);visit(t);/void nInOrderTraverse(BitTree t)BitTree tmp=t;Stack s;if(!tmp) return;dowhile(tmp!=NULL)s.Push(tmp); /非递归中序遍历二叉树tmp=Getlchild(tmp);tmp=s.Pop();visit(tmp);tmp=Getrchild(tmp);while(tmp!=NULL|s.Empty();s.Destory();/void main()ElemType an=A,B,C, , ,D,E, ,G, , ,F, , , ;cout先序创建的二叉树为(为空格):;for(int i=0;in;i+)if(ai= )cout-;elsecoutai-;coutendlendl;BitTree t;Init(&t);Create(&t,a,num);if(!Empty(t)cout二叉树的深度为 :hendl;cout二叉树的结点数为 :nodenum+1endl;cout二叉树的叶子结点数为:nodenumendl;coutendl;cout递归先序遍历二叉树 :;PreOrderTraverse(t);coutendlendl;cout递归中序遍历二叉树 :;InOrderTraverse(t);coutendlendl;cout递归后序遍历二叉树 :;PosOrderTraverse(t);coutendlendl;cout非递归中序遍历二叉树:;nInOrderTraverse(t);coutendlendl;头文件”stack.h”templateclass Stack/栈类private:int Maxsize;/栈的最大值private:T* base;/栈低private:T* top;/栈顶public: Stack();/初始化栈void Push(T p);/入栈T Pop();/出栈void Clear();/清空栈void Destory();/销毁栈int Length();/获取栈的长度bool Empty();/判断栈是否为空;templateStack:Stack():Maxsize(10)this-base=new TMaxsize;if(!this-base) exit(0);this-top=this-base;templatevoid Stack:Push(T p)if(this-top-this-base=Maxsize)this-base=new TMaxsize+10;if(!this-base) exit(0);this-top=this-base+this-Maxsize;this-Maxsize+=10;*(this-top)=p;this-top+;templateT Stack:Pop()if(this-top=this-base)return *(this-top); return *-(this-top);templatevoid Stack:Clear()this-top=this-base;templatevoid Stack:Destory()delete (this-base);this-base=this-top=NULL;this-