【题目描述】

由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。

现给出扩展二叉树的先序序列，要求输出其中序和后序序列。

【输入】

扩展二叉树的先序序列。

【输出】

输出其中序和后序序列。

【输入样例】

ABD..EF..G..C..

【输出样例】

DBFEGAC
DFGEBCA

#include<iostream>
#include<cstring>
using namespace std;
typedef struct node;//声明结构体的创建，按顺序
typedef node *tree;
struct node{
    char data;
    tree Lchild,Rchild;
};
tree bt;//创建这棵树的起始指针
int wz=-1;//字符串定位
string str;
void build(tree &xtree){//取 xtree 节点地址
    if(str[++wz]!='.'){
        xtree=new node;//为 xtree 开辟 新节点
         xtree->data=str[wz];
        build(xtree->Lchild);
        build(xtree->Rchild);
    }else xtree=NULL;
}
void Zhong(tree bt){
    if(bt){
        Zhong(bt->Lchild);
        cout<<bt->data;
        Zhong(bt->Rchild);
    }
}
void Hou(tree bt){
    if(bt){
        Hou(bt->Lchild);
        Hou(bt->Rchild);
        cout<<bt->data;
    }
}
int main(){
    cin>>str;
    build(bt);
    Zhong(bt);
    cout<<endl;
    Hou(bt);
    return 0;
}//ok 教程案例
/* ABD..EF..G..C..   */