由中序序列和后序序列建立一颗二叉树，出了问题

a372187663

//已知中序序列和后序序列，建立一颗二叉树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 11

typedef char ElemType;

ElemType pmid[N] = {'D','C','B','G','E','A','H','F','I','J','K'}; //中序序列
ElemType post[N] = {'D','C','E','G','B','F','H','K','J','I','A'}; //后序序列

typedef struct BiTNode
{
        char data;
        struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

int FindPos(char x,char pmid[],int start) //从start处开始查找
{
        int i,j;
        for(i = start;i >= 0;i--)
        {
                if(x == pmid[i])
                {
                        printf("第%d次找到%c,i = %d\n",11-i,pmid[i],i);
                        return i; //返回中序根节点位置
                }
                else
                {
                        printf("第%d次查找不到%c,i = %d\n",11-i,x,i);
                }
        }

        return 0;
}

void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标，j为post[]中的尾字符下标，len为子树字符串长度
{
        int m;
        int leftlen,rightlen;
        if(len <= 0)
        {
                (*T) = NULL;
        }
        else
        {
                (*T) = (BiTree)malloc(sizeof(BiTree));
                (*T)->data = post[j];
                m = FindPos(post[j],pmid,j); // 小于m的是左孩子，大于m的是右孩子
                leftlen = m - i; //以m为根，左孩子的长度
                rightlen = len - leftlen -1;//以m为根，右孩子的长度
               
                CreatBiTree_pmid_post(&(*T)->lchild,i,j-1-leftlen,leftlen);
                CreatBiTree_pmid_post(&(*T)->rchild,m+1,j-1,len-leftlen-1);
        }
}

void visit(char c)
{
        printf("%c", c);
}

void PreOrderTraverse(BiTree T)
{
        if( T )
        {
                visit(T->data);
                PreOrderTraverse(T->lchild);
                PreOrderTraverse(T->rchild);
        }
}

int main()
{
        BiTree T = NULL;
        int  i,j,s;
        printf("中序序列为:\n");
        for(i = 0;i<N;i++)
        {
                printf("%c",pmid[i]);
        }
        printf("\n");
        printf("后序序列为：\n");
        for(j = 0;j<N;j++)
        {
                printf("%c",post[j]);
        }
        printf("\n");
        s = strlen(pmid);
        CreatBiTree_pmid_post(&T,0,N-1,s);
        printf("创建后前序遍历为：   ");
        PreOrderTraverse(T);
       
        return 0;
}

递归建立左子树时没错，因为我的是 i--查找根结点，从后往前找，但是建立右子树时，后序序列中的E要与中序序列的E相匹配，但是 i=2时，i--找不到中序序列中的E,我觉得是递归右子树时出了问题，但我有点想不明白，希望有人能帮我解释完善代码。中序序列为：DCBGEAHFIJK
     后序序列为： DCEGBFHKJIA

二叉树

鱼币少了望海涵- -。。

a372187663

//已知中序序列和后序序列，建立一颗二叉树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 11

typedef char ElemType;

ElemType pmid[N] = {'D','C','B','G','E','A','H','F','I','J','K'}; //中序序列
ElemType post[N] = {'D','C','E','G','B','F','H','K','J','I','A'}; //后序序列

typedef struct BiTNode
{
        char data;
        struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

int FindPos(char x,char pmid[]) //从start处开始查找
{
        int i;
        for(i = 11;i >= 0;i--)
        {
                if(x == pmid[i])
                {  
                            return i; //返回中序根节点位置
                }

        }

        return 0;
}

void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标，j为post[]中的尾字符下标，len为子树字符串长度
{
        int m;
        int leftlen,rightlen;
        if(len <= 0)
        {
                (*T) = NULL;
        }
        else
        {
                (*T) = (BiTree)malloc(sizeof(BiTree));
                (*T)->data = post[j];
                m = FindPos(post[j],pmid);// 小于m的是左孩子，大于m的是右孩子
                printf("根节点位于第%d个字符，元素为%c\n",m+1,pmid[m]);
                    leftlen = m - i; //以m为根，左孩子的长度
                rightlen = len - leftlen -1;//以m为根，右孩子的长度
               
                CreatBiTree_pmid_post(&(*T)->lchild,i,j-1-rightlen,leftlen);
                CreatBiTree_pmid_post(&(*T)->rchild,m+1,j-1,rightlen);
        }
}

void exchange(BiTree T)
{
        BiTree p;
        if(T)
        {
                p = T->lchild;
                T->lchild = T->rchild;
                T->rchild = p;
                exchange(T->lchild);
                exchange(T->rchild);
        }
}

void visit(char c)
{
        printf("%c", c);
}

void PreOrderTraverse(BiTree T)
{
        if( T )
        {
                visit(T->data);
                PreOrderTraverse(T->lchild);
                PreOrderTraverse(T->rchild);
        }
}

int main()
{
        BiTree T = NULL;
      int  i,j,s;
      printf("中序序列为:\n");
      for(i = 0;i<N;i++)
      {
              printf("%c",pmid);
      }
      printf("\n");
      printf("后序序列为：\n");
      for(j = 0;j<N;j++)
      {
              printf("%c",post[j]);
      }
      printf("\n");
      s = strlen(pmid);
      CreatBiTree_pmid_post(&T,0,N-1,s);
      printf("创建后前序遍历为:\n");
      PreOrderTraverse(T);
      printf("\n");

        exchange(T);
        printf("交换后前序遍历为:\n");
        PreOrderTraverse(T);;
        printf("\n");

      return 0;
}

自己改出来了

秦晓彬

表示小宝路过，看不大懂，呵呵