二叉查找数 golang实现

Tibbersshao · · 628 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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


image.png

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


image.png

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


image.png

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


image.png

个人认为二叉查找数最大的难点是删除一个树节点
有4种情况:
1,待删除节点的左右节点都为null,直接返回null
2,待删除节点的左节点为null,直接返回右节点
3,待删除节点的右节点为null,直接返回左节点
4,待删除节点的左右节点都不为null, 一种普遍的做法是用该节点的右节点的最小的节点来代替这个节点来保持二叉数的稳定。
手画图:


image.png

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


image.png

然后是具体的删除函数:
image.png

这是比较关键的代码:
image.png

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

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


image.png

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

参考:算法(第四版)


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:Tibbersshao

查看原文:二叉查找数 golang实现

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

628 次点击  
加入收藏 微博
上一篇:Go语言4
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传