#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define NULL 0
#define OVERFOLOW 0
typedef char TElemType;
typedef int Status;
typedef struct node
{ TElemType data;
struct node *lchild,*rchild;
}Bitree;
Bitree *Q[MAX];
/*层次建立二叉树*/
Bitree *CREATE()
{char ch;
int front,rear;
Bitree *root,*s;
root=NULL;
front=1;rear=0;
ch=getchar();
while(ch!='#')
{s=NULL;
if(ch!='@')
{
s=malloc(sizeof(Bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1) root=s;
else
{if(s&&Q[front])
if(rear%2==0) Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1) front++;
}
ch=getchar();
}
return root;
}
/*非递归中序遍历*/
void inorder1(Bitree *T)
{
Bitree *p;
Bitree *stack[20];
int top=0;
p=T;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%2c",p->data);
p=p->rchild ;
}
}
main()
{
Bitree *T=NULL;
T=CREATE();
printf("the order is: \n");
inorder1(T);
getch();
}
/*换了书上的层次输入二叉树 本来用中序递归 可是太麻烦 用到了指针的指针 一时搞不清楚是什么东西了 输出还有点问题不知道为什么 麻烦大家帮我看看 测试输入a回车b回车c回车#回车 即可发现输出不是一个直线 不知道为什么*/