二叉排序树

概念:

如果一个二叉树有如下性质:

1.如果他有左子树,那么他的左子树的值都比根节点的值小。

2.如果他有右子树,那么他的右子树的节点值都比根节点的值大。

3.左子树和右子树也有同样的特性1,2.

4.理论上是没有重复值的。


代码实现:

二叉排序树的插入,查询遍历,都比较简单。但是删除极其复杂。

二叉排序树的node节点定义,data,leftnode,rightnode,parentnode。

删除一个节点分为4中情况。

1.需要删除的节点是叶子节点。


叶子节点或根节点

2.需要删除的节点只有左子树。


7是父节点的左孩子,是父节点的右孩子

3.需要删除的节点只有右子树。

4.需要删除的节点,左右子树都纯在。

4.1)待删除节点的右子树,没有左子树。直接将右子树替换当前的删除点

4.2

最复杂的情况,
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容