首页 > 代码库 > 算法:由后序遍历和中序遍历求前序遍历
算法:由后序遍历和中序遍历求前序遍历
假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ,中序遍历序列为 DBGEHJACIF ,求前序遍历。
整体思路是这样的,由后序遍历找到每个节点,然后由中序遍历判断左右子树,将整个二叉树还原后写出前序遍历。
后序遍历的顺序知道,最后一个A是二叉树的根节点,
然后把中序遍历从A分成两段,A左边的是左子树,A右边的是右子树,
结果如下
然后看右边的子树,
从后序遍历知道,左子树的后序遍历为IFC,中序遍历为CIF
问题回到刚开始,重复之前的过程,由后序遍历知道根节点为C,把中序遍历从C分成两段,
左边是左子树,右边是右子树
也就是右边只有一个右子树,
然后再次重复以上过程,现在IF的后序遍历是IF,中序遍历是IF,说明
节点时F,I是F的左子树
这样,这棵二叉树的右子树就完全复原了,左子树的方法完全相同,就是一个递归过程,流程图如下
NEXT:
最后得到的完整二叉树如下:
然后写出前序遍历就可以了,是ABDEGHJCFI
用算法可以实现的,暂时留在这。
作者:jason0539
微博:http://weibo.com/2553717707
博客:http://blog.csdn.net/jason0539(转载请说明出处)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。