【数据结构】Binary Search Tree(BST) 二分搜索树

2023-11-18

在这里插入图片描述

数据结构源码

实现类

import java.util.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二分搜素树 —— BST
 * @param <E>
 */
public class BST<E extends Comparable<E>> {

    /**
     * 维护内部类，结点Node
     */
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    /**
     * 维护字段
     */
    private Node root;
    private int size;

    /**
     * 构造函数
     */
    public BST() {
        root = null;
        size = 0;
    }

    /**
     * 返回BST的size
     * @return
     */
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 向二分搜索树中添加新的元素e
     * @param e
     */
    public void add(E e) {
        root = add(root, e);
    }

    /**
     * 向以node为根的二分搜索树中插入元素E，递归算法
     * 返回插入新节点后二分搜索树的根
     * @param node
     * @param e
     * @return
     */
    private Node add(Node node, E e) {

        if (node == null) {
            size++;
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        }
        else if (e.compareTo(node.e) > 0) {  // e.compareTo(node.e) > 0
            node.right = add(node.right, e);
        }

        return node;
    }

    /**
     * 看二分搜索树中是否包含元素e
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    /**
     * 看以node为根的二分搜索树中是否包含元素e，递归算法
     * @param node
     * @param e
     * @return
     */
    private boolean contains(Node node, E e) {

        if (node == null)
            return false;

        if (e.compareTo(node.e) == 0) {
            return true;
        }
        else if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        }
        else { // e.compareTo(node.e) > 0
            return contains(node.right, e);
        }
    }

    /**
     * 二分搜索树的前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    /**
     * 前序遍历以node为根的二分搜索树，递归算法
     * @param node
     */
    private void preOrder(Node node) {
        if (node == null)
            return;

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    public void preOrderNR() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.e);

            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);

        }
    }

    /**
     * 二分搜索树的中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }

    /**
     * 中序遍历以node为根的二分搜索树，递归算法
     * @param node
     */
    private void inOrder(Node node) {
        if (node == null)
            return;

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    /**
     * 二分搜索树的后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    /**
     * 二分搜索树的层序遍历
     */
    public void levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);

            if (cur.left != null)
                q.add(cur.left);
            if (cur.right != null)
                q.add(cur.right);
        }
    }

    /**
     * 寻找二分搜索树的最小元素
     * @return
     */
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty!");
        }
        return minimum(root).e;
    }

    private Node minimum(Node node) {
        if (node.left == null)
            return node;
        return minimum(node.left);
    }

    /**
     * 寻找二分搜索树最大元素
     * @return
     */
    public E maximum() {
        if (size == 0)
            throw new IllegalArgumentException("BST is empty");
        return maximum(root).e;
    }

    /**
     * 返回以node为根的二分搜索树的最大值所在的节点
     * @param node
     * @return
     */
    private Node maximum(Node node) {
        if (node.right == null)
            return root;
        return maximum(node.right);
    }

    /**
     * 从二分搜索树中删除最小值所在的结点，返回最小值
     * @return
     */
    public E removeMin() {
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后的新的二分搜素树的根
     * @param node
     * @return
     */
    private Node removeMin(Node node) {

        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    /**
     * 从二分搜索树中删除最大值所在的结点，返回最大值
     * @return
     */
    public E removeMax() {
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    /**
     * 删除掉以node为根的二分搜索树中的最大节点
     * 返回删除节点后的新的二分搜素树的根
     * @param node
     * @return
     */
    private Node removeMax(Node node) {

        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

    /**
     * 从二分搜索树中删除元素为e的结点
     * @param e
     */
    public void remove(E e) {
        root = remove(root, e);
    }

    /**
     * 删除以node为根的二分搜索树中值为e的结点，递归算法
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @param e
     * @return
     */
    public Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        }
        else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        }
        else { // e == node.e
            // 待删除节点左子树为空时
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            // 待删除节点右子树为空时
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况
            // 找到比待删除结点大的最小节点，即待删除结点右子树的最小节点
            // 用这个节点顶替待删除结点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    /**
     * 生成以node为根结点，深度为depth的描述二叉树的字符串
     * @param node
     * @param depth
     * @param res
     */
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if (node == null) {
            res.append(generateDepthString(depth) + "null\n");
            return;
        }

        res.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("--");
        }
        return res.toString();
    }

    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
//        int[] nums = {5, 3, 6, 8, 4, 2};
//        for (int num : nums) {
//            bst.add(num);
//        }

        ///
        //      5        //
        //     /  \      //
        //    3    6     //
        //   / \    \    //
        //  2   4    8   //
        ///
//        bst.levelOrder();

//        bst.preOrder();
//        System.out.println();
//
//        bst.preOrderNR();

//        bst.inOrder();
//        System.out.println();
//
//        bst.postOrder();
//        System.out.println();
//        System.out.println(bst);

        Random random = new Random();
        int n = 1000;
        for (int i = 0; i < n; i++) {
            bst.add(random.nextInt(10000));
        }

        ArrayList<Integer> nums = new ArrayList<>();
        while (!bst.isEmpty()) {
            nums.add(bst.removeMin());
        }

        System.out.println(nums);

        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i - 1) > nums.get(i))
                throw new IllegalArgumentException("Error");
        }

    }
}

数据结构拆解

维护字段和内部类

    /**
     * 维护内部类，结点Node
     */
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    /**
     * 维护字段
     */
    private Node root;
    private int size;

构造函数


    /**
     * 构造函数
     */
    public BST() {
        root = null;
        size = 0;
    }

增


    /**
     * 向二分搜索树中添加新的元素e
     * @param e
     */
    public void add(E e) {
        root = add(root, e);
    }

    /**
     * 向以node为根的二分搜索树中插入元素E，递归算法
     * 返回插入新节点后二分搜索树的根
     * @param node
     * @param e
     * @return
     */
    private Node add(Node node, E e) {

        if (node == null) {
            size++;
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        }
        else if (e.compareTo(node.e) > 0) {  // e.compareTo(node.e) > 0
            node.right = add(node.right, e);
        }

        return node;
    }

删



    /**
     * 从二分搜索树中删除最小值所在的结点，返回最小值
     * @return
     */
    public E removeMin() {
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后的新的二分搜素树的根
     * @param node
     * @return
     */
    private Node removeMin(Node node) {

        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    /**
     * 从二分搜索树中删除最大值所在的结点，返回最大值
     * @return
     */
    public E removeMax() {
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    /**
     * 删除掉以node为根的二分搜索树中的最大节点
     * 返回删除节点后的新的二分搜素树的根
     * @param node
     * @return
     */
    private Node removeMax(Node node) {

        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

    /**
     * 从二分搜索树中删除元素为e的结点
     * @param e
     */
    public void remove(E e) {
        root = remove(root, e);
    }

    /**
     * 删除以node为根的二分搜索树中值为e的结点，递归算法
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @param e
     * @return
     */
    public Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        }
        else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        }
        else { // e == node.e
            // 待删除节点左子树为空时
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            // 待删除节点右子树为空时
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况
            // 找到比待删除结点大的最小节点，即待删除结点右子树的最小节点
            // 用这个节点顶替待删除结点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    }

改

查


    /**
     * 返回BST的size
     * @return
     */
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }


    /**
     * 看二分搜索树中是否包含元素e
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    /**
     * 看以node为根的二分搜索树中是否包含元素e，递归算法
     * @param node
     * @param e
     * @return
     */
    private boolean contains(Node node, E e) {

        if (node == null)
            return false;

        if (e.compareTo(node.e) == 0) {
            return true;
        }
        else if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        }
        else { // e.compareTo(node.e) > 0
            return contains(node.right, e);
        }
    }

    /**
     * 二分搜索树的前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    /**
     * 前序遍历以node为根的二分搜索树，递归算法
     * @param node
     */
    private void preOrder(Node node) {
        if (node == null)
            return;

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    public void preOrderNR() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.e);

            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);

        }
    }

    /**
     * 二分搜索树的中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }

    /**
     * 中序遍历以node为根的二分搜索树，递归算法
     * @param node
     */
    private void inOrder(Node node) {
        if (node == null)
            return;

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    /**
     * 二分搜索树的后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    /**
     * 二分搜索树的层序遍历
     */
    public void levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);

            if (cur.left != null)
                q.add(cur.left);
            if (cur.right != null)
                q.add(cur.right);
        }
    }

    /**
     * 寻找二分搜索树的最小元素
     * @return
     */
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty!");
        }
        return minimum(root).e;
    }

    private Node minimum(Node node) {
        if (node.left == null)
            return node;
        return minimum(node.left);
    }

    /**
     * 寻找二分搜索树最大元素
     * @return
     */
    public E maximum() {
        if (size == 0)
            throw new IllegalArgumentException("BST is empty");
        return maximum(root).e;
    }

    /**
     * 返回以node为根的二分搜索树的最大值所在的节点
     * @param node
     * @return
     */
    private Node maximum(Node node) {
        if (node.right == null)
            return root;
        return maximum(node.right);
    }

测试用例


    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
//        int[] nums = {5, 3, 6, 8, 4, 2};
//        for (int num : nums) {
//            bst.add(num);
//        }

        ///
        //      5        //
        //     /  \      //
        //    3    6     //
        //   / \    \    //
        //  2   4    8   //
        ///
//        bst.levelOrder();

//        bst.preOrder();
//        System.out.println();
//
//        bst.preOrderNR();

//        bst.inOrder();
//        System.out.println();
//
//        bst.postOrder();
//        System.out.println();
//        System.out.println(bst);

        Random random = new Random();
        int n = 1000;
        for (int i = 0; i < n; i++) {
            bst.add(random.nextInt(10000));
        }

        ArrayList<Integer> nums = new ArrayList<>();
        while (!bst.isEmpty()) {
            nums.add(bst.removeMin());
        }

        System.out.println(nums);

        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i - 1) > nums.get(i))
                throw new IllegalArgumentException("Error");
        }

    }

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法与数据结构

数据结构

深度优先

二分搜素树

【数据结构】Binary Search Tree(BST) 二分搜索树的相关文章

XMT.com超200万被区块链终端交易

链客专为开发者而生有问必答此文章来自区块链技术社区未经允许拒绝转载狭义来讲区块链是一种按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构并以密码学方式保证的不可篡改和不可伪造的分布式账本当下区块链俨然成为炙手可
c语言基础（一）——预处理详解

目录 1 预处理是什么 2 预定义符号 3 define标识符 3 1 define 定义标识符 3 2 define定义宏命名约定 3 3 宏的题目 4 和 4 1 的作用 4 2 的作用 5 带副作用的宏参数 6 宏与函数的对比 7
Nomad系列-Nomad网络模式

系列文章 Nomad 系列文章概述 Nomad 的网络和 Docker 的也有很大不同和 K8s 的有很大不同另外 Nomad 不同版本 Nomad 1 3 版本前后或是否集成 Consul 及 CNI 等不同组件也会导致网络模式各
python中多进程（multiprocessing）

python中多进程 multiprocessing 一 multiprocessing中使用子进程概念 from multiprocessing import Process 可以通过Process来构造一个子进程 p Process t

随机推荐

USB匹配电阻

做过USB的人都或许有一个纠结那就是D 和D 上到底要串多大的电阻串在源端还是终端我想说网络上的说法都不完全正确首先USB有低速全速和高速之分在低速和全速模式下是电压驱动的驱动电压为3 3V 但在高速模式下是电流驱动的驱动
计算机组成原理期末复习【超实用】

计算机组成原理第二版唐朔飞编著课本有些地方还不错可以下载电子版看看 b站2小时讲解链接 https www bilibili com video BV1x4411q7Fz 初次录讲解视频各种差错和画音不同步请各位谅解我录到后面
Qt常用数据类型

常用数据类型 1 常用基本数据类型常用接口求绝对值 T是泛型以下都是 T qAbs const T t 最大值和最小值会把最大或最小的返回出来 T qMax const T value1 const T value2 T qMin
解决笔记本电脑（i）某个键的字母按不出来

前两天清理电脑键盘没有关机然后清理了一下键盘再使用的时候就打不出 i 字母了重启也没用看网上说使用Fn F11 可以但是可能每个电脑配置不同使用失败最后想了想F11 不行最后试试F12吧最后Fn F11 成功解锁哈哈哈
ffmpeg通过命令拉udp的rtsp流的方法

ffmpeg用命令拉流是非常简单易用的特别是对这种常见的摄像头的流 rtsp 10 1 21 121 554 profile1 稍微复杂一点 rtsp admin a1234567 10 1 21 121 554 cam realmoni
【sqli-labs】 less5 GET - Double Injection - Single Quotes - String (双注入GET单引号字符型注入)...

双注入查询可以查看这两篇介绍 https www 2cto com article 201302 190763 html https www 2cto com article 201303 192718 html 简而言之就是构造如下的查询
相关性和因果性

一如果A和B相关有至少五种可能性 1 A导致B 2 B导致A 3 C导致A和B 4 A和B互为因果 5 小样本引起的巧合二相关是线性关性非线性的因果关系对应的相关性可能会减弱或消失统计上A和B具有线性或者非线性关系通常代表
AccessibilityEvent常用详解

AccessibilityEvent常用详解本文是作者在使用android的AccessibilityService时记录使用到的AccessibilityEvent的一些情况如有错误欢迎指正 dinjet foxmail com 屏幕
C++（VS基础操作）基础操作

VS的基本操作 1 创建项目在起始页中选择 2 创建文件夹 CPP Project 起文件名称 3 起项目名称 CPPLesson01 4 解决方案一个解决方案能存放多个项目一个项目只能选择一个解决方案 5 创建空项目 6 c 使用开发
编译原理（静态语义分析）

文章目录语法制导翻译中间代码简介后缀式三地址码符号表声明语句的翻译数组元素的引用例题数组元素引用的语法制导翻译布尔表达式拉链与回填语法制导翻译语义分析的作用检查结构正确的句子表达的意思是否正确执行规定的语义动作
RHEL6进入救援模式

1 救援模式救援模式作用更改root密码恢复硬盘文件系统操作系统无法启动时通过救援模式启动 2 放入系统光盘重启从光盘启动 4 选择语言默认English就行 5 保持默认即可 6 网口检查不需要直接选择NO 7 直接c
函数重载隐藏重写覆盖

重载 Overload 重载是比较容易弄明白的定义重载是指不同的函数使用相同的函数名但是函数的参数个数或类型不同参数列表不同调用的时候根据函数的参数来区别不同的函数函数重载跟返回值无关规则函数名相同必须具有不同的参数列表
【Linux篇】fputs、fgets函数

一 fputs函数 include
水下图像采集

原文 http blog csdn net sunlinyi66 article details 50153875 NASA提供的雾天标准图像这次终于找到了雾天处理图像来自哪里了雾天图像 http dragon larc nasa go
机器学习——朴素贝叶斯算法

朴素贝叶斯算法 1 引言 2 朴素贝叶斯分类方法 3 概率基础 4 朴素贝叶斯特征提取 5 朴素贝叶斯分类的sklearn实现 6 垃圾短息分类补充 1 引言贝叶斯方法是一个历史悠久有着坚实的理论基础的方法同时处理很多问题时直接而又
django自动生成接口文档

django自动生成接口文档先pip安装coreapi包配置在urls py 在对应的serializers py文件设置备注先pip安装coreapi包 pip install coreapi 小知识这里不需要使用导出pip所
亚马逊云服务器aws配置ssl https证书

文章目录 1 申请证书 1 1 搜索ssl 1 2 请求证书 1 3 请求共有证书 1 4 添加域名 1 5 选择验证方法提交审核等待大概10分钟审核成功 2 配置证书 2 1 创建负载均衡器 2 2 选择https 2 3 配置负载
Qt创建一个自定义按钮

1 概述案例编写一个自定义按钮要求 1 给按钮添加自定义背景 2 监听按钮点击事件 2 代码案例 1 创建一个类让其继承QWidget 点击下一步下一步最后完成 2 打开MyPushButton 让其继承QPushButton 如下所
java 子线程异常_Java子线程中的异常处理（通用）

在普通的单线程程序中捕获异常只需要通过try catch finally 代码块就可以了那么在并发情况下比如在父线程中启动了子线程如何在父线程中捕获来自子线程的异常从而进行相应的处理呢常见错误也许有人会觉得很简单嘛直接在
【数据结构】Binary Search Tree(BST) 二分搜索树

数据结构源码实现类 import java util import java util LinkedList import java util Queue import java util Stack 二分搜素树 BST param

【数据结构】Binary Search Tree(BST) 二分搜索树

数据结构源码

实现类

数据结构拆解

维护字段和内部类

构造函数

增

删

改

查

测试用例

【数据结构】Binary Search Tree(BST) 二分搜索树 的相关文章

随机推荐

热门标签

【数据结构】Binary Search Tree(BST) 二分搜索树的相关文章