数据结构实验之二叉树二:遍历二叉树
Time Limit: 1000MS Memory Limit: 65536KB
Problem Description
已知二叉树的一个按先序遍历输入的字符序列,如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。
Input
连续输入多组数据,每组数据输入一个长度小于50个字符的字符串。
Output
每组输入数据对应输出2行:
第1行输出中序遍历序列;
第2行输出后序遍历序列。
Example Input
abc,,de,g,,f,,,
Example Output
cbegdfacgefdba
Hint
Author
xam
#include <stdio.h>
#include <string.h>
struct node
{char data;struct node *l,*r;
};
int l1;
char a[55];
struct node *creat()
{struct node *root;char ch;ch = a[l1++];if(ch == ',')return NULL;else{root = (struct node *)malloc(sizeof(struct node));root->data = ch;root->l = creat();root->r = creat();}return root;
}
void zhong(struct node *t)
{if(t == NULL)return ;if(t!=NULL){zhong(t->l);printf("%c",t->data);zhong(t->r);}
}
void hou(struct node *t)
{if(t == NULL)return ;if(t!=NULL){hou(t->l);hou(t->r);printf("%c",t->data);}
}
int main()
{while(scanf("%s",a) != EOF){struct node *root;l1 = 0;root = creat();zhong(root);printf("\n");hou(root);printf("\n");}return 0;
}