什么是二叉查找树，有什么优势？

柔情只为你懂 2023-01-07 08:49 141阅读 0赞

### 引言 ###

原文链接：[什么是二叉查找树，有什么优势？][Link 1] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

### 1、二叉查找树的定义 ###

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

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

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

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

*  若左子树不为空，则左子树所有结点的值小于根结点
 *  若左子树不为空，则左子树所有结点的值小于根结点
 *  左右子树也是二叉查找树

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

二叉查找树有三个操作：

*  查找结点
 *  插入结点
 *  删除结点

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

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

![图片][49ae3498f1e9871b4d2d7fc8bbd046a1.png]

*  ADTBuilder：可以直接返回构建好的二叉树样本
 *  ADTMain：main方法所在类，提供二叉查找树各种操作的示例程序
 *  ADTDelete：二叉查找树的删除操作
 *  ADTInsert：二叉查找树的插入操作
 *  ADTNode：二叉查找树结点类
 *  ADTSearch：二叉查找树的查找操作

### 2、二叉查找树的查找 ###

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

*  key
 *  List<Data>
 *  左孩子指针
 *  右孩子指针

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

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

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

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

假设要查找的二叉排序树如下图所示。  
![图片][ad1f5106df0e39bc08e5505a2e519e40.png]

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

下面重点介绍一下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());
        }
    }

### 我的二维码 ###

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70][]

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484573&idx=1&sn=7450aca8554e1144db1d76b7d251cd53&chksm=ea307c5fdd47f549cab2a932590d54699dadf62e8ddd9407cc860404334386a3a8a9e82415e5&token=841855279&lang=zh_CN#rd
[49ae3498f1e9871b4d2d7fc8bbd046a1.png]: /images/20221119/2e493a0416794db3ac75430a52dfdf99.png
[ad1f5106df0e39bc08e5505a2e519e40.png]: /images/20221119/30c9b4e0afae4dafa78f178e904f0eb8.png
[https_gitee.com_bobo_tea_datastructure]: https://gitee.com/bobo_tea/datastructure
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201222130032214.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM=,size_16,color_FFFFFF,t_70