根据前序序列+中序序列或根据中序序列+后序序列还原二叉树

• 已知先序序列存在pre[l1...r1]中 ,中序序列存在in[l2...r2]中,二叉树的结点数据域不等,构造二叉树并求其后序遍历序列
• 已知中序序列存在in[l2...r2]中,后序序列存在post[l1...r1],二叉树的结点数据域不等,构造二叉树并求其前序遍历序列

代码以下ios

#include <iostream>
#include <stdlib.h>

typedef struct BTNode{//二叉树结点 
    char data;
    struct BTNode *lchild,*rchild;
}BTNod;


BTNode *createBT(char pre[],int l1,int r1,char in[],int l2,int r2){//由先序+中序还原二叉树 
    BTNode *s;//为二叉树的根节点 
    int i;
    if(l1>r1){
        return NULL;
    }else{
        s=(BTNode *)malloc(sizeof(BTNode));//为其分配内存空间 
        s->lchild=NULL;//初始化左右孩子指针 
        s->rchild=NULL;
        for(i=l2;i<=r2;i++){
            if(in[i]==pre[l1]){//在中序序列中找到根结点 
                break;
            }
        }
        s->data=in[i];//数据域存放的是根结点的数据 
        s->lchild=createBT(pre,l1+1,l1-l2+i,in,l2,i-1);//找到根结点后,找出左子树的序列范围 
        s->rchild=createBT(pre,l1-l2+i+1,r1,in,i+1,r2);//找出右子树的序列范围 
    }
}

BTNode *createBT2(char post[],int l1,int r1,char in[],int l2,int r2){//由后序+中序还原二叉树 
    BTNode *s;//为二叉树的根节点 
    int i;
    if(l1>r1){
        return NULL;
    }else{
        s=(BTNode *)malloc(sizeof(BTNode));
        s->lchild=NULL;
        s->rchild=NULL;
        for(i=l2;i<=r2;i++){
            if(in[i]==post[r1]){//在中序序列中找到根结点 
                break;
            }
        }
        s->data=in[i];
        s->lchild=createBT2(post,l1,l1-l2+i-1,in,l2,i-1);//找到根结点后,找出左子树的序列范围 
        s->rchild=createBT2(post,l1-l2+i,r1-1,in,i+1,r2);//找出右子树的序列范围 
    }
}

void preOrder(BTNode *p){//前序遍历 
    if(p!=NULL){
        printf("%c ",p->data);
        preOrder(p->lchild);
        preOrder(p->rchild);
    }
}

void postOrder(BTNode *p){//后序遍历 
    if(p!=NULL){
        postOrder(p->lchild);
        postOrder(p->rchild);
        printf("%c ",p->data);
    }
}
int main(int argc, char** argv) {
    BTNode *p;
    char pre[]={'a','b','d','c'};//前序遍历序列 
    char in[]={'b','d','a','c'};//中序遍历序列 
    char post[]={'d','b','c','a'};//后序遍历序列 
    int l1,r1,l2,r2;
    l1=l2=0;
    r1=r2=3;
    printf("由先序+中序肯定的二叉树的后序序列为: ") ;
    p=createBT(pre,l1,r1,in,l2,r2);
    postOrder(p);
    printf("\n");

    printf("由中序+后序肯定的二叉树的前序序列为: ") ;
    p=createBT2(post,l1,r1,in,l2,r2);
    preOrder(p);
    return 0;
}

我在上述代码中也给出了相似的已知中序+后序求二叉树的实现,但已知前序+后序不能惟一肯定一颗二叉树web