二叉查找数 golang实现

栏目: Go · 发布时间: 6年前

内容简介:首先定义数据结构,这个不用多说,这里添加了一个size,这样就可以在o(1)的时间复杂度内获取这个二叉树的大小。首先要写的是添加节点(put)接口:通过和当前节点的key比较,如果相等就更新val,如果小于就遍历左节点,反之则遍历右节点。如果没有找到就创建一个新节点:

首先定义数据结构,这个不用多说,这里添加了一个size,这样就可以在o(1)的时间复杂度内获取这个二叉树的大小。

二叉查找数 golang实现

image.png

首先要写的是添加节点(put)接口:通过和当前节点的key比较,如果相等就更新val,如果小于就遍历左节点,反之则遍历右节点。

二叉查找数 golang实现

image.png

如果没有找到就创建一个新节点:

二叉查找数 golang实现

image.png

然后是 get接口,这个接口也比较简单,和put类似,左右遍历即可:

二叉查找数 golang实现

image.png

个人认为二叉查找数最大的难点是删除一个树节点

有4种情况:

1,待删除节点的左右节点都为null,直接返回null

2,待删除节点的左节点为null,直接返回右节点

3,待删除节点的右节点为null,直接返回左节点

4,待删除节点的左右节点都不为null, 一种普遍的做法是用该节点的右节点的最小的节点来代替这个节点来保持二叉数的稳定。

手画图:

二叉查找数 golang实现

image.png

具体代码如下

先写出删除该树的最小节点和找到这个树的最小节点。这两个函数相对比较简单

二叉查找数 golang实现

image.png

然后是具体的删除函数:

二叉查找数 golang实现

image.png

这是比较关键的代码:

二叉查找数 golang实现

image.png

先获取待删除节点的右节点的最小节点,使新节点的右节点等于原节点的有节点删除最小节点后的值(即删除获取到的新节点),左节点就等于原节点的左节点。

用中序遍历验证函数的正确性:

二叉查找数 golang实现

image.png

代码写的不好或者有bug的地方,欢迎各位大佬来拍砖。

参考:算法(第四版)


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

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

PWA实战

PWA实战

[美]Dean Alan Hume / 郑丰彧 / 电子工业出版社 / 2018-6 / 69

Progressive Web App(PWA)是由谷歌提出的一整套技术解决方案,它致力于为 Web 提供出色的用户体验,并完美体现了渐进增强原则。作为为数不多的实战入门用书,《PWA 实战:面向下一代的Progressive Web App》旨在通过大量清晰示例来介绍 PWA 的主要特性。全书一共由五个部分组成:第一部分介绍 PWA 的概念及解锁 PWA 应用的关键—Service Worker......一起来看看 《PWA实战》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具