一、题目描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：
输入包括1行字符串，长度不超过100。

输出描述：
可能有多组测试数据，对于每组数据，输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行。

二、示例

输入：abc##de#g##f###
输出：c b e g d f a

三、实现

由先序序列ABC##DE#G##F### ：【根，左，右】
第一个为二叉树的根节点A，
然后B为A左子树的根，C为B的左子树的根，C的左右子树都为#，D为B的右子树，E为D的左子树的根，E的左子树为空，E的右子树为G，G的左右子树都为空，F为D的右子树的根，F的左右子树都为空。
A的右子树为空。

首先我们要有先序序列字符串的输入，然后根据先序序列创建一颗二叉树。

int main() {char a[100];scanf("%s", a);int i = 0;BTNode* root = CreateTree(a, &i);InOrder(root);printf("\n");return 0;
}

在CreateTree构建二叉树中，因为要对先序字符串进行遍历，所以需要传入先序序列，在构建的过程中使用递归遍历，为了保持只想先序字符串的索引一致，还需要遍历的索引i，并使用引用传递。

我们还要提供二叉树的结点定义，因为要根据字符新建结点，提供了一个创建结点的函数：

typedef int BTDataType;
typedef struct BinaryTreeNode {struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
} BTNode;BTNode* CreateNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){printf("malloc fail\n");exit(-1);}node->data = x;node->left = node->right = NULL;return node;
}

具体遍历时：
如果该字符不为#，则创建该结点，遍历指针后移，然后构建该结点的左子树，构建该结点的右子树。
如果遇到#，则返回空，并且遍历指针要后移。

BTNode* CreateTree(char* a, int* pi)
{if(a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = CreateNode(a[*pi]);(*pi)++;root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}

然后再给出中序遍历就可以了，完整代码如下：

#include <stdio.h>
#include <stdlib.h>typedef int BTDataType;
typedef struct BinaryTreeNode {struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
} BTNode;BTNode* CreateNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){printf("malloc fail\n");exit(-1);}node->data = x;node->left = node->right = NULL;return node;
}BTNode* CreateTree(char* a, int* pi)
{if(a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = CreateNode(a[*pi]);(*pi)++;root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}void InOrder(BTNode* root)
{if(root == NULL)return;InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}int main() {char a[100];scanf("%s", a);int i = 0;BTNode* root = CreateTree(a, &i);InOrder(root);printf("\n");return 0;
}