首页 > 数据库技术 > 详细

已知二叉树的中序序列为DBGEAFC,后序序列为DGEBFCA,给出相应的二叉树

时间:2017-06-17 10:56:03      阅读:285      评论:0      收藏:0      [点我收藏+]

面对这种问题时我们该怎么解决?

今天写数据结构题。发现了一道总是碰见问题的题在这里我写了一种求解方法我自己称它为分层递归求解。

第一步通过观察我们知道后序遍历时最后一个是根节点A

在中序序列中A的左边是左子树右边是右子树

第二步我们来画第一层为根节点的右子树为A-C-F

技术分享

第三步拆分左子树

在中序序列中为DBGE(由于我们不知道左子树中的树结构无法直接看出来就把左子树另外拆分出来看)在后序序列中为DGEB

第五步模仿第一步和第二步的做法来画

这个时候我们能够得到左子树的结构例如以下:

技术分享

已知二叉树的中序序列为DBGEAFC,后序序列为DGEBFCA,给出相应的二叉树

原文:http://www.cnblogs.com/gccbuaa/p/7039568.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!