先序和中序创建二叉树的一段C语言代码，帮我解读一下

Question

void CreatBin1(Bintree *T,List pro,List mid)//pro先序序列,mid中序序列,
{
List midr,q;
char ch;
if(pro->next==NULL || mid->next==NULL) *T=NULL;//
else
{
*T=(Bintree)malloc(sizeof(Binnode));//
(*T)->lchild=NULL;
(*T)->rchild=NULL;
ch=pro->next->ch ;
pro->next=pro->next->next;
(*T)->data=ch;//
for(midr=mid->next,q=mid;midr->ch!=ch;q=midr,midr=midr->next);
q->next=NULL;
CreatBin1(&((*T)->lchild),pro,mid);
CreatBin1(&((*T)->rchild),pro,midr);

}
return;
}

Answer 1

示例：先序：ABECDFGHIJ，中序：EBCDAFHIGJ
找规律：
前序：ABECDFGHIJ的第1个字符为A，说明它是树的根。然后定位A在中序：EBCDAFHIGJ中的位置，A把中序分成两个子串：EBCD和FHIGJ，它们分别是A的左子树和右子树的所有结点。

前序：ABECDFGHIJ的第2个字符为B，同理它把子串EBCD分成两个子串E和CD，它们分别是以B为根的两个左、右子数。

前序：ABECDFGHIJ的第3个字符为E，它已是叶结点。因为E是个字符。左右为空串。
前序：ABECDFGHIJ的第4个字符为C，同理它把子串CD分成左空串和字符D，空串说明C没有左子结点。
前序：ABECDFGHIJ的第5个字符为D，它已是叶结点。因为D是个字符。

。。。
同理，A的右子树也能重构出来。
示例：
void createbtreeFromPreM(NODE** root,char* p,char* m,int len)
{
int llen,rlen;//llen+rlen+1=len
if(p)
*root=createnode(*p);//动态分配结点内存并初始化

int pos=0;//前序中第一个字符在中序中的位置 base 0
while(*p!=*(m+pos))
pos++;

if(pos-1>0)
{
llen=pos;
createbtreeFromPreM(&(*root)->left,p+1,m,llen);
}
if(len-pos-1>0)
{
rlen=len-pos-1;
createbtreeFromPreM(&(*root)->right,p+llen+1,m+llen+1,rlen);
}

}

void CreatBin1(Bintree **T,List pro,List mid)//pro先序序列,mid中序序列,
{
List midr,q;//midr--右子树的中序序列
char ch;
if(pro->next==NULL || mid->next==NULL) *T=NULL;//
else
{
*T=(Bintree)malloc(sizeof(Binnode));//
(*T)->lchild=NULL;
(*T)->rchild=NULL;
ch=pro->next->ch ;
pro->next=pro->next->next;//处理先序的下一个元素
(*T)->data=ch;//
//定位ch在中序中的位置
for(midr=mid->next,q=mid;midr->ch!=ch;q=midr,midr=midr->next);
q->next=NULL;//把中序分为两个子中序
CreatBin1(&((*T)->lchild),pro,mid);//构造左子树
CreatBin1(&((*T)->rchild),pro,midr);//构造右子树

}
return;
}

Answer 2

先序的第一个元素是根，由这个元素把中序分为前后两部分，前面是左子树，后面是右子树，递归建立就行

Answer 3

根据先序和中序序列可以唯一确定一个二叉树。每次都以pro（先序序列链表）里的第一个元素为根节点，再以这个元素把mid(中序序列列表)分成两部分，前部为左子树，后部分为右子树，循环该过程递归调用，你模拟一下根据先序和中序序列还原二叉树的过程就可以明白程序了。