数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

再看二分搜索树的遍历

虽然这三种遍历方式在程序的实现上是非常容易的,可是我们有没有办法能够快速的写出前中后序遍历的结果呢?这一小节最后我们介绍一个简单的方法。

二分搜索树的遍历

对于二分搜索树来说,我们都把它看成这样一种递归结构,也就是对于每一个节点都连接着左子树和右子树。

具体遍历的时候,我们对每一个节点都有三次的访问机会,分别是在遍历它的左子树之前我们会访问一下这个节点,然后才能遍历它的左子树,在遍历完左子树之后我们会回到这个节点,之后才会去遍历它的右子树,在遍历完右子树之后,又来到这个节点,所以对于每一个节点使用递归遍历这种方式会访问三次。

下图中,我们对二分搜索树前中后这三种遍历其实就对应于这个节点的这三个紫色的点。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

可以结合代码跟这个图比较一下,这三个紫色的点对应代码的这三个位置,可以用一个具体的例子来看一下设置了这三个点之后为什么可以帮助我们更快速的不通过程序直接找到一个二分搜素树前中后序遍历的结果。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

对于这个二分搜索树每一个节点都相应绘制出了这三个点,对于叶子节点来说也有这三个点,只不过叶子节点的左右子树都是空子树,也是满足这样一个关系的。基于这种情况下来看一下二分搜素树的前序遍历。

二分搜索树的前序遍历

首先从28出发,来到28,对于前序遍历来说就访问了28,右侧是遍历的结果,接下来访问28的左子树16,继续访问16的左子树13,13的左子树为空,就会第二次访问13,右孩子也为空,第三次访问13,由于第一次访问已经做了操作,后两次访问不做任何操作。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

接下来又回到了16这里,之前已经访问过16了,紧接着访问16的右子树,来到22,对其进行操作,和之前的节点一样,进行第二次和第三次访问,然后又回到16这个节点。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

然后回到28的中间这一点,不做任何事情,然后看28的右子树,第一次来到30,访问了30,然后看30的左子树,同理,以此类推……

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

真正对节点进行的操作是图中蓝色的点,具体顺序也非常简单,对每个节点先看左,再看右,依次类推,这就是二分搜索树的前序遍历。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

二分搜索树的中序遍历

第一次访问28,由于是中序遍历,什么都不干,继续访问16,也什么都不敢,再访问13,也不做操作,然后第二次访问13的时候才进行中序遍历真正的操作,这里我们拿到了13,第三次访问13的时候什么都不做。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

之后回到了16,第二次访问16,满足中序遍历中间那次,对16进行操作,之后看16的右子树22。
数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

同理,依次类推,完成中序遍历。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

如图,蓝色的点就是我们进行操作的点。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

二分搜索树的后序遍历

从28根节点出发,第一次访问28什么都不做,再看28左子树,什么都不做,同理再看13,第二次看到13也什么都不做,第三次访问13,这里是后序遍历,对13进行操作,之后回到13的父节点16,也什么都不做,再看16的右子树……

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

同理,依次类推,完成后续遍历。

数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历

这一小节我们讲二分搜索树都是基于递归方法的,下一小节我们将学习对于前序遍历的非递归的写法。

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历
分享到:
赞(0)

评论抢沙发

评论前必须登录!