Code Bye

数据结构树：只知道中序后序求树

码拜
c语言

老师给的题目 做了很久
已知到中序D I G J L K B A E C H F
后序 I L K J G D B E H F C A
求这棵树。
求解过程
http://www.baidu.com/s?wd=中序，后序，%20求树&ie=utf-8

后序最后是A，所以A是根，在中序中以A为界分成两半，后半部分是ECHF，在后序中A之前是C，所以A的右子树以C为根，而中序是ECHF，所以C的左子树只有一个节点E，后序中C前面是F，所以C的右子树以F为根，中序为HF，所以H是F的左孩子节点。中序中A的前半部分也是同样道理分析即可。
其实我知道右边，我是分析不出左边
5分 
struct btree{
    btree * left, *right;
    char c;
};

btree *build(const char *post,const char *lastpost,
             const char *in,  const char *lastin)
{
    assert(lastpost-post==lastin-in);
    if(post==lastpost) return NULL;
    btree *rt =(btree *)malloc(sizeof(*rt));
    rt->c =lastpost[-1];
    const char *p=strchr(in,rt->c);
    const char *mid =p-in+post;
    rt->left =build(post,mid,in,p);
    rt->right=build(mid,lastpost-1,p+1,lastin);
    return rt;
}

int main()
{
    const char *in    ="DIGJLKBAECHF";
    const char *post  ="ILKJGDBEHFCA";
    int len=strlen(post);
    btree *root =build(post,post+len,in,in+len);

    return 0;
}
35分
引用 3 楼 pjw694438869c 的回复:

其实我知道右边，我是分析不出左边

左边也是一个道理啊。
后序I L K J G D B E H F C A，分析完A的右子树（E H F C A）之后，接下来后序最后一个就是B，那B自然就是A的左孩子节点了，B之前是D，所以D肯定是B的孩子，在中序中D在B左边，所以D是B的左孩子节点，后序中D前面是G，中序G又在D右边，所以G是D的右孩子节点，后序中G前面是J，中序中J在G右边，所以J是G的右孩子，中序中I在G左边，所以I是G的左孩子节点，后序中J前面是K，中序中K在J右边，所以K是J的右孩子节点，后序中K前面是L，中序中L在K左边，所以L是K的左孩子节点。
引用 4 楼 fly_dragon_fly 的回复: 
struct btree{
    btree * left, *right;
    char c;
};

btree *build(const char *post,const char *lastpost,
             const char *in,  const char *lastin)
{
    assert(lastpost-post==lastin-in);
    if(post==lastpost) return NULL;
    btree *rt =(btree *)malloc(sizeof(*rt));
    rt->c =lastpost[-1];
    const char *p=strchr(in,rt->c);
    const char *mid =p-in+post;
    rt->left =build(post,mid,in,p);
    rt->right=build(mid,lastpost-1,p+1,lastin);
    return rt;
}

int main()
{
    const char *in    ="DIGJLKBAECHF";
    const char *post  ="ILKJGDBEHFCA";
    int len=strlen(post);
    btree *root =build(post,post+len,in,in+len);

    return 0;
}

谢谢
引用 5 楼 wangzuxi 的回复:
Quote: 引用 3 楼 pjw694438869c 的回复:

其实我知道右边，我是分析不出左边

左边也是一个道理啊。
后序I L K J G D B E H F C A，分析完A的右子树（E H F C A）之后，接下来后序最后一个就是B，那B自然就是A的左孩子节点了，B之前是D，所以D肯定是B的孩子，在中序中D在B左边，所以D是B的左孩子节点，后序中D前面是G，中序G又在D右边，所以G是D的右孩子节点，后序中G前面是J，中序中J在G右边，所以J是G的右孩子，中序中I在G左边，所以I是G的左孩子节点，后序中J前面是K，中序中K在J右边，所以K是J的右孩子节点，后序中K前面是L，中序中L在K左边，所以L是K的左孩子节点。

看了 终于会了
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明数据结构树：只知道中序后序求树！