二叉排序树查找效率_什么是二叉查找树，有什么优势？
对于顺序存储，不需要维护有序性，但查询效率低；
而有序存储，查询效率高，但由于插入删除需要维护有序性，因此效率低。
本文要介绍的二叉查找树(也叫二叉搜索树、二叉排序树、ADT树)结合了二者的优势，不仅查询效率高，插入和删除效率也高。
二叉查找树(空树也是二叉查找树)的定义：
若左子树不为空，则左子树所有结点的值小于根结点
若左子树不为空，则左子树所有结点的值小于根结点
左右子树也是二叉查找树
构建一颗二叉查找树的目的，不是为了排序，而是为了提高查询、插入、删除关键字的速度。不管怎么说，有序数据结构的查找速度总是要大于无序数据结构的。
二叉查找树有三个操作：
查找结点
插入结点
删除结点
本文主要实现二叉查找树的查找操作。
首先，我的代码有6个类,如下图所示。
ADTBuilder：可以直接返回构建好的二叉树样本
ADTMain：main方法所在类，提供二叉查找树各种操作的示例程序
ADTDelete：二叉查找树的删除操作
ADTInsert：二叉查找树的插入操作
ADTNode：二叉查找树结点类
ADTSearch：二叉查找树的查找操作
二叉查找树的查找
假设所有结点中没有相同的两个值，因为二叉查找树是对关键字的排序，而关键字可以理解为唯一。退一万步来讲，就算有两条数据关键字相同，也可以将它们存储于一个结点中，即结点可以设置四个字段：
key
List
左孩子指针
右孩子指针
回归主题，首先什么是二叉排序树的查找呢？
给定一颗二叉排序树和要查找的关键字，返回关键字对应结点的指针。
查找的思路是什么呢？如何利用二叉查找树的特性进行查找？
根据二叉查找树的性质，二叉查找树的中序遍历结果是从小到大有序的。
假设要查找的二叉排序树如下图所示。
由于代码篇幅原因太长，我没有将完整代码粘贴到文章中，如果就需要的话请访问我的码云git仓库，附上地址：https://gitee.com/bobo_tea/datastructure。或者点击底部菜单->资源汇总->仓库汇总。
下面重点介绍一下ADTSearch类。
示例程序
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/91166.html
