数据结构--二叉排序树（Binary Search Tree，简称BST）

2024-02-28 13:44
文章标签 数据结构 排序 二叉 tree search binary 简称 bst

本文主要是介绍数据结构--二叉排序树（Binary Search Tree，简称BST），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这里写自定义目录标题

  • 二叉排序树
    • 二叉排序树与排序数组没有排序数组，链式存储链表的对比
    • 二叉排序树概念
      • 对于搜索操作，
      • 对于插入操作，
      • 对于删除操作，
    • 分析删除节点
    • 代码
    • 运行结果

二叉排序树

二叉排序树与排序数组没有排序数组，链式存储链表的对比

  • 二叉排序树（BST）：

    • 数据结构：通过链式存储方式实现，每个节点包含一个值以及左右子节点的指针。
    • 特点：满足二叉搜索树的性质，即对于树中的每个节点，其左子树中的所有节点都小于它，右子树中的所有节点都大于它。
    • 插入操作：按照大小顺序将新元素插入到树的合适位置，保持树的有序性。
    • 查询操作：通过比较节点的值与目标值的大小关系，递归地在左子树或右子树中进行查找。
    • 删除操作：根据情况，将要删除的节点替换为其子节点或后继节点，并保持树的有序性。

  • 排序数组：

    • 数据结构：通过线性数组的方式存储，元素按照升序排列。
    • 特点：数组中的元素按照从小到大的顺序排列。
    • 插入操作：通过比较元素的大小关系，找到插入位置，并将元素插入到数组中的合适位置，然后移动其他元素以保持有序性。
    • 查询操作：使用二分查找算法，在数组中快速定位目标值。
    • 删除操作：通过移动元素，将要删除的元素从数组中删除，并保持有序性。

  • 链式存储的链表：

    • 数据结构：使用节点和指针的方式进行存储，每个节点包含一个值以及指向下一个节点的指针。
    • 特点：节点之间通过指针连接，形成一个链式结构，可以是单向链表、双向链表等。
    • 插入操作：在链表中插入新节点可以在 O(1) 时间内完成，只需调整指针的指向。
    • 查询操作：需要从头节点开始依次遍历链表，时间复杂度为 O(n)。
    • 删除操作：通过调整节点之间的指针，可以在 O(1) 时间内完成删除操作。

数组排序，

  • 优点：可以使用二分查找，查找速度快，
  • 缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。[示意图]
    使用链式存储-链表
  • 不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。[示意图]

二叉排序树概念

二叉排序树（Binary Search Tree，简称BST）是一种特殊的二叉树，它满足以下条件：

  • 左子树上所有节点的值小于根节点的值。
  • 右子树上所有节点的值大于根节点的值。
  • 左右子树也分别为二叉排序树。
    通过这种结构，我们可以快速地进行查找、插入和删除操作。

在一个二叉排序树中，每个节点都存储着一个值，并且左子节点的值小于父节点的值，右子节点的值大于父节点的值。这样的结构使得我们可以利用二叉3树的特性，在平均情况下以O(log n)的时间复杂度进行搜索、插入和删除操作。

对于搜索操作，

  • 我们从根节点开始，比较目标值与当前节点的大小关系，如果目标值小于当前节点的值，则在左子树中继续搜索；如果目标值大于当前节点的值，则在右子树中继续搜索；如果目标值等于当前节点的值，则找到了目标节点。

对于插入操作，

  • 我们从根节点开始，比较要插入节点的值与当前节点的大小关系，如果要插入节点的值小于当前节点的值，并且当前节点的左子节点为空，则将要插入的节点作为当前节点的左子节点；如果要插入节点的值大于当前节点的值，并且当前节点的右子节点为空，则将要插入的节点作为当前节点的右子节点；否则，继续在左子树或右子树中进行插入操作。

对于删除操作，

  • 我们首先找到要删除的节点。如果要删除的节点没有子节点，则直接删除即可；如果要删除的节点只有一个子节点，则将子节点替代要删除的节点；如果要删除的节点有两个子节点，则需要找到其后继节点（即右子树中最小的节点），将其值替代要删除的节点的值，然后再删除后继节点。

二叉排序树在实际应用中有广泛的应用，例如在数据库索引、字典等场景中，都可以使用二叉排序树来提高搜索效率。

分析删除节点

在这里插入图片描述
33在这里插入图片描述

代码

package com.atguigu.binarysorttree;public class BinarySortTreeDemo {public static void main(String[] args) {int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};BinarySortTree binarySortTree = new BinarySortTree();//循环的添加结点到二叉排序树for(int i = 0; i< arr.length; i++) {binarySortTree.add(new Node(arr[i]));}//中序遍历二叉排序树System.out.println("中序遍历二叉排序树~");binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12//测试一下删除叶子结点binarySortTree.delNode(12);binarySortTree.delNode(5);binarySortTree.delNode(10);binarySortTree.delNode(2);binarySortTree.delNode(3);binarySortTree.delNode(9);binarySortTree.delNode(1);binarySortTree.delNode(7);System.out.println("root=" + binarySortTree.getRoot());System.out.println("删除结点后");binarySortTree.infixOrder();}}//创建二叉排序树
class BinarySortTree {private Node root;public Node getRoot() {return root;}//查找要删除的结点public Node search(int value) {if(root == null) {return null;} else {return root.search(value);}}//查找父结点public Node searchParent(int value) {if(root == null) {return null;} else {return root.searchParent(value);}}//编写方法: //1. 返回的 以node 为根结点的二叉排序树的最小结点的值//2. 删除node 为根结点的二叉排序树的最小结点/*** * @param node 传入的结点(当做二叉排序树的根结点)* @return 返回的 以node 为根结点的二叉排序树的最小结点的值*/public int delRightTreeMin(Node node) {Node target = node;//循环的查找左子节点，就会找到最小值while(target.left != null) {target = target.left;}//这时 target就指向了最小结点//删除最小结点delNode(target.value);return target.value;}//删除结点public void delNode(int value) {if(root == null) {return;}else {//1.需求先去找到要删除的结点  targetNodeNode targetNode = search(value);//如果没有找到要删除的结点if(targetNode == null) {return;}//如果我们发现当前这颗二叉排序树只有一个结点if(root.left == null && root.right == null) {root = null;return;}//去找到targetNode的父结点Node parent = searchParent(value);//如果要删除的结点是叶子结点if(targetNode.left == null && targetNode.right == null) {//判断targetNode 是父结点的左子结点，还是右子结点if(parent.left != null && parent.left.value == value) { //是左子结点parent.left = null;} else if (parent.right != null && parent.right.value == value) {//是由子结点parent.right = null;}} else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点int minVal = delRightTreeMin(targetNode.right);targetNode.value = minVal;} else { // 删除只有一颗子树的结点//如果要删除的结点有左子结点 if(targetNode.left != null) {if(parent != null) {//如果 targetNode 是 parent 的左子结点if(parent.left.value == value) {parent.left = targetNode.left;} else { //  targetNode 是 parent 的右子结点parent.right = targetNode.left;} } else {root = targetNode.left;}} else { //如果要删除的结点有右子结点 if(parent != null) {//如果 targetNode 是 parent 的左子结点if(parent.left.value == value) {parent.left = targetNode.right;} else { //如果 targetNode 是 parent 的右子结点parent.right = targetNode.right;}} else {root = targetNode.right;}}}}}//添加结点的方法public void add(Node node) {if(root == null) {root = node;//如果root为空则直接让root指向node} else {root.add(node);}}//中序遍历public void infixOrder() {if(root != null) {root.infixOrder();} else {System.out.println("二叉排序树为空，不能遍历");}}
}//创建Node结点
class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}//查找要删除的结点/*** * @param value 希望删除的结点的值* @return 如果找到返回该结点，否则返回null*/public Node search(int value) {if(value == this.value) { //找到就是该结点return this;} else if(value < this.value) {//如果查找的值小于当前结点，向左子树递归查找//如果左子结点为空if(this.left  == null) {return null;}return this.left.search(value);} else { //如果查找的值不小于当前结点，向右子树递归查找if(this.right == null) {return null;}return this.right.search(value);}}//查找要删除结点的父结点/*** * @param value 要找到的结点的值* @return 返回的是要删除的结点的父结点，如果没有就返回null*/public Node searchParent(int value) {//如果当前结点就是要删除的结点的父结点，就返回if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {//如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空if(value < this.value && this.left != null) {return this.left.searchParent(value); //向左子树递归查找} else if (value >= this.value && this.right != null) {return this.right.searchParent(value); //向右子树递归查找} else {return null; // 没有找到父结点}}}@Overridepublic String toString() {return "Node [value=" + value + "]";}//添加结点的方法//递归的形式添加结点，注意需要满足二叉排序树的要求public void add(Node node) {if(node == null) {return;}//判断传入的结点的值，和当前子树的根结点的值关系if(node.value < this.value) {//如果当前结点左子结点为nullif(this.left == null) {this.left = node;} else {//递归的向左子树添加this.left.add(node);}} else { //添加的结点的值大于 当前结点的值if(this.right == null) {this.right = node;} else {//递归的向右子树添加this.right.add(node);}}}//中序遍历public void infixOrder() {if(this.left != null) {this.left.infixOrder();}System.out.println(this);if(this.right != null) {this.right.infixOrder();}}}

运行结果

E:\jdk\jdk1.8.0_161\bin\java.exe "-javaagent:D:\IDEA\IntelliJ IDEA 2022.2.1\lib\idea_rt.jar=62543:D:\IDEA\IntelliJ IDEA 2022.2.1\bin" -Dfile.encoding=UTF-8 -classpath E:\jdk\jdk1.8.0_161\jre\lib\charsets.jar;E:\jdk\jdk1.8.0_161\jre\lib\deploy.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\access-bridge-64.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\cldrdata.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\dnsns.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\jaccess.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\jfxrt.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\localedata.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\nashorn.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunec.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunjce_provider.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunmscapi.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunpkcs11.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\zipfs.jar;E:\jdk\jdk1.8.0_161\jre\lib\javaws.jar;E:\jdk\jdk1.8.0_161\jre\lib\jce.jar;E:\jdk\jdk1.8.0_161\jre\lib\jfr.jar;E:\jdk\jdk1.8.0_161\jre\lib\jfxswt.jar;E:\jdk\jdk1.8.0_161\jre\lib\jsse.jar;E:\jdk\jdk1.8.0_161\jre\lib\management-agent.jar;E:\jdk\jdk1.8.0_161\jre\lib\plugin.jar;E:\jdk\jdk1.8.0_161\jre\lib\resources.jar;E:\jdk\jdk1.8.0_161\jre\lib\rt.jar;D:\课程\java课程\guiGu_suanFa\out\production\guiGu_suanFa com.atguigus.binarysorttree.BinarySortTreeDemo
中序遍历二叉排序树~
Node [value=1]
Node [value=2]
Node [value=3]
Node [value=5]
Node [value=7]
Node [value=9]
Node [value=10]
Node [value=12]
root=null
删除结点后
二叉排序树为空，不能遍历Process finished with exit code 0

这篇关于数据结构--二叉排序树（Binary Search Tree，简称BST）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/755666。

相关文章

Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
Spring排序机制之接口与注解的使用方法

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri
阅读更多...
大数据小内存排序问题如何巧妙解决

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法：数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高；分治法高效但实现复杂；位图法可读性差,但存储空间受限... 目录三种方法：方法概要数据库排序（http://www.chinasem.cn对数据库设备要求较高）分治法（常
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序
阅读更多...
关于Java内存访问重排序的研究

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
uva 575 Skew Binary（位运算）

uva 575 Skew Binary（位运算）

求第一个以（2^(k+1)-1)为进制的数。 数据不大，可以直接搞。 代码： #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2