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

原创 lronelove 随笔 浅谈数据结构 101阅读 2019-02-23 15:48:29 举报

数据结构----二叉树及二叉树排序这篇文章里面,简要介绍了一下什么是二叉树,以及二叉树的一些基本特性。并尝试去实现了二叉树的添加节点的append方法,以及在利用二叉树来进行排序。
当然,二叉树还有很多属性和方法,本文介绍一些比较基础的属性和方法

1. append方法

数据结构----二叉树及二叉树排序对append方法有详细的介绍,这里不再重复,直接上代码:

上述代码,依次添加了key值为20,16,90,50,100,15,17的节点,构造了一个基本的二叉树,我们在此基础上探寻它的属性和方法。
打印的结果如图1:

形成的二叉树结构如图2:

2. 遍历二叉树

我们现在有了图2这样的一个二叉树,那么我们如何遍历二叉树里面的每一个节点呢?
我们可以从根节点20开始,打印自己的key值,然后分别去找自己的left节点和right节点,即找16和90,这样依次向下,我们不就可以遍历整个二叉树了么。
遍历代码如下:

完整代码如下:

打印结果如图3:

其实我们发现遍历的时候,我们顺便把这个数组从小到大排序了,大家也可以试试改变walk()里面打印的位置,看看有什么结果。

3. 查找

我们想去在二叉树里面,查找某个关键字为key的节点。
如果不存在,那么返回null,如果存在返回这个节点(假设二叉树里面关键字各个关键字不一样)。
思路:我们从根节点开始,比较节点current的key值和要查找的节点node的key值,如果相同,那么就直接返回这个节点。如果不相同,那么我比较current节点和node节点的key值大小,如果current节点比node节点大,那么就用current.left来和node节点比较;如果current节点比node节点小,那么就用current.right节点和node节点来比较。
查找函数search(node, key)代码如下:

完整代码如下:

打印结果如下:

4. 迭代版本的查找

上面的查找方式效率不太高,因而有了迭代版本的查找,思路其实差不多,都是通过从根节点开始对比key值,依次往下去找。
具体代码如下:

完整的代码如下:

打印结果如下:

本文介绍了二叉树的4个方法,还有一些方法没有介绍,比如查找二叉树的最小值、最大值(最小值和最大值的查找很简单,大家可以看看有没有想法)、后继、删除。
后面会依次介绍这些方法和属性,谢谢🙏

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

赶紧努力消灭 0 回复