专栏首页孙小白已知两种遍历序列求原始二叉树

已知两种遍历序列求原始二叉树

注意事项:

  1. 只有通过先序和中序 或者 中序和后序,可以还原出原始的二叉树(确定一个二叉树)

  2. 已知先后中序的任意一个序列 或者 先序和后序,都不能还原出原始的二叉树

    已知先序和中序,求后序:

思路:

先序里面,最先出现的是根节点,所以A就是根节点

中序里面,根节点A在中间,所以A的左边BDCE是左子树,A的右边FHG是右子树

先序里面,A的左子树B最先出现,所以B是左子树的根节点

中序里面,根节点B的左边没有结点,所以B的左子树为空,即DCE是B的右子树

先序里面,B的右子树C最先出现,所以C是右子树的根节点

中序里面,D在C的左边,E在C的右边,所以D是C的左子树,E是C的右子树

至此,A的左子树还原完毕

先序里面,A的右子树F最先出现,所以F是根节点

中序里面,根节点F的左边没有结点,所以F的左子树为空,即HG是F的右子树

先序里面,F的右子树G最先出现,所以G是根节点

中序里面,根节点G的左边有结点H,所以H是G的左子树

至此,A的二叉树还原完毕

即原始二叉树的后序为:D-E-C-B-H-G-F-A

    已知中序和后序,求先序:

后序里面,最后出现的是根节点,所以A是根节点

中序里面,根节点A在中间,所以A的左边BDCE是左子树,A的右边FHG是右子树

后序里面,A的左子树B最后出现,所以B是左子树的根节点

中序里面,根节点B的左边没有结点,所以B的左子树为空,B的右子树是DCE

后序里面,B的右子树C最后出现,所以C是根节点

中序里面,根节点C的左边是E,所以E是C的左子树,C的右边是E,所以E是C的右子树

至此A的左子树还原完毕

后序里面,A的右子树F最后出现,所以F是根节点

中序里面,根节点F左边没有结点,所以F的左子树为空,F的右子树为HG

后序里面,F的右子树G最后出现,所以G是根节点

中序里面,G的左子树为H,G的右边没有结点,所以G的右子树为空

至此,A的二叉树还原完毕

所以先序为:A-B-C-D-E-F-G-H

通过这两个例子不难发现,已知先序和中序或者中序和后序,进行还原二叉树时需要不断交替观察结点在先序、中序或者中序、后序里的位置,结合先序遍历、中序遍历、后序遍历的特点,根据先序和后序能确定根节点,根据中序能判断左右子树的结点,这样便能还原出原始的二叉树。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 树的定义以及相关专业术语

    双亲结点或父节点(parent):若一个节点含有子节点,则这个节点称为其子节点的父节点

    爱学习的孙小白
  • 链表的定义、确定一个链表需要几个参数?

        N个节点离散分配 彼此通过指针相连 每个节点只有一个前驱节点,每个节点只有一个后驱节点。 首节点没有前驱节点,尾节点没有后续节点

    爱学习的孙小白
  • NameNode是如何存储元数据的?

    edits文件的产生: NN在启动之后,每次接受的写操作请求,都会将写命令记录到edits文件中,edits文件每间隔一定的时间和大小滚动!

    爱学习的孙小白
  • JavaScript 数组练习题之实现

    ** 题 3:改变传入的数组,将数组中第 n(从 0 开始算 ) 个元素放到数组的开头 **

    Joel
  • fireeyee解剖新型Android恶意软件

    总结 你是否下载安装过体积很大但是UI或者功能很少的Android应用程序?最近,FireEye实验室移动安全研究人员发现了一种新型的手机恶意软件,在看起来普通...

    FB客服
  • 业务驱动的互联网公司是什么样的?能学到些什么?

    明天就是周一了,打起精神,准备战斗。 先说结论,“如何选择,都是基于自身的情况,没有绝对的正确”。如果你正在寻找你的第一份工作,且手里只有一份offer,那么你...

    web前端教室
  • 两种编程高手

    第一种工程师 给一段复杂的程序,比如有7个局部变量,5层循环和if嵌套,他能赤手空拳上阵,迅速领会程序意图、找到bug,不用借助任何工具甚至纸笔。 给一个复杂的...

    企鹅号小编
  • 从0到1搭建spark集群---企业集群搭建

    今天分享一篇从0到1搭建Spark集群的步骤,企业中大家亦可以参照次集群搭建自己的Spark集群。

    LhWorld哥陪你聊算法
  • SwiftUI:集成 Core Image

    就像Core Data是Apple处理数据的内置框架一样,Core Image 是Apple处理图像的框架。这不是绘画,或者至少在大多数情况下不是绘画,而是关于...

    韦弦zhy
  • ArrayAdapter简单使用

    Adapter是Data和View之间的桥梁,一般用在ListView中。 代码:MainActivity import android.app.Activi...

    苦咖啡

扫码关注云+社区

领取腾讯云代金券