由遍历序列恢复二叉树

根据二叉树的定义，先序遍历是先访问根节点，然后再先序遍历左子树的，最后先序遍历右子树。因此，先序遍历序列中的第一个节点一定是二叉树的根节点。此外，二叉树的中序遍历是先中序遍历根节点的左子树，然后访问根节点，最后中序遍历根节点的右子树，因此，在中序遍历序列中，根节点将序列可以分成两个子序列，根节点左边的是左子树所对应的中序序列，根节点右边的是右子树所对应的中序序列；根据这两个子序列可以在先序遍历序列中找到对应的左子树和右子树，而此时的左子树序列的第一个节点就是左子树的根节点，右子树序列的第一个节点就是右子树的根节点，这样就可以确定左右子树的根节点，接下来在对左右子树的左右子树进行划分，如此递归划分下去，当取尽先序遍历的节点时，就唯一恢复了这个二叉树。
同样，由后序遍历和中序遍历同样也可以唯一的确定一个二叉树。

先序遍历，中序遍历确定二叉树

void Pre_In_Order(char pred[],char ind[],int i,int j,int k, int h,BiTNode **p){
    //i,j是前序遍历的下，上界；k,h是中序遍历的下，上界
    int m;
    *p=(BiTNode*)malloc(sizeof(BiTNode));
    (*p)->data=pred[i];
    m=k;
    while(pred[i]!=ind[m]){
        m++;
    } 
    if(m==k){
        //该节点的左子树为空
        (*p)->lchild=NULL; 
    }
    else{
        Pre_In_Order(pred,ind,i+1,i+m-k,k,m-1,&(*p)->lchild);
    }
    if(m==h){
        //右子树为空
        (*p)->rchild=NULL;
    }
    else{
        Pre_In_Order(pred,ind,i+m-k+1,j,m+1,h,&(*p)->rchild); 
    } 
} 

中序，后序确定二叉树

void Post_In_Order(char post[],char ind[],int i,int j,int k, int h,BiTNode **p){
    //i,j是后序遍历的下，上界；k,h是中序遍历的下，上界
    int m;
    *p=(BiTNode*)malloc(sizeof(BiTNode));
    (*p)->data=post[j];
    m=k;
    while(post[j]!=ind[m]){
        m++;
    } 
    if(m==k){
        //该节点的左子树为空
        (*p)->lchild=NULL; 
    }
    else{
        Post_In_Order(post,ind,i,i+m-k-1,k,m-1,&(*p)->lchild);
    }
    if(m==h){
        //右子树为空
        (*p)->rchild=NULL;
    }
    else{
        Post_In_Order(post,ind,i+m-k,j-1,m+1,h,&(*p)->rchild); 
    } 
}