手机搭建网站教程视频教程阜新网站seo
数据结构实验之二叉树二：遍历二叉树
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。
Input
连续输入多组数据，每组数据输入一个长度小于50个字符的字符串。
Output
每组输入数据对应输出2行：
第1行输出中序遍历序列；
第2行输出后序遍历序列。
Sample Input
abc,,de,g,,f,,,
Sample Output
cbegdfa cgefdba
#include <stdio.h>
#include <stdlib.h>
struct node
{int data;struct node *Lchild, *Rchild;
};char a[100];
int t;
struct node *Creat();
void Inorder_Traversal(struct node *);
void Postorder_Traversal(struct node *);
int main()
{struct node *root;while(~scanf("%s", a)){t = 0;root = Creat();Inorder_Traversal(root);printf("\n");Postorder_Traversal(root);printf("\n");}return 0;
}
struct node *Creat()
{struct node *root;char c;c = a[t++];if(c == ',') return NULL;else{root = (struct node *)malloc(sizeof(struct node));root->data = c;root->Lchild = Creat();root->Rchild = Creat();}return root;
}
void Inorder_Traversal(struct node *root)
{if(root){Inorder_Traversal(root->Lchild);printf("%c", root->data);Inorder_Traversal(root->Rchild);}
}
void Postorder_Traversal(struct node *root)
{if(root){Postorder_Traversal(root->Lchild);Postorder_Traversal(root->Rchild);printf("%c", root->data);}
}