二叉树的建立及遍历.doc

文档介绍：数据结构实验五课程 数据结构 实验名称  二叉树的建立及遍历   第   页专业        班级       学号       姓名    实验日期:  年 月 日              评分         一、。,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二、。。。   三、,构造一棵二叉树,采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。,并采用先序遍历的非递归算法对此二叉树进行遍历。四、实验步骤(描述实验步骤及中间的结果或现象。在实验中做了什么事情,怎么做的,发生的现象和中间结果)第一题#include""#include""#include""#include""#include<stack>usingnamespacestd;#defineNULL0#defineOK1#defineOVERFLOW-1typedefintStatus;typedefstructnode{chardata;structnode*lchild;structnode*rchild;}*bitree;intk=0;intdepth(bitreeT)//树的高度{if(!T)return0;else{intm=depth(T->lchild);intn=depth(T->rchild);return(m>n?m:n)+1;}}//先序,中序建树structnode*create(char*pre,char*ord,intn){structnode*T;intm;T=NULL;if(n<=0){returnNULL;}else{m=0;T=new(structnode);T->data=*pre;T->lchild=T->rchild=NULL;while(ord[m]!=*pre)m++;T->lchild=create(pre+1,ord,m);T->rchild=create(pre+m+1,ord+m+1,n-m-1);returnT;}}//中序递归遍历voidinorder(structnode*T){if(!T)return;else{inorder(T->lchild);cout<<T->data;inorder(T->rchild);}}voidinpre(structnode*T){if(!T)return;else{cout<<T->data;inpre(T->lchild);inpre(T->rchild);}}voidpostorder(structnode*T){if(!T)return;else{postorder(T->lchild);postorder(T->rchild);cout<<T->data;}}//先序非递归遍历voidinpre1(structnode*T){structnode*p;structnode*stack[20];inttop=0;p=T;cout<<"非递归先序";while(p||top!=0){while(p){stack[top++]=p;cout<<p->data;p=p->lchild;}p=stack[--top];p=p->rchild;}}//中序非递归遍历voidinorder1(structnode*T){