一文详解:二叉搜索树

这几天一直在刷题,每天都觉得时间不够用,心态上会有波动。争取在9月之前刷到300道题,调整心态,继续前行。

今天我们来复习一下二叉排序树(BST),首先我们先看下定义:
一棵空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
(4)没有键值相等的结点。
其实BST是一个排过序的二叉树,具体怎么排的呢?按照定义可以知道,对于一个结点比它小的值,放在左边;比它大的值放在右边。其中左子树和右子树也分别满足这个规则。例如下图这个二叉树就是一个二叉排序树(BST)
在这里插入图片描述
接下来我们用代码来实现,当然啦,第一步肯定先要造一个结点,然后结点组成一个二叉树
造结点:
在节点中我们写了添加节点的方法,使用的是递归的方式;不得不说,在树的问题中,递归用的真的是多。其实为了方便遍历我们写了二叉树的中序遍历(递归方式)。

//创建node结点
class Node{
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value+
                '}';
    }

    //添加节点的方法
    //递归的方式添加节点,需要满足二叉排序树
    public void add(Node node){
        if(node == null){
            return;
        }

        //判断传入的结点的值和当前子树的根节点的值的关系
        if(node.value<this.value){
            //如果当前结点左子节点为null
            if(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();
        }
    }

}

有了每个结点之后,我们来构造二叉树:

//创建二叉排序树
class BinarySortTree{
    private Node root;
    //添加节点的方法
    public void add(Node node){
        if(root == null){
            root = node;
        }else{
            root.add(node);
        }
    }
    //中序排序
    public void infixOrder(){
        if(root != null){
            root.infixOrder();
        }else{
            System.out.println("当前的二叉排序树是空的");
        }
    }
}

最后进行测试:

public class BST {
    public static void main(String[] args) {
        int[] arr={7,3,10,12,5,1,9};
        BinarySortTree binarySortTree = new BinarySortTree();
        for(int i=0;i<arr.length;i++){

            //binarySortTree.add(arr[i]);
            //需要传入的是node结点
            binarySortTree.add(new Node(arr[i]));
        }
        //中序遍历二叉排序树
        binarySortTree.infixOrder();
    }
}

这里我们需要注意的是:二叉树和二叉排序树主要区别就是排序,因此,我们需要注意二叉排序树的插入,单独拎出来看一下:

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

热门文章

暂无图片
编程学习 ·

Python:% 和 .format() 的使用

目录基本的格式化值转换填充和对齐字符串截断长串结合截断与填充数字填充数字带符号的数字有名字的占位符Getitem 和 Getattr日期时间参数化的格式自定义对象多年来,Python 具有出色的字符串格式化程序,但是有关它们的文档在理论和技术上都太过严格了。通过此站点,我们尝试通…
暂无图片
编程学习 ·

『杭电1251』统计难题

Problem DescriptionIgnatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).Input输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师…
暂无图片
编程学习 ·

中断、异常、系统调用的概念

系统调用是由应用程序发起的,意思是应用程序主动向操作系统发出服务请求。 异常是由不良的应用程序发起的,意思是非法指令或者其他坏的处理状态,比如内存出错。 中断是由外设发起的,它来自于不同硬件设备的计时器或者网络的中断。
暂无图片
编程学习 ·

日志框架 SLF4j

是什么:SLF4J,即简单日志门面(Simple Logging Facade for Java),不是具体的日志解决方案,它只服务于各种各样的日志系统。按照官方的说法,SLF4J是一个用于日志系统的简单Facade,允许最终用户在部署其应用时使用其所希望的日志系统为什么:在java.util.logging, logback…
暂无图片
编程学习 ·

文本生成评价指标的进化与推翻

文章目录前言基于词重叠率的方法机器翻译 & 摘要 常用指标BLEUROUGENISTMETEORTERdata to text 常用指标relation generation (RG)content selection (CS)content ordering (CO)如何实现上述的评价指标CoverageDistinctimage caption 常用指标CIDEr好处SPICE词向量评价指标…
暂无图片
编程学习 ·

flume采集多个文件夹日志

在flume1.6版本及之前,如果想要监控多个目录下的多个文件,可以使用Filelistener,在flume1.7之后,增加了TAILDIR,主要是监控文件的变化 参考配置: #配置Agent a1 的组件 a1.sources=r1 a1.sinks=s1 a1.channels=c1#描述/配置a1的source1 a1.sources.r1.type=TAILDIR #偏移量…
暂无图片
编程学习 ·

抓头,0xc00005错误看到一个比较多的解释 记录一下

说明文字:PAGE-FAULT-IN-NONPAGED-AREA 通常的原因:内存错误(数据不能使用分页文件交换到磁盘中). 解决方法:卸掉所有的新近安装的硬件. 运行由计算机制造商提供的所有系统诊断软件.尤其是内存检查. 检查是否正确安装了所有新硬件或软件,如果这是一次全新安装,请与硬件或软…
暂无图片
编程学习 ·

JavaIo流看这一篇就足够了

1什么是文件? 文件可认为是相关记录或存放在一起相关数据的集合。 我们用什么去操作文件呢? 在Java当中专门有一个包Java.io.*;是内置的包,包含对文件的读和写的操作。 2File类 在Java当中使用File类来操作文件和目录。 File类的四个构造方法 File(File parent, String chil…
暂无图片
编程学习 ·

关于剪贴板的故事—起源于公众号后台的一次探寻

关于剪贴板的故事—起源于公众号后台的一次探寻 整个事情的起源是这样的。 六月底,我打算重新开始更我停了很久的公众号,因为域名到期和图片自动上传不够便利的原因,我弃用了之前的vscode+markdown preview enhanced插件+qiniu-upload-image插件的写文方案。同时,vscode写m…
暂无图片
编程学习 ·

靶机实战(DC-4)

DC-4实验环实验过程信息收集主机发现端口扫描服务发现网站指纹漏洞发现漏洞利用提权总结 实验环 靶机:DC-4 测试机:kali(IP:192.168.186.128),win10 实验过程 信息收集 主机发现 netdiscover -I eth0 -r 192.168.186.0/24 nmap -sn 192.168.186.0/24 arp-scan -l ,arp-sc…
暂无图片
编程学习 ·

【浅拷贝】Object.create()、Object.assign()、扩展运算符

文章目录【ES5】Object.create() 方法【ES6】Object.assign() 方法【ES6】对象展开运算符 "..."【ES5】Object.create() 方法第一层嵌套层原对象未被修改,而第二层开始,原对象被影响(计数器例子只有一层)【ES6】Object.assign() 方法第一层嵌套层原对象未被修改,…
暂无图片
编程学习 ·

JVM-面试题

一、什么是Java虚拟机?为什么Java被称作是“平台无关的编程语言”?Java虚拟机是一个可以执行Java字节码的虚拟机进程。Java源文件被编译成能被Java虚拟机执行的字节码文件。 Java被设计成允许应用程序可以运行在任意的平台,而不需要程序员为每一个平台单独重写或者是重新编译…
暂无图片
编程学习 ·

“/“和 “\“以及“//“和“\\“有什么区别?

大家在学习生活中对于斜杠肯定不会陌生,不管在网址或者地址都会接触到这些东西,这几天刚好抽出一段时间来给大家讲解一下,有什么问题遗漏大家多多指正!!"/"正斜杠表示除法,分割;在windows系统中常用来分割“命令行参数”;正斜杠还表示虚拟路径,比如网址。&q…
暂无图片
编程学习 ·

生成文件时加序号

生成的文件按序号01,02,03,04去排列,有需要的同学可以使用,希望可以帮到你public static String generateName(File fil,final String fileName){int count = fil.listFiles(new FileFilter(){public boolean accept(File file){if(file.getName().startsWith(fileName))…
暂无图片
编程学习 ·

奥运五环的绘制

#奥运五环的绘制 import turtle turtle.width(10) turtle.color(“blue”) turtle.circle(50) turtle.penup() turtle.goto(120,0) turtle.pendown() turtle.color(“black”) turtle.circle(50) turtle.penup() turtle.goto(240,0) turtle.pendown() turtle.color(“red”) tu…
暂无图片
编程学习 ·

7月1日学习记录

额~ 今日份的记录,今天投了两家公司,春招都过去3,4个月了,再怂得不敢投简历不敢面试,就有点说不过去了…现在对我来说最最重要的是要学会敢于面对失败。 编程题:整数中1出现的次数 求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。 思考: 先把每个数字转换…
暂无图片
编程学习 ·

JAVA中集合的迭代/遍历方法iterator()

JAVA中集合的迭代/遍历方法以下讲解的遍历方式/迭代方式,是所有Collection通用的一种方式在Map集合中不能使用,在所有的Collection以及子类中使用第一步:创建迭代器对象: Iterator it = e.iterator();第二步:通过以上获取的迭代器对象开始迭代/遍历集合 以下两个方法为迭代…