前序、中序、后续构造二叉树?

栏目: 数据库 · 发布时间: 5年前

内容简介:前面分享了《每种遍历输出的就是一个序列。如果只给我们一个序列,我们是没办法反唯一的向构造出一个二叉树的。比如前序序列

一、背景

前面分享了《 二叉树就是这么简单 》,里面提到二叉树有三种遍历方式:前序遍历、中序遍历、后序遍历。

每种遍历输出的就是一个序列。如果只给我们一个序列,我们是没办法反唯一的向构造出一个二叉树的。

比如前序序列 [3,9,20,15,7] ,我们可以确定 3 是根,但是之后的就不知道哪个属于左子树,哪个属于右子树。

但是给我们一个中序序列和后序序列,我们就可以唯一的构造出一个二叉树了。

二、中序与后序

假设中序和后序的数据如下:

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

前序、中序、后续构造二叉树?

这里假设我们实现了一个函数,传入两个中序序列和后序序列,我们可以返回对应的二叉树。

第一步:根据后序序列最后一个位置,我们可以确定根是 postorder[4]=3

然后在中序序列中,查找到根的位置是 inorder[1]=3

第二步:根据中序序列根的位置,我们可以得到左子树的中序序列 [9] 和右子树的中序序列 [15,20,7]

接着,我们也可以根据两个子树的序列长度,得到左子树的后序序列 [9] 和右子树的后序序列 15,7,20

第三步:递归函数自身,分别得到左子树和右子树。

前序、中序、后续构造二叉树?

注意事项:这里有个特殊处理:如果序列为空,则返回空二叉树。

三、最后

对于中序和前序,其实是类似的方法,作为思考题留给大家吧。

另外再附加一道思考题:前序和后序能得到二叉树吗?为什么?

-EOF-


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

黑客大曝光

黑客大曝光

Joel Scambray、Vincent Liu、Caleb Sima / 姚军 / 机械工业出版社华章公司 / 2011-10 / 65.00元

在网络技术和电子商务飞速发展的今天,Web应用安全面临着前所未有的挑战。所有安全技术人员有必要掌握当今黑客们的武器和思维过程,保护Web应用免遭恶意攻击。本书由美国公认的安全专家和精神领袖打造,对上一版做了完全的更新,覆盖新的网络渗透方法和对策,介绍如何增强验证和授权、弥补Firefox和IE中的漏洞、加强对注入攻击的防御以及加固Web 2.0安全,还介绍了如何将安全技术整合在Web开发以及更广泛......一起来看看 《黑客大曝光》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具