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

C语言 码拜 6年前 (2015-05-11) 443次浏览 0个评论

老师给的题目 做了很久
已知到中序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协议进行授权 , 转载请注明数据结构树:只知道中序后序求树
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!