#include<stdio.h>
#include<malloc.h>
typedef struct bttree
{char data;
struct bttree *l_child;
struct bttree *r_child;
}bttree;

//创建二叉链表存储的二叉树
bttree* createbttree()
{char c;
bttree *bt;
c=getchar();
if(c=='#')
bt=NULL;
else
{bt=(bttree *)malloc(sizeof(bttree));
bt->data=c;
bt->l_child=createbttree();
bt->r_child=createbttree();
}
return bt;
}

//先序遍历二叉树
void Preorder(bttree* bt)
{if(bt!=NULL)
{printf("%c",bt->data);
Preorder(bt->l_child);
Preorder(bt->r_child);
}
}

//后序遍历二叉树
void Postorder(bttree* bt)
{if(bt!=NULL)
{Postorder(bt->l_child);
Postorder(bt->r_child);
printf("%c",bt->data);
}
}

//中序遍历二叉树
void Inorder(bttree* bt)
{if(bt!=NULL)
{Inorder(bt->l_child);
printf("%c",bt->data);
Inorder(bt->r_child);
}
}

void main()
{bttree *bt;
    printf("请按先序序列输入二叉树中的元素，空格用#表示：\n");
        bt=createbttree();
    printf("先序遍历的结果为：\n");
   Preorder( bt);
   printf("\n");
   printf("中序遍历的结果为：\n");
Inorder( bt);
printf("\n");
printf("后序遍历的结果为：\n");
Postorder(bt);
printf("\n");
}




#include<stdio.h>
#include<malloc.h>
typedef struct bttree
{char data;
struct bttree *l_child;
struct bttree *r_child;
}bttree;
typedef struct
{char elem[50];
int top;
}Stack;
//创建二叉链表存储的二叉树
bttree* createbttree()
{char c;
bttree *bt;
c=getchar();
if(c=='#')
bt=NULL;
else
{bt=(bttree *)malloc(sizeof(bttree));
bt->data=c;
bt->l_child=createbttree();
bt->r_child=createbttree();
}
return bt;
}


//中序遍历二叉树的非递归函数
void Inorder(bttree* bt)
{Stack s;
bttree* p;
s.top=-1;
p=bt;
while(p!=NULL||s.top !=-1)
{
if(p!=NULL)
{s.top++;
s.elem [s.top]=p->data;
p=p->l_child;
}
else
{p->data=s.elem [s.top];
s.top --;
printf("%c",p->data);
p=p->r_child;

}
}
}

//先序遍历二叉树的非递归函数

void Preorder(bttree* bt)
{Stack s;
bttree* p;
s.top=-1;
p=bt;
while(p!=NULL||s.top !=-1)
{
if(p!=NULL)
{printf("%c",p->data);
    s.top++;
s.elem [s.top]=p->data;
p=p->l_child;
}
else
{p->data =s.elem [s.top];
s.top --;
p=p->r_child;

}
}
}
//后序遍历二叉树的非递归函数
void Postorder(bttree* bt)
{Stack s;
bttree* p,*q;
bttree** S;
s.top=-1;
p=bt;
q=NULL;
S=(bttree**)malloc(sizeof(bttree*)*2);
while(p!=NULL||s.top !=-1)
{
while(p!=NULL)
{    s.top++;
s.elem [s.top]=p->data;
p=p->l_child;
}
if(s.top>-1)
{p->data=s.elem [s.top];
if(p->r_child ==NULL||p->r_child ==q)
{printf("%c",p->data);
q=p;
    s.top --;
p=NULL;
}
else
p=p->r_child;

}
}
free(S);
}


void main()
{bttree *bt;
    printf("请按先序序列输入二叉树中的元素，空格用#表示：\n");
        bt=createbttree();
printf("先序遍历的结果为：\n");
   Preorder(bt);
   printf("\n");
   printf("中序遍历的结果为：\n");
Inorder( bt);
printf("\n");
printf("后序遍历的结果为：\n");
Postorder(bt);
printf("\n");
}