本文共 2013 字,大约阅读时间需要 6 分钟。
原文链接: 希望点进去的小伙伴关注一下我的公众号哟,文末有二维码,谢谢!
对于顺序存储,不需要维护有序性,但查询效率低;
而有序存储,查询效率高,但由于插入删除需要维护有序性,因此效率低。
本文要介绍的二叉查找树(也叫二叉搜索树、二叉排序树、ADT树)结合了二者的优势,不仅查询效率高,插入和删除效率也高。
二叉查找树(空树也是二叉查找树)的定义:
若左子树不为空,则左子树所有结点的值小于根结点
若左子树不为空,则左子树所有结点的值小于根结点
左右子树也是二叉查找树
构建一颗二叉查找树的目的,不是为了排序,而是为了提高查询、插入、删除关键字的速度。不管怎么说,有序数据结构的查找速度总是要大于无序数据结构的。
二叉查找树有三个操作:
查找结点
插入结点
删除结点
本文主要实现二叉查找树的查找操作。
首先,我的代码有6个类,如下图所示。
ADTBuilder:可以直接返回构建好的二叉树样本
ADTMain:main方法所在类,提供二叉查找树各种操作的示例程序
ADTDelete:二叉查找树的删除操作
ADTInsert:二叉查找树的插入操作
ADTNode:二叉查找树结点类
ADTSearch:二叉查找树的查找操作
假设所有结点中没有相同的两个值,因为二叉查找树是对关键字的排序,而关键字可以理解为唯一。退一万步来讲,就算有两条数据关键字相同,也可以将它们存储于一个结点中,即结点可以设置四个字段:
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()); }}
觉得写得不错的小伙伴,扫码关注一下我的公众号吧,谢谢呀!
转载地址:http://gppkf.baihongyu.com/