二叉查找树(二叉排序树)

左子树上所有结点的数据域均小于或等于根结点的数据域,右子树上所有结点的数据域均大于根结点的数据域


查找操作:

由于无法确定二叉树的具体特性,因此只能对左右子树都进行递归遍历。但是二叉查找树的性质决定了读者可以只选择其中一棵子树进行遍历。


和普通二叉树的查找函数不同,二叉查找树的查找在于左右子树的选择递归。在普通二叉树中,无法确定需要查找的值x到底是在左子树还是右子树,但是在二叉查找树中就可以确定,因为二叉查找树中的数据域顺序总是左子树<根结点<右子树



插入操作:



二叉查找树的建立:












下面两个函数用来寻找以root为根的树中最大或最小权值的结点,而且可以用这两个函数来辅助寻找结点的前驱和后继:



以删除权值为5和6的结点为例解读下面的代码

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容