本文共 2013 字，大约阅读时间需要 6 分钟。

引言

原文链接： 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

1、二叉查找树的定义

对于顺序存储，不需要维护有序性，但查询效率低；

而有序存储，查询效率高，但由于插入删除需要维护有序性，因此效率低。

本文要介绍的二叉查找树（也叫二叉搜索树、二叉排序树、ADT树）结合了二者的优势，不仅查询效率高，插入和删除效率也高。

二叉查找树（空树也是二叉查找树）的定义：

• 若左子树不为空，则左子树所有结点的值小于根结点

• 若左子树不为空，则左子树所有结点的值小于根结点

• 左右子树也是二叉查找树

构建一颗二叉查找树的目的，不是为了排序，而是为了提高查询、插入、删除关键字的速度。不管怎么说，有序数据结构的查找速度总是要大于无序数据结构的。

二叉查找树有三个操作：

• 查找结点

• 插入结点

• 删除结点

本文主要实现二叉查找树的查找操作。

首先，我的代码有6个类,如下图所示。

• ADTBuilder：可以直接返回构建好的二叉树样本

• ADTMain：main方法所在类，提供二叉查找树各种操作的示例程序

• ADTDelete：二叉查找树的删除操作

• ADTInsert：二叉查找树的插入操作

• ADTNode：二叉查找树结点类

• ADTSearch：二叉查找树的查找操作

2、二叉查找树的查找

假设所有结点中没有相同的两个值，因为二叉查找树是对关键字的排序，而关键字可以理解为唯一。退一万步来讲，就算有两条数据关键字相同，也可以将它们存储于一个结点中，即结点可以设置四个字段：

• key

• List<Data>

• 左孩子指针

• 右孩子指针

回归主题，首先什么是二叉排序树的查找呢？

• 给定一颗二叉排序树和要查找的关键字，返回关键字对应结点的指针。

查找的思路是什么呢？如何利用二叉查找树的特性进行查找？

• 根据二叉查找树的性质，二叉查找树的中序遍历结果是从小到大有序的。

假设要查找的二叉排序树如下图所示。

由于代码篇幅原因太长，我没有将完整代码粘贴到文章中，如果就需要的话请访问我的码云git仓库获取，附上地址：。或者点击公众号底部菜单->资源汇总->仓库汇总。

下面重点介绍一下ADTSearch类。

/** * 二叉查找树结点搜索操作类 */public class ADTSearch {    /**     * 递归搜索     */    private ADTNode search(ADTNode adtNode,int key){        //如果要搜索的二叉查找树是null，则返回null        if(adtNode == null){            return null;        }        //证明找到了，返回这个结点        if(adtNode.getVal() == key){            return adtNode;        }        //比较一下，如果小于，则递归往左边搜索        if(key < adtNode.getVal()){            return search(adtNode.getLeft(),key);        }        //比较一下，如果大于，则递归往右边搜索        if(key > adtNode.getVal()){            return search(adtNode.getRight(),key);        }        return null;    }    /**     * 搜索操作入口     * @param root 从该结点开始搜素     * @param key 要搜索的值     * @return 搜索到的结点     */    public ADTNode searchEntrance(ADTNode root,int key){        return this.search(root, key);    }}

示例程序

/** * 二叉查找树main方法 */public class ADTMain {    public static void main(String[] args) {        ADTSearch adtSearch = new ADTSearch();        ADTNode searchResult = adtSearch.searchEntrance(ADTBuilder.buildBySample_1(), 47);        System.out.println(searchResult==null?"搜索不到该结点":searchResult.getVal());    }}

我的二维码

觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！

转载地址：https://blog.csdn.net/xl_1803/article/details/112706149 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！