#include<stdio.h>
#include<malloc.h>
typedef struct st{
char data;
struct st *r;
struct st *l;
}*link,ll;
char s[20]="ABC##DE##F##G##";//二叉树序列
int i=0;
void create_tree(link &tree)//先序递归建树
{
if(s[i]=='#')
tree=NULL,i++;
else
{
tree=(link)malloc(sizeof(ll));
tree->data=s[i],i++;
create_tree(tree->l);
create_tree(tree->r);
}
}
void in_1(link tree)//递归中序遍历
{
if(tree)
{
in_1(tree->l);
printf("%c ",tree->data);
in_1(tree->r);
}
}
void in_2(link tree)//非递归中序遍历
{
link s[20];//储存指针结点
int top =-1;
link p = tree;
while(p!=NULL||top!=-1){
if(p!=NULL){
s[++ top] = p;
p = p->l;
}else{
p = s[top --];
printf("%c ",p->data); //出栈时,访问输出
p = p->r;
}
}
}
int main()
{
link T=NULL;
create_tree(T);//建树
printf("递归中序遍历\n");
in_1(T);//递归中序遍历
printf("\n非递归中序遍历\n");
in_2(T);//非递归中序遍历
return 0;
}