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

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的左孩子节点。看了终于会了

文章评论已关闭！