#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 100//定义最大的节点数
//创建二叉树的类型
typedef struct TNode{
char data;//数据类型
struct TNode *left,*right;
}*BinTree;//定义指针变量
//输入字符串返回二叉链表
BinTree cearteTree(char *str){//返回的是一个二叉链表
BinTree s[M],b=NULL,p;//初始栈，初始化root指针，定义一个用来创建的指针
int top=-1,i=0,flag=1;//原始栈为空,定义标志位flag=1
while(str[i]!='\0'){//字符串遍历完成
if(str[i]!='#'){
p=(BinTree)malloc(sizeof ( struct TNode));//如果不是#申请存储空间
p->data=str[i];//为当前的数据赋值
p->left=p->right=NULL;//初始话左右指针
if(b==NULL){//判断是否有双亲节点
b=p;
}else{
switch(flag){
case 1:s[top]->left=p;break;//使双亲节点的左指针指向当前的指针
case 2:s[top]->right=p;top--;break;//使双亲节点的左指针指向当前的指针，双亲节点出战
}
}
top++;//指针后移
s[top]=p;//将当前的值入栈
flag=1;//刷新当前的flag
}else{
flag=2;//标记为右指针
if(str[i-1]=='#'){//若上一个是#代表左右都是空
top--;//指针后移
}
}
i++;//字符元素后移
}
return b;//最后返回根节点b
}
//先序遍历，底层为递归算法
void preorder(BinTree b){
if(b==NULL){
return ;
}else{
printf("%-5c",b->data);//输出对应的结果
preorder(b->left);//向左递归查找
preorder(b->right);//向右递归查找
}
}
//中序遍历，底层为递归算法
void center(BinTree b){
if(b==NULL){
return ;
}else{
preorder(b->left);//向左递归查找
printf("%-5c",b->data);//输出对应的结果
preorder(b->right);//向右递归查找
}
}
//后序遍历，底层为递归算法
void finall(BinTree b){
if(b==NULL){
return ;
}else{
preorder(b->left);//向左递归查找
preorder(b->right);//向右递归查找
printf("%-5c",b->data);//输出对应的结果
}
}
int main(){
char s[M];//定义一个最大大小的字符数组
BinTree b;//定义一个二叉树的头指针b
gets(s);//得到输入的字符串
b=cearteTree(s);//创建二叉树
preorder(b);//先序遍历
printf("\n");
center(b);//中序遍历
printf("\n");
finall(b);//后序遍历
printf("\n");
return 0;
}
