二叉树

华北电力大学科技学院实验报告实验名称二叉树课程名称数据结构专业班级：学生姓名：学号：成绩：指导老师：张琦实验日期：2012年5月28日实验三二叉树一、实验目的及要求1、实验目的(1)通过实验，掌握二叉树的建立与存储(2)通过实验，掌握二叉树的遍历方法2、实验要求(1)二叉树需要用二叉链表作为节点类型描述。(2)二叉树的遍历递归算法能够转换为非递归算法。(3)编写完整程序完成下面的实验内容并上机运行。(4)整理并上交实验报告。二、实验内容1、问题描述利用先序遍历建立一棵二叉树，并分别用前序、中序、后序遍历该二叉树2、节点形式LchilddataRchild3、说明(1)输入数据：1，2，3，0，0，4，0，0，5，0，0其中“0”表示空子树。(2)输出数据：先序：1，2，3，4，5中序：3，2，4，1，5后序：3，4，2，5，1三、实验步骤1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。2.建立二叉树,并通过调用函数,输出先序遍历、中序遍历与后序遍历的结果。实现提示：二叉链表的类型定义如下：typedefstructbtnode{intdata;structbtnode*Lchild,*Rchild;}*bitreptr四、实验源代码#includeiostream#includemalloc.husingnamespacestd;#includestdlib.h#includemath.htypedefstructTNode//定义二叉树{intdata;TNode*lchild,*rchild;}TNode,*BTree;intNil=0;voidInitBTree(BTree&T)//定义一个空树{T=NULL;}voidCreateBTree(BTree&T)//建立一个树{intnumber;cinnumber;if(number==Nil)//结点的值为空T=NULL;else//结点的值不为空{T=(BTree)malloc(sizeof(TNode));//生成根结点if(!T)exit(OVERFLOW);T-data=number;//将值赋给T所指结点CreateBTree(T-lchild);//递归构造左子树CreateBTree(T-rchild);//递归构造右子树}}voidDestroyBTree(BTree&T){if(T)//非空树{DestroyBTree(T-lchild);//递归销毁左子树，如无左子树，则不执行任何操作DestroyBTree(T-rchild);//递归销毁右子树，如无右子树，则不执行任何操作free(T);//释放根结点T=NULL;//空指针赋0}}voidPreOrderTraverse(BTreeT){if(T)//T不空{coutT-data;//先访问根结点PreOrderTraverse(T-lchild);//再先序遍历左子树PreOrderTraverse(T-rchild);//最后先序遍历右子树}}voidPreOrderTraverse1(BTreeT)//非递归先序遍历{if(T==NULL)return;else{BTreep;//定义一个动态节点p=T;//T为根节点inttop=0;BTrees[100];//建立栈，总长度为100while(p!=NULL||top!=0){while(p!=NULL){coutp-data;if(p-rchild!=NULL){top++;s[top]=p-rchild;}p=p-lchild;}if(top!=0){p=s[top];top--;}}}}voidInOrderTraverse(BTreeT)//递归中序遍历{if(T){InOrderTraverse(T-lchild);//先中序遍历左子树coutT-data;//再访问根结点InOrderTraverse(T-rchild);//最后中序遍历右子树}}voidInOrderTraverse1(BTreeT)//非递归中序遍历{if(T==NULL)return;else{BTreep;p=T;inttop=0;BTrees[100];while(p!=NULL||top!=0){while(p!=NULL){top++;s[top]=p;p=p-lchild;}if(p==NULL){p=s[top];top--;coutp-data;p=p-rchild;}}}}voidPostOrderTraverse(BTreeT){if(T)//T不空{PostOrderTraverse(T-lchild);//先后序遍历左子树PostOrderTraverse(T-rchild);//再后序遍历右子树coutT-data;//最后访问根结点}}voidPostOrderTraverse1(BTreeT)//非递归后续遍历{if(T==NULL)return;else{BTreep;p=T;inttop=0;BTrees[100];inta[100];//栈的标志位while(p!=NULL||top!=0){while(p!=NULL){top++;s[top]=p;a[top]=1;p=p-lchild;}while((top!=0)&&(p==NULL)){p=s[top];top--;if(a[top+1]0){top++;a[top]=-1;s[top]=p;p=p-rchild;}else{coutp-data;p=NULL;}}}}}voidmain(){BTreeT;InitBTree(T);//初始化二叉树Tcout按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1240050030600endl;CreateBTree(T);//建立二叉树Tcoutendl;cout先序递归遍历二叉树：endl;PreOrderTraverse(T);//先序递归遍历二叉树Tcoutendl;cout先序非递归遍历二叉树：endl;PreOrderTraverse1(T);//先序非递归遍历二叉树Tcoutendl;cout中序递归遍历二叉树：endl;InOrderTraverse(T);//中序递归遍历二叉树Tcoutendl;cout中序非递归遍历二叉树：endl;InOrderTraverse1(T);//中序非递归遍历二叉树Tcoutendl;cout后序递归遍历二叉树：endl;PostOrderTraverse(T);//后序递归遍历二叉树Tcoutendl;cout后序非递归遍历二叉树：endl;PostOrderTraverse1(T);//后序非递归遍历二叉树Tcoutendl;}五、实验输出结果