已知二叉树先序和中序遍历，生成二叉树

参考：
如先序为：abdc,中序为：bdac .
则程序可以求出后序为：dbca 。此种题型也为数据结构常考题型。
算法思想：先序遍历树的规则为中左右，则说明第一个元素必为树的根节点，比如上例
中的a就为根节点,由于中序遍历为：左中右，再根据根节点a，我们就可以知道，左子树包含
元素为：db，右子树包含元素：c，再把后序进行分解为db和c（根被消去了），然后递归的
进行左子树的求解（左子树的中序为：db，后序为：db），递归的进行右子树的求解（即右
子树的中序为：c，后序为：c）。如此递归到没有左右子树为止。
关于“已知先序和后序求中序”的思考：该问题不可解，因为对于先序和后序不能唯一的确定

中序，比如先序为 ab，后序为ba，我只能知道根节点为a，而并不能知道b是左子树还是右子树，

#include <stdio.h>

typedef struct _Node{
	char data;
	struct _Node *lchild;
	struct _Node *rchild;
} Node;

Node * CreateTree()
{   /* 生成二叉树的普通方法
     * 按先序次序输入二叉树中结点的值
     * 构造二叉链表表示的二叉树T。输入空格表示空子树。 */

    char ch;
    scanf("%c",&ch);
    Node *T;

    if(ch==' ') /* 空 */
        return NULL;
    else
    {
        T=(Node *)malloc(sizeof(Node));
        if(!T)
            exit(0);
        T->data=ch; /* 生成根结点 */
        T->lchild = CreateTree(); /* 构造左子树 */
        T->rchild = CreateTree(); /* 构造右子树 */
    }
    return T;
}
/* 由先根序列和中根序列生成二叉树
 * 递归法。pre 是先跟序列，in是中根序列
 * pre_s是先根序列的起始，pre_e是先跟序列的结束
 * in_s是中根序列的起始,in_e是中根序列的结束
 */
Node *Convert(char pre[], int pre_s, int pre_e,
              char in [], int in_s , int in_e )
{
    if(in_s > in_e)return NULL;

    int i = in_s;
    for(i=in_s;i<in_e&&in[i]!=pre[pre_s];i++);


    Node *p = (Node *)malloc(sizeof(Node));
    p->data = pre[pre_s];
    p->lchild = Convert(pre, pre_s+1, pre_s+i-in_s,
                        in,  in_s,i-1);
    p->rchild = Convert(pre, pre_s+i-in_s+1,pre_e,
                        in,  i+1,in_e);

    return p;
}
void PreTranverse(Node *head)
{
	if(!head)return ;
    printf("%c\t",head->data);
	PreTranverse(head->lchild);
	PreTranverse(head->rchild);
	return;
}
void InTranverse(Node *head)
{
	if(!head)return ;
	PreTranverse(head->lchild);
    printf("%c\t",head->data);
	PreTranverse(head->rchild);
	return;
}
void BackTranverse(Node *head)
{
    if(!head)return;
    BackTranverse(head->lchild);
    BackTranverse(head->rchild);
    printf("%c\t",head->data);
    return;
}

int main(int argc, char *argv[])
{
    char pre[]="abdc";
	char in[]="bdac";
    Node *head = NULL;

    head = Convert(pre,0,strlen(pre)-1,
                   in ,0,strlen(in)-1);
    InTranverse(head);
    printf("\n");
	getch();
}

由此可见该问题不可解。当然也可以构造符合中序要求的所有序列。