内容简介：首先定义数据结构，这个不用多说，这里添加了一个size，这样就可以在o(1)的时间复杂度内获取这个二叉树的大小。首先要写的是添加节点（put）接口：通过和当前节点的key比较，如果相等就更新val，如果小于就遍历左节点，反之则遍历右节点。如果没有找到就创建一个新节点：
首先定义数据结构，这个不用多说，这里添加了一个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的地方，欢迎各位大佬来拍砖。
参考：算法（第四版）
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- 数据结构和算法(Golang实现)(27)查找算法-二叉查找树
- Java实现二分查找算法
- 二维数组中的查找如何实现？看图！
- JavaScript实现简单二叉查找树
- 【PHP 实现数据结构】二叉查找树
- 如何用 Go 编码实现查找 DNS 记录
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
淘宝、天猫网上开店速查速用一本通
刘珂 / 北京时代华文书局 / 2015-6 / 39.8
为了帮助众多的新手卖家掌握淘宝天猫网上开店、货源准备、店铺装修、商品拍摄、交易方法、营销推广以及售后服务等知识，本书作者根据自己多年网上开店心得，并结合了多名淘宝五皇冠店主和天猫旗舰店卖家的经验，精心策划编写了本书。 《淘宝、天猫网上开店速查速用一本通：开店、装修、运营、推广完全攻略》将目前最前沿、最流行的营销理念运用到淘宝天猫网上平台，所有技术都在实际应用获得显著效果，并且还在持续创造着惊......一起来看看 《淘宝、天猫网上开店速查速用一本通》 这本书的介绍吧!
