一文看懂数据结构中的树 值得收藏

假设以这种顺序插入结点: 50, 76, 21, 4, 32, 100, 64, 52。50会是我们初始的根结点。

再依次进行如下操作：

76 大于50，置于右边21 小于 50, 置于左边4 置于21左边

最终一气呵成我们会得到下面这棵树：

发现规律了么?像开车一样，从根结点驶入，待插入值大于当前结点值向右开否则向左开知道找到空位停车入库。(嘀嘀嘀，老司机)

代码实现也很简单：

这个算法最牛逼的地方在于他的递归部分，你知道是哪几行吗?

结点检索

其实结合我们的插入操作，检索的方法就显而易见，依旧从根结点开始，小于对应结点值左转，大于右转，等于报告找到，走到叶子结点都没找到 gg，就报没有该元素。例如我们想知道下图中有没有52这个值：

代码如下：

删除: 移除并重构

删除操作要更复杂一些，因为要处理三种不同情况：

情景 #1：叶子结点

是最简单的情况，直接删除就好.

情景 #2：只有左孩子或右孩子

该情景等价于链表上的结点删除，把当前结点删除并让其子结点替换自己原来位置。

情景 #3：同时具有左右孩子的结点

找到该结点右子树中最小值所在的结点，剔除要删除的当前结点并把最小值结点提升到空缺位置。

一些别的操作

清零：将三个属性全部置None即可。

找到最小值：从根节点开始，一直左转，直到找不到任何结点为止，此时我们就找到了最小值。

恭喜你学完本篇内容!数据结构中的树的内容大致如此，赶紧收藏起来吧

（编辑：西安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!