【图解算法思维】1-7 二叉查找树-机器人-热点资讯-野望文存-科技 
    欢迎来到野望文存-科技!
当前位置:野望文存-科技 > 热点资讯 > 机器人 >  【图解算法思维】1-7 二叉查找树

【图解算法思维】1-7 二叉查找树

发表时间:2020-02-21 23:16:00  来源:野望文存  浏览:次   【】【】【



点击上方蓝字关注我们

有意思的机器人、编程课程,Scratch、EV3、Wedo、Python不定。

本公众号中分享的课程并非完全原创,如果有参考其他老师或者书刊的部分,会在文末列出。


二叉查找树

二叉查找树,又叫二叉搜索树或二叉排序树,是一种数据结构,采用了树形结构,数据存储于二叉查找树的各个结点中。


01


这就是二叉查找树的示例。结点中的数字便是存储的数据。此处以不存在相同数字为前提进行说明。


TIPS:每个结点最多有两个子结点。


02


二叉查找树有两个性质。第一个是每个结点的值均大于其左侧子树上的任意一个结点的值。


比如结点9大于其左侧子树上的3和8.


03


同样,结点15也大于其左侧子树上任意一个结点的值。


04


第二个是每个结点的值均小于其右侧子树上任意一个结点的值。


比如结点15小于其右侧子树上的23、17和28。


05


根据这两个性质可以得到以下结论:


首先,二叉查找树的最小结点要从顶端开始,向左下的末端寻找。此处最小值为3。


06


反之,二叉查找树的最大结点要从顶端开始,向右下的末端寻找。此处最大值为28。


07


下面我们来试着往二叉查找树中添加数据。比如添加数字1。


08


首先从二叉查找树的顶端结点开始寻找添加数字的位置。


将想要添加的数字1该结点中的值进行比较,小于它则左移,大于它则右移。


由于1<15所以将其往左移。


09


由于1<9,所以将1往左移。


10


由于1<3,所以继续将1往左移,但前面已经没有结点了,所以把1作为新结点添加到左下方。


11


这样,1的添加操作就完成了。


12


接下来,我们再试试添加数字4。


13


和前面的步骤一样,首先从二叉查找树的顶端结点开始寻找添加数字的位置。


由于4<15,所以将其往左移。


14


由于4<9,所以将其往左移。


15


由于4>3,所以将其往右移。


16


由于4<8,所以将其往左移,但前面已经没有结点了,所以把4作为新的结点添加到左下方。


17


于是4的添加操作也完成了。


18


接下来看看如何在二叉查找树中删除结点。比如我们来试试删除结点28。


19


如果需要删除的结点没有子结点,直接删掉该结点即可。


20


再试试删除结点8。


21


如果需要删除的结点只有一个子结点,那么先删除目标结点。


22


然后把子结点移到被删除结点的位置上即可。


23


最后来试试删除结点9。


24


如果需要删除的结点有两个子结点,那么先删除目标结点。


25


然后在被删除结点的左侧子树中寻找最大结点。


26


最后将最大结点移到被删除结点的位置上。这样一来,就能满足在二叉查找树性质的前提下删除结点了。


27


下面来看看如何在二叉查找树中查找结点。


比如我们来试试查找12。


28


从二叉查找树的顶端结点开始往下查找。和添加数据时一样,把12和结点中的值进行比较,小于该结点的值则往左移,反之则往右移。


由于12<15,所以将其往左移。


29


由于12>4,所以将其往右移。


30


找到结点12了。



TIPS


我们可以把二叉查找树看作是二分查找法思想的树形结构体现。因为它具有前面提到的那两个性质,所以在查找数据或寻找适合添加数据的位置时,只要将其和现有的数据比较大小,就可以根据比较结果得知该往哪儿移动了。




声明:本文中使用的图片来源于APP “算法动画图解”,侵删。


Sky 的机器人教室



微信号 : sky_robotroom

● 扫码关注我们






责任编辑:蔡学森