数据结构----二叉树属性方法浅说(二)

在上一篇文章数据结构----二叉树属性方法浅说(一)里面介绍了二叉树的添加节点append方法、遍历walk方法以及两个查找方法search和iterativeSearch。

在这篇文章里面,介绍一下二叉树相对更简单的一些方法,比如查找最小值,最大值以及后继。

  1. 查找二叉树的最小值节点
    其实根据二叉树左子节点比父节点小的这一个特性,我们可以从根节点开始遍历,一直寻找当前节点的left,直到某个节点的left为空,那么这个节点不就是我们想找的最小值么?
    核心代码如下:

其实比较简单明了。
完整代码如下:

可以看到打印的结果如下图:

成功超找到最小节点15

2.超找二叉树的最大值节点
这个的思路和超找最小值的思路差不多,从根节点开始,一直查找当前节点的right值,直到某个节点的right值为空,那么这个节点就是最大值的节点。
思路和代码都很简单,我就不写出来了,大家感兴趣可以试一试。

3.超找某个节点的后继
首先我们了解下什么是后继,一个节点的后继是比该节点大的最小节点。
比如,有一组数:20, 16, 90, 50, 100, 15, 17
20的后继:1. 比20大,有90,50,100三个数 2.在90,50,100里面最小。所以20的后继就是50。

现在对后继有了基本的了解,然后我们看看找后继的思路。
我们有这样结构的一个二叉树:

分两种情况:

1.该节点node存在右子树,那么它的后继就是该右子树下面的最小值。

分析一下,首先后继节点肯定不在node的左子树里面,因为node的左子树里面的值都比node的值要小,对吧?
那么,当node节点有右子树的时候,会不会出现在node的祖宗节点(父亲节点,叔叔节点等)里面?
假设存在,假设20的后继是21在祖宗节点里面,那么当有90这个节点插入的时候,因为后继是比20大的最小的节点,所以90一定在21的右子树下面,同理50,100都在21的右子树下面,所以节点20没有右子树,与事实相矛盾。
所以,该节点node存在右子树,那么它的后继就一定在该右子树的里面的最小值。

2. 该节点没有右子树,那么后继一定在祖宗节点里面

这个有了之前的结论之后,就简单明了很多了。
首先,后继不可能在左子树,而且右子树不存在,所以肯定在祖宗节点里面。
那么这么多祖宗,哪一个才是该节点的后继呢?
假设该节点是其父节点的右节点,说明该节点比父节点大,那肯定不行。如果该节点是其父节点的左节点,说明该节点比父节点小。那么我们往上找,当该节点是父节点的左节点的时候,那么此父节点就是后继。

弄清楚了大概的思路之后,代码就好写了一点:
核心代码如下:

完整代码如下:

打印结果如下:

我们查找了20的后继,是50。

本文介绍了如何查找二叉树的最小值,最大值,以及后继。
后面会介绍比较难的一个方法,删除节点。
谢谢

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复