1340【例3-5】扩展二叉树

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1340

【题目描述】
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。
这里写图片描述
现给出扩展二叉树的先序序列，要求输出其中序和后序序列。

【输入】
扩展二叉树的先序序列。

【输出】
输出其中序和后序序列。

【输入样例】
ABD..EF..G..C..
【输出样例】
DBFEGAC
DFGEBCA

【题目大意】
输入一串字符，表示树的先序序列，输出这棵树的中序序列和后序序列。
【思路】
一开始第一思路是遇到‘.’时，说明这个结点时叶节点或者它只有左孩子或者右孩子，但是发现，
只有左孩子时右孩子不要确定到底是哪个点，那怎么办呢？于是我自己手写了一下过程！大概是这
样的（以样例为例子）

箭头的指向表示这是自己的父亲，后来苦思冥想发现这样也很难实现，那就直接用数组来记录自己的孩

子和父亲吧，（好像父亲记录下来也没用）大概就是这样

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1005;
 4 struct node{
 5     char date;
 6     int lc,rc;
 7 }tree[N];
 8 int id=1;
 9 //建树 
10 void build(int root){
11     char c;
12     cin>>c;
13     if(c!='.'){
14         tree[root].date=c;//给根赋值 
15         tree[root].lc=++id;//给左儿子赋值 
16         build(tree[root].lc);//进入左儿子（左子树) 
17         tree[root].rc=++id;//给右儿子赋值 
18         build(tree[root].rc);//进入右儿子（右子树） 
19     }
20     else{
21         tree[root].date='.';//便于后面输出时判断
22     }
23 }
24 //中序遍历 
25 void zxprint(int root){
26     if(tree[root].date!='.'){
27         zxprint(tree[root].lc);//1.先访问左儿子 
28         cout<<tree[root].date;// 2.访问根并输出根的值 
29         zxprint(tree[root].rc);//3.访问右儿子 
30     }
31 } 
32 //后序遍历
33 void hxprint(int root){
34     if(tree[root].date!='.'){ 
35         hxprint(tree[root].lc);//1.先访问左儿子
36         hxprint(tree[root].rc);//2.访问右儿子 
37         cout<<tree[root].date;//3.访问根并输出根的值
38     }
39 }
40 //测试
41 void pr(){
42     for(int i=1;i<=15;i++){
43         cout<<i<<" "<<tree[i].date<<" "<<tree[i].lc<<" "<<tree[i].rc<<endl;
44     }
45 } 
46 int main(){
47     build(1);
48 //  pr();
49     zxprint(1);
50     cout<<endl;
51     
52     hxprint(1);
53     return 0;
54 }