二叉树的建立及遍历.doc

文档介绍：数据结构实验五
课程数据结构实验名称二叉树的建立及遍历第页
专业班级学号
姓名
实验日期: 年月日评分
一、实验目的
。
,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
二、实验要求
。
。
。
三、实验内容
,构造一棵二叉树,采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。
2 .编写程序生成下面所示的二叉树,并采用先序遍历的非递归算法对此二叉树进行遍历。

四、实验步骤
(描述实验步骤及中间的结果或现象。在实验中做了什么事情,怎么做的,发生的现象和中间结果)
第一题
#include ""
#include""
#include""
#include""
#include<stack>
using namespace std;
#define NULL 0
#define OK 1
#define OVERFLOW -1
typedef int Status;
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}*bitree;
int k=0;
int depth(bitree T)//树的高度
{
if(!T)return 0;
else
{
int m=depth(T->lchild);
int n=depth(T->rchild);
return (m>n?m:n)+1;
}
}
//先序,中序建树
struct node *create(char *pre,char *ord,int n)
{
struct node * T;
int m;
T=NULL;
if(n<=0)
{
return NULL;
}
else
{
m=0;
T=new(struct node);
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);
return T;
}
}
//中序递归遍历
void inorder(struct node *T)
{
if(!T)
return;
else
{
inorder(T->lchild );
cout<<T->data;
inorder(T->rchild );
}
}
void inpre(struct node *T)
{
if(!T)
return;
else
{
cout<<