数据结构实验之二叉树二:遍历二叉树

2/10/2017来源:ASP.NET技巧人气:850

PRoblem Description

已知二叉树的一个按先序遍历输入的字符序列,如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。 Input

连续输入多组数据,每组数据输入一个长度小于50个字符的字符串。 Output

每组输入数据对应输出2行: 第1行输出中序遍历序列; 第2行输出后序遍历序列。

Example Input

abc,,de,g,,f,,,

Example Output

cbegdfa cgefdba

Hint

Author xam

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; typedef struct node { char a; node *left; node *right; }Node; int top=0; struct node *creat(char *p)//建树方法 { Node *root=NULL; if(top<strlen(p)) { if(p[top]!=',') { root=(Node *)malloc(sizeof(Node)); root->left=NULL; root->right=NULL; root->a=p[top++]; root->left=creat(p); root->right=creat(p); } else { top++; } } return root; } void zhong(Node *root)//中序遍历,先序和后序类似 { if(root) { zhong(root->left); printf("%c", root->a); zhong(root->right); } } void hou(Node *root) { if(root) { hou(root->left); hou(root->right); printf("%c", root->a); } } int main() { char p[60]; while(~scanf("%s", p)) { Node *root; top=0; root = creat(p); zhong(root); printf("\n"); hou(root); printf("\n"); } }