已知二叉树中序，前序（或后序 -求后序（或前序

向右看齐 2022-07-12 07:11 130阅读 0赞

已知前序，中序的遍历的 求后序

node *print_postOrder(int len,char *a,char *b)
    {
        int i;
        char x = a[0];
        if(len<=0)//递归的结束条件
            return NULL;
        node *root;
        root = (node *)malloc(sizeof(struct node));
        root->data = x;//一定别忘了把根的数据赋值过去，要不然根什么都毛了
        for(i=0; i<len; i++){
            if(b[i]==x)//寻找在中序里根的位置下标
                break;
         root->l = print_postOrder(i,a+1,b);//左子树的长度，左子树在先序中开始的地方，左子树在中序中开始的地方
        root->r = print_postOrder(len-i-1,a+i+1,b+i+1);//右子树的长度，右子树在先序中开始的地方，右子树在中序中开始的地方printf("%c",root->data);
    }

老样子，一开始我还以为懂了，没想到到应用的时候老错，看来还是没吃透，要赶快找人帮忙啊

已知后序，中序的遍历的 求前序

void *print_postOrder(int len,char *in,char *post)
    {
        if(len<=0)
            return NULL;
        int i;
        char x = post[len-1];
        node *root;
        root = (node *)malloc(sizeof(struct node));
        root->data = x;
        for(i=0; i<len; i++){
            if(in[i]==x)
                break;
        }
        printf("%c",root->data);
        root->l = print_postOrder(i,in,post);
        root->r = print_postOrder(len-i-1,in+i+1,post+i);
    }

这问题无非就求两种情况，他奶奶的，要不干脆背模板算了  
反正求前序就是

root->l = print_postOrder(i,in,post);
        root->r = print_postOrder(len-i-1,in+i+1,post+i);

后序就是

root->l = print_postOrder(i,a+1,b);
        //左子树的长度，左子树在先序中开始的地方，左子树在中序中开始的地方
        root->r = print_postOrder(len-i-1,a+i+1,b+i+1);
        //右子树的长度，右子树在先序中开始的地方，右子树在中序中开始的地方