AI 助理
备案控制台
开发者社区 云计算 文章 正文

二叉排序树(BST)

2023-08-09 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 二叉排序树(BST)

二叉排序树（Binary Sort Tree）


前言： 二叉排序树是二叉树中十分重要的一种，又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。


Node节点类代码


package day7_test;
public class Node {
    public int val;
    public Node right;
    public Node left;
    /**
     * 查找要删除的节点并返回
     * @param index 要删除的节点的val值
     * @return 返回要删除的节点
     */
    public  Node searchNode(int index){
        if(this.val == index){
            return this;
        }else if(index < this.val) {
            if(this.left == null){
                return null;
            }else{
                return this.left.searchNode(index);
            }
        }else {
            if (this.right == null){
                return null;
            }else {
                return this.right.searchNode(index);
            }
        }
    }
    /**
     * 找到要删除的节点的父节点
     * @param index 要删除的节点的索引
     * @return 返回父节点
     */
    public Node searchParent(int index){
        //情况一： 当前节点就是要删除节点的父节点
        if((this.left != null && this.left.val == index) ||(this.right != null && this.right.val == index)){
            return this;
        }else {
            //左节点不为空，并且左节点就是parent
            if(index < this.val && this.left != null){
                return this.left.searchParent(index);
            }else if (index >= this.val && this.right != null){
                return this.right.searchParent(index);
            }else {
                return null;
            }
        }
    }
    //添加节点
    public void add(Node node){
        if(node == null){
            return;
        }
        if(node.val < this.val){
            if(this.left == null){
                this.left = node;
            }else{
                this.left.add(node);
            }
        }else{
            //node.val >= this.val
            if(this.right == null){
                this.right = node;
            }else{
                this.right.add(node);
            }
        }
    }
    //中序遍历二叉树
    public void infix(){
        if(this.left != null){
            this.left.infix();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.infix();
        }
    }
    public Node(int val) {
        this.val = val;
    }
    @Override
    public String toString() {
        return "Node[" +
                "val=" + val +
                ']';
    }
}


二叉排序树的添加功能


思路：


每传进来一个node节点，我们就与当前节点进行比较


1.node的val值 < 当前节点的val值：

向左进行递归，一直递归到this.left == null时，加入node节点


2.node的val值 >= 当前节点的val值：

向右进行递归，知道this.right == null时，加入node节点


代码实现：

//添加节点
public void add(Node node){
    if(node == null){
        return;
    }
    if(node.val < this.val){
        if(this.left == null){
            this.left = node;
        }else{
            this.left.add(node);
        }
    }else{
        //node.val >= this.val
        if(this.right == null){
            this.right = node;
        }else{
            this.right.add(node);
        }
    }
  }

 

结果：


Node[val=0]

Node[val=1]

Node[val=3]

Node[val=5]

Node[val=7]

Node[val=9]

Node[val=10]

Node[val=12]


二叉排序树删除功能详解


思路：

首先分三种情况进行处理：


① 所删除的节点为叶子节点（left 和right 节点上为空）

② 所删除的节点为非叶子节点，并且left 或 right节点上只有一个不为空

③ 所删除的节点为非叶子节点，并且left 和 right 都不为空


在处理这三种情况之前，先再Node节点类中增添方法，用来查询要删除的目标节点targetNode 以及targetNode的父节点 parent节点


代码如下：

/**
 * 查找要删除的节点并返回
 * @param index 要删除的节点的val值
 * @return 返回要删除的节点
 */
public  Node searchNode(int index){
    if(this.val == index){
        return this;
    }else if(index < this.val) {
        if(this.left == null){
            return null;
        }else{
            return this.left.searchNode(index);
        }
    }else {
        if (this.right == null){
            return null;
        }else {
            return this.right.searchNode(index);
        }
    }
}
/**
 * 找到要删除的节点的父节点
 * @param index 要删除的节点的索引
 * @return 返回父节点
 */
public Node searchParent(int index){
    //情况一： 当前节点就是要删除节点的父节点
    if((this.left != null && this.left.val == index) ||(this.right != null && this.right.val == index)){
        return this;
    }else {
        //左节点不为空，并且左节点就是parent
        if(index < this.val && this.left != null){
            return this.left.searchParent(index);
        }else if (index >= this.val && this.right != null){
            return this.right.searchParent(index);
        }else {
            return null;
        }
    }
}


情况一：删除的是叶子节点


步骤：【

找到目标节点targetNode 及其它的父节点 parent

确定targetNode是parent的left节点 还是right 节点

parent.left = null 或 parent.right = null ;

】


代码：

Node targetNode = root.searchNode(index);
if (targetNode == null){
      System.out.println("没有找到要删除的节点！");
    return;
}
if (root.left == null && root.right == null){
    root = null;
    return;
}
Node parent = root.searchParent(index);
//要删除的是叶子节点
if(targetNode.left == null && targetNode.right == null){
    if(parent.left!= null && parent.left.val == targetNode.val){
        parent.left = null;
    }else if(parent.right != null && parent.right.val == targetNode.val ) {
        parent.right = null;
    }
}


情况二：要删除的节点只有一个子节点


步骤【

  1. 找到父节点和targetNode目标节点后
  2. 先判断targetNode的left 和right 是否为空 ，如果不为空再判断是否有parent节点，因为很可能这个节点是root节点 ，root节点没有parent节点
  3. 接下来就是四种判断

targetNode 有左节点 ，targetNode是parent的左节点；—–> parent.left = targetNode.left;


targetNode 有左节点 ，targetNode是parent的右节点；—–> parent.right = targetNode.left;


targetNode 有右节点 ，targetNode是parent的左节点；—–>parent.left = targetNode.right;


targetNode 有右节点 ，targetNode是parent的右节点；—–>parent.right = targetNode.right;


】


代码实现：

//要删除的节点只有一个子节点
else{
    if(targetNode.left != null){
        //要删除的节点有左子节点
        if(parent != null){
            if (parent.left == targetNode){
                parent.left = targetNode.left;
            }else{
                parent.right = targetNode.left;
            }
        }else {
            root = targetNode.left;
        }
    }
    else {
        if(parent != null){
            if (parent.left == targetNode){
                parent.left = targetNode.right;
            }else{
                parent.right = targetNode.right;
            }
        }else {
            root = targetNode.right;
        }
    }
}


情况三：要删除的节点只有一个子节点


这种情况我们有两种解决办法


步骤 【

方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点

方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点

】


代码实现：

//要删除的是有两个子节点的节点
            else if (targetNode.left != null && targetNode.right !=null){
                /*
                  方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点
                  方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点
                 */
//                int tempMin = 0;
//                Node tempNode = targetNode.right;
//                while(tempNode.left != null){
//                    tempNode = tempNode.left;
//                }
//                tempMin = tempNode.val;
//                deleteNode(tempMin);
//                targetNode.val = tempMin;
                int tempMax = 0;
                Node tempNode = targetNode.left;
                while(tempNode.right != null){
                    tempNode = tempNode.right;
                }
                tempMax = tempNode.val;
                deleteNode(tempMax);
                targetNode.val = tempMax;
            }

     

main方法代码

public static void main(String[] args) {
    int arr[] ={7,3,10,12,5,1,9,0};
    BinarySortTree b = new BinarySortTree();
    for(int i=0;i<arr.length;i++){
        b.add(new Node(arr[i]));
    }
    b.infix(b.root);
    b.deleteNode(3);
    b.deleteNode(12);
    b.deleteNode(5);
    b.deleteNode(1);
    b.deleteNode(7);
    b.deleteNode(9);
    b.deleteNode(10);
    b.deleteNode(0);
    System.out.println("删除之后~~~");
    b.infix(b.root);
}


整体代码实现：

package day7_test;
public class BinarySortTree {
    public Node root;
    public static void main(String[] args) {
        int arr[] ={7,3,10,12,5,1,9,0};
        BinarySortTree b = new BinarySortTree();
        for(int i=0;i<arr.length;i++){
            b.add(new Node(arr[i]));
        }
        b.infix(b.root);
        b.deleteNode(3);
        b.deleteNode(12);
        b.deleteNode(5);
        b.deleteNode(1);
        b.deleteNode(7);
        b.deleteNode(9);
        b.deleteNode(10);
        b.deleteNode(0);
        System.out.println("删除之后~~~");
        b.infix(b.root);
    }
    /**
     * 删除二叉树节点
     * @param index 要删除的节点的val值
     */
    public void deleteNode(int index){
        if (root == null){
            return;
        }
        else{
            Node targetNode = root.searchNode(index);
            if (targetNode == null){
                  System.out.println("没有找到要删除的节点！");
                return;
            }
            if (root.left == null && root.right == null){
                root = null;
                return;
            }
            Node parent = root.searchParent(index);
            //要删除的是叶子节点
            if(targetNode.left == null && targetNode.right == null){
                if(parent.left!= null && parent.left.val == targetNode.val){
                    parent.left = null;
                }else if(parent.right != null && parent.right.val == targetNode.val ) {
                    parent.right = null;
                }
            }
            //要删除的是有两个子节点的节点
            else if (targetNode.left != null && targetNode.right !=null){
                /*
                  方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点
                  方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点
                 */
//                int tempMin = 0;
//                Node tempNode = targetNode.right;
//                while(tempNode.left != null){
//                    tempNode = tempNode.left;
//                }
//                tempMin = tempNode.val;
//                deleteNode(tempMin);
//                targetNode.val = tempMin;
                int tempMax = 0;
                Node tempNode = targetNode.left;
                while(tempNode.right != null){
                    tempNode = tempNode.right;
                }
                tempMax = tempNode.val;
                deleteNode(tempMax);
                targetNode.val = tempMax;
            }
            //要删除的节点只有一个子节点
            else{
                if(targetNode.left != null){
                    //要删除的节点有左子节点
                    if(parent != null){
                        if (parent.left == targetNode){
                            parent.left = targetNode.left;
                        }else{
                            parent.right = targetNode.left;
                        }
                    }else {
                        root = targetNode.left;
                    }
                }
                else {
                    if(parent != null){
                        if (parent.left == targetNode){
                            parent.left = targetNode.right;
                        }else{
                            parent.right = targetNode.right;
                        }
                    }else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }
    //添加节点
    public void add(Node node){
        if (root == null){
            root = node;
        }else {
            root.add(node);
        }
    }
    //中序遍历
    public void infix(Node root){
        if (root == null){
            System.out.println("空树！");
            return;
        }
        root.infix();
    }
}


运行结果：


删除3 后

Node[val=0]

Node[val=1]

Node[val=5]

Node[val=7]

Node[val=9]

Node[val=10]

Node[val=12]

删除3,12,5,1 后

Node[val=0]

Node[val=7]

Node[val=9]

Node[val=10]

删除3,12,5,1,7,9 后

Node[val=0]

Node[val=10]

删除所有的之后

空树！


Rayce.
目录
相关文章
chian-ocean
|
28天前
|
存储 C++
【C++】二叉搜索树（BST）
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其每个节点的左子树所有节点值小于该节点值，右子树所有节点值大于该节点值，且左右子树也均为二叉搜索树。BST支持高效的数据查找、插入和删除操作，时间复杂度通常为O(log n)。本文档详细介绍了BST的基本概念、存储结构及其实现，包括迭代和递归两种方式的查找、插入、删除等操作的具体代码示例。
chian-ocean
39 3
java冯坚持
|
2月前
|
存储 算法 数据管理
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
这篇文章通过需求分析、代码实现和测试验证，详细介绍了二叉排序树的创建、遍历和删除操作，以及二叉平衡树（AVL）的自平衡特性和单旋转操作，旨在提高树结构在数据管理中的效率和性能。
java冯坚持
53 0
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
廖文
|
2月前
|
API 调度
二叉排序树
二叉排序树
廖文
41 0
小小工匠
|
7月前
Algorithms_二叉树的前序遍历、中序遍历、后续遍历(深度优先）
Algorithms_二叉树的前序遍历、中序遍历、后续遍历(深度优先）
小小工匠
65 0
dulu~dulu
|
7月前
|
算法
二叉树的递归遍历和非递归遍历
二叉树的递归遍历和非递归遍历
dulu~dulu
34 0
爱敲代码的小黄
|
7月前
|
数据格式
树结构练习——排序二叉树的中序遍历
树结构练习——排序二叉树的中序遍历
爱敲代码的小黄
53 1
fly丶知秋
|
算法 JavaScript 前端开发
二叉搜索树BST（二）
二叉搜索树BST
fly丶知秋
44 0
fly丶知秋
|
存储 算法
二叉搜索树BST （一）
二叉搜索树BST
fly丶知秋
78 0
砖业洋__
树的遍历(已知前序遍历中序遍历求后序遍历，或者已知后序中序求先序)
二叉树相关练习
砖业洋__
137 0
游客dnwnpshbiaxrq
先序、中序、后序遍历确定唯一树
快速学习先序、中序、后序遍历确定唯一树
游客dnwnpshbiaxrq
267 0
先序、中序、后序遍历确定唯一树

热门文章

最新文章

  • 1
    四大触点，教你从“用户视角”构建数据分析体系
  • 2
    Spring-boot+Dubbo应用启停源码分析
  • 3
    《Stata统计分析与应用（第2版）》一3.4 图形的保存、合并及修改
  • 4
    RocketMq-Request-Reply消息
  • 5
    Confluence 6 手动添加用户
  • 6
    2013年4月20日 通用权限管理系统组件V3.8功能改进说明
  • 7
    Configuring EIGRP Unequal-Cost Paths
  • 8
    PowerShell 指定关键词遍历文件内容
  • 9
    Windows时间服务出现故障 向用户发送错误的时间
  • 10
    三种dedecms调用相关文章的方法
  • 1
    《鸿蒙HarmonyOS应用开发从入门到精通（第2版）》简介
    55
  • 2
    《Python 助力：人工智能模型的“瘦身”与“加速”之旅》
    111
  • 3
    《非计算机专业者：Python 开启人工智能职业新航道》
    40
  • 4
    《Python赋能：智绘智慧城市新蓝图》
    43
  • 5
    《智育新篇：点亮学生人工智能伦理与社会责任之光》
    48
  • 6
    《数据主权：人工智能时代的核心基石与挑战》
    34
  • 7
    鸿蒙HarmonyOS应用开发 | 探索 HarmonyOS Next-从开发到实战掌握 HarmonyOS Next 的分布式能力
    111
  • 8
    鸿蒙原生开发环境的创新与性能优化：从工具到跨平台支持的全方位提升
    280
  • 9
    鸿蒙HarmonyOS应用开发 | 「鸿蒙技术分享」HarmonyOS NEXT元服务卡片实战体验
    165
  • 10
    Qwen-Coder：通过Qwen 2.5模型实现智能代码生成的技术实践
    41

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    DataWorks售前咨询