L1-008 建立与遍历二叉树 （20 分)

以字符串的形式定义一棵二叉树的先序序列，若字符是‘#’, 表示该二叉树是空树，否则该字符是相应结点的数据元素。读入相应先序序列，建立二叉链式存储结构的二叉树，然后中序遍历该二叉树并输出结点数据。

输入格式:

字符串形式的先序序列（即结点的数据类型为单个字符）

输出格式:

中序遍历结果

输入样例:

在这里给出一组输入。例如：

ABC##DE#G##F###

输出样例:

在这里给出相应的输出。例如：

CBEGDFA

1 #include
      
        2 #include
       
         3 using namespace std; 4 char ch; 5 typedef struct BiTNode{ 6     char data; 7     struct BiTNode *lchild,*rchild; 8 }BiTNode,*BiTree; 9 //按前序输入二叉树中结点的值(一个字符)10 //#表示空树，构造二叉链表表示二叉树T11 void CreateBiTree(BiTree &T)12 {13     if(ch=='\n')14         return;15     scanf("%c",&ch);16     if(ch=='#')17         T=NULL;18     else{19         T=(BiTree)malloc(sizeof(BiTNode));20         T->data=ch;21         CreateBiTree(T->lchild);22         CreateBiTree(T->rchild);23     }24 }25 void InOrder(BiTree T)//中序遍历二叉树26 {27     if(T!=NULL){28         InOrder(T->lchild);29         printf("%c",T->data);30         InOrder(T->rchild);31     }32 }33 int main()34 {35     BiTree T;36     CreateBiTree(T);37     InOrder(T);38     return 0;//124##5##3##39 }