题目来源：严蔚敏《数据结构》C语言版本习题册 6.65

    【题目】6.65
    已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

    【答案】

    1. // 6.65 前序序列、中序序列-->二叉链表
    2. BiTNode* PreInOrderToBiTree(char *prestr, char *instr, int prestart, int preend, int instart, int inend) {
    3.     char e;
    4.     int root,leftlen,rightlen;
    5.     BiTNode *p;
    7.     e=prestr[prestart];
    8.     p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);
    9.     p->data=e;p->lchild=NULL;p->rchild=NULL;
    10.     //找到e在中序中所在的位置
    11.     for (root=instart; instr[root]!=e && root<=inend; root++);
    12.     if (root>inend) return NULL; //出错
    14.     //构建左子树
    15.     leftlen = root - instart; //左子树长度
    16.     if (leftlen) p->lchild = PreInOrderToBiTree(prestr, instr, prestart+1, prestart+leftlen, instart, instart+leftlen-1);
    17.     //构建右子树
    18.     rightlen = inend - root; //右子树长度
    19.     if (rightlen) p->rchild = PreInOrderToBiTree(prestr, instr, preend-rightlen+1, preend, inend-rightlen+1, inend);
    21.     return p;
    22. }

    【完整代码】

    /*
@Desc:二叉链表 无头结点
@Vesrion:0.0.1
@Time:20180922创建
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif

#define TElemType char //固定为char，若修改需要修改方法
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
void visit(TElemType e) {
    printf("%c", e);
}
#define SElemType BiTNode*
#include"SqStack.h"

#define maxSize 50 //本文件中 队列、栈 最大的内容


// 递归遍历
void PreOrder(BiTree T); // 先序遍历二叉树
void InOrder(BiTree T); // 中序遍历二叉树
void PostOrder(BiTree T); // 后序遍历二叉树

// 6.65 前序序列、中序序列-->二叉链表
BiTNode* PreInOrderToBiTree(char *prestr, char *instr, int prestart, int preend, int instart, int inend) {
    char e;
    int root,leftlen,rightlen;
    BiTNode *p;

    e=prestr[prestart];
    p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);
    p->data=e;p->lchild=NULL;p->rchild=NULL;
    //找到e在中序中所在的位置
    for (root=instart; instr[root]!=e && root<=inend; root++);
    if (root>inend) return NULL; //出错

    //构建左子树
    leftlen = root - instart; //左子树长度
    if (leftlen) p->lchild = PreInOrderToBiTree(prestr, instr, prestart+1, prestart+leftlen, instart, instart+leftlen-1);
    //构建右子树
    rightlen = inend - root; //右子树长度
    if (rightlen) p->rchild = PreInOrderToBiTree(prestr, instr, preend-rightlen+1, preend, inend-rightlen+1, inend);

    return p;
}

int main() {
/* 6.65
ABCDEFHIJ
CBEFDAHJI
*/
    char prestr[maxSize],instr[maxSize];
    BiTree T;
    scanf("%s", prestr);
    scanf("%s", instr);

    T = PreInOrderToBiTree(prestr, instr, 0, strlen(prestr)-1, 0, strlen(instr)-1 );
    printf("二叉链表：\n");
    PreOrder(T);printf("\n");
    InOrder(T);printf("\n");
    PostOrder(T);printf("\n");


    return 0;
}


// 先序遍历二叉树
void PreOrder(BiTree T) { // - 递归
    if (!T) return ;
    visit(T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}
// 中序遍历二叉树
void InOrder(BiTree T) { // - 递归
    if (!T) return ;
    InOrder(T->lchild);
    visit(T->data);
    InOrder(T->rchild);
}
// 后序遍历二叉树
void PostOrder(BiTree T) { // - 递归
    if (!T) return ;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T->data);
}