数据结构–二叉排序树（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