数据结构严书习题6.65已知前中序，求二叉链表
数据结构严书习题6.65已知前中序，求二叉链表
Description
已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。
Input
分两行分别输入一棵二叉树的前序序列和中序序列。
Output
输出该二叉树的后序序列。
知识点回顾：二叉树
1、二叉树的定义 二叉树是n(n≥0)个节点的有限集合，它或者是空树(n=0),或者是有一个根节点及两颗不相交的且分别称为左、右子树的二叉树所组成。可见，二叉树同样具有递归性质。
特别需要注意的是，尽管树和二叉树的概念之间有许多联系，但它们是两个不同的概念，树和二叉树之间最主要的区别是：二叉树结点的子树要区分左子树和右子树，即使在节点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。另外，二叉树结点最大度为2，二树中不限制节点的度数。
2、二叉树的性质 （1）二叉树第i层（i≥1）上至多有个节点
（2）高度为k的二叉树之多有个节点（k≥1）
（3）对于任一颗二叉树，若其终端的节点数为,度为2的节点数为，则
（4）具有n个节点的完全二叉树的深度为
3、二叉树的存储结构 1）二叉树的顺序存储结构
用一组地址连续的存储单元存储二叉树中的节点，必须把节点排成一个适当的线性序列，并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。
2）二叉树的链式存储结构
由于二叉树的节点中包含有数据元素、左子树的根、右子树的根及双亲等信息，因此可以用三叉链表或二叉链表（即一个节点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根节点。
4、二叉树的遍历 遍历二叉树的方法分别有先序遍历、中序遍历、后序遍历。
先序遍历：先遍历根节点，然后是左子树，最后是右子树；根节点->左子树->右子树
中序遍历：先遍历左子树，然后是根节点、最后是右子树；左子树->根节点->右子树
后序遍历：先遍历左子树，然后是右子树，最后是根节点；左子树->右子树->根节点
下面给出一种已知二叉树前中序，求其二叉链表的算法，递归~
前：ABDFGCEH 中：BFDGACEH 后：FGDBHECA
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 1000005
#define lb(x) (x&(-x))
const double eps = 1e-6;
using namespace std;
inline ll read()
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
typedef struct node
{
char val;
struct node*lchild,*rchild;
}Binode,*Bitree;
inline void Print(Bitree T)
{
if(T)
{
Print(T->lchild);
Print(T->rchild);
cout<<T->val<<" ";
}
else return ;
}
char pre[maxn],mid[maxn];
inline Binode* work(ll pre_b,ll pre_e,ll mid_b,ll mid_e)
{
Bitree root=(Bitree)malloc(sizeof(Binode));
root->lchild=root->rchild=NULL;
root->val=pre[pre_b];
rg i=0;
while(mid[i]!=root->val)i++;
ll llen=i-mid_b,rlen=mid_e-i;
if(llen>0)root->lchild=work(pre_b+1,pre_b+llen,mid_b,i-1);
if(rlen>0)root->rchild=work(pre_b+llen+1,pre_e,i+1,mid_e);
return root;
}
int main()
{
Bitree T=(Bitree)malloc(sizeof(Binode));
scanf("%s%s",pre,mid);
ll len=strlen(pre);
T=work(0,len-1,0,len-1);
Print(T);
return 0;
}