315二叉树扩展先序遍历转中序遍历

题目：二叉树扩展先序遍历转中序遍历

问题描述

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

输入格式

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

输出格式

        输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行。

样例输入

        abc##de#g##f###

样例输出

        c b e g d f a

样例说明

根据给定的扩展先序遍历序列，建立对应的二叉树，然后对所得的二叉树进行中序遍历输出结果即可。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef struct treenode
 5 {
 6     char data;
 7     struct treenode *lchild;
 8     struct treenode *rchild;
 9 }treenode,*tree;
10 
11 tree createTree();
12 void inordertraverse(tree t);
13 int main()
14 {
15     tree t;
16     
17     t=createTree();
18     inordertraverse(t);
19     
20     return 0;
21 }
22 tree createTree()
23 {
24     treenode *p;
25     char ch;
26     ch=getchar();
27     
28     p=(treenode *)malloc(sizeof(treenode));
29     if(ch=='#') p=NULL;//这里本来是return NULL很不舒服
30     else
31     {
32         p->data=ch;
33         p->lchild=createTree();
34         p->rchild=createTree();
35     }
36     return p;//只return一个
37 }
38 
39 void inordertraverse(tree t)
40 {
41     if(t)
42     {
43         inordertraverse(t->lchild);
44         printf("%c ",t->data);
45         inordertraverse(t->rchild);
46     }
47 }

主要是create函数