二叉树详解
二叉树详解
一、开始
什么是树,什么又是二叉树?我知道大家都听过,但对于具体的概念,应该还是比较模糊的吧?
一起来看看,什么是树,什么又是二叉树!
二、概念
1)树结构概念
树是一种数据结构,它是由节点相连,带来的一个层次结构的数据集合,且除了根节点以外,其余节点有且只有一个父节点。
与链表不同的是,树的连接关系往往是一对多的关系。
树结构通常表现为下图方式
子节点:一个节点指向下一个节点时,下个节点是上个节点的子节点。上图A节点的子节点是B节点和C节点
父节点、双亲节点:一个节点指向下一个节点时,下个节点是上个节点的子节点。上图B节点的父节点是A节点
兄弟节点:拥有同一个父节点的两个节点,互为兄弟节点。上图如D节点和E节点互为兄弟节点
节点的度:拥有子节点的数量称为节点的度。如D节点的度为3,C节点的度为2
节点的权:代表节点中存的对象。如D节点代表存了D字符
根节点:一颗树最开始的节点,被称为根节点。上图为A节点
叶子节点:没有子节点的节点,也就是度为0的节点。上图为H节点、E节点、F节点等
内部节点、枝节点:除了根节点和叶子节点以外的节点。如B节 ...
排序算法之堆排序
排序算法之堆排序
一、介绍
由于堆排序与以前的排序都不太一样,他是基于顺序存储的二叉树结构来进行的排序,故此拉出来单独做了一张。
以前的排序算法传送门
二、概念
在开始编码之前,我们先要理解下面两个概念
1)顺序存储的二叉树
对于任意一个数组,它都可以转换为一个完全二叉树
如下图,平铺着转换就可以了
对于一个顺序存储的二叉树,它的节点连接定义如下
下标N的左节点:2n+12n+12n+1
下标N的右节点:2n+22n+22n+2
下标N的父节点:n−12\frac{n-1}{2}2n−1
2)大小顶堆
什么是大顶堆,就是父节点永远都比子节点的数要大,故名为大顶堆。如下图
相反,如果一颗二叉树的父节点都比子节点的数要小,那么它就是小顶堆。如下图
三、代码
简单的来说,堆排序就是将持续的将,一个顺序存储的二叉树变成大顶堆或者小顶堆。
升序使用大顶堆,降序使用小顶堆。
步骤如下,这是第一步
从非叶子节点开始前遍历
每一个非叶子节点,都将和自己的左节点、右节点进行判断
根据大小顶堆的需要,来进行替换
直到称为一个大小顶堆
成为了大小顶堆之后,我们将得到了一个最大或者 ...
汉诺塔问题
汉诺塔问题
一、介绍
汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。介绍来源于百度知道。
我小时候也玩过,但当时就是云里雾里的,不知道怎么去解题,简单的可以完成,难的就不行了。
到了现在,如何用代码解题,依旧是一个不小的难度,反正我是得琢磨一会。
二、解题思路
有三根柱子,分别是起始的柱子,辅助的柱子,目标的柱子,我们需要将圆盘从开始移动到目标。
但由于汉诺塔的这项规则,在小圆盘上不能放大圆盘上,我们就可以将其分为两部分,分为上面一部分,下面一部分。
下面一部分永远比上面一部分要大,所以需要先将上面这一部分移动到辅助的位置。
当上面这部分有多个时,照样看成上下两部分,上面部分移动到辅助位置(最开始的目标位置,现在变成了辅助位置)
如此重复执行,直到完成所有的迁移。
大家可以先试试这个小游戏,找找灵感
代码如下,主要 ...
MySQL触发器详解
MySQL触发器详解
一、介绍
大家应该都听过MySQL的触发器,它的概念如下
它是一种特殊的一种存储过程,当表数据发生了新增、更新、删除时,便触发这个存储过程。
由此,故而名为触发器。下面一起来看看触发器的使用吧!
二、语法
1)语法格式
1234567891011121314-- 删除drop trigger 触发器名;-- 定义结束符号delimiter $$-- 创建create trigger 触发器名 before|after insert|update|delete on 表名 for each rowbegin 执行语句end$$-- 定义结束符号delimiter ;
触发事件类型
insert:有数据新增时触发
update:有数据被修改时触发
delete:有数据被删除时触发
执行顺序
before:在触发事件前执行语句
after:在触发事件后执行语句
在执行语句中,和正常的存储过程差不多,不过触发器多了两个存储过程没有的对象,分别是NEW和OLD;
OLD:代表着更新,删除前的数据,可以通过OLD.字段名来获取以前的值
NEW:代表着新增 ...
SpringBoot中使用注解读取redis缓存
SpringBoot中使用注解读取redis缓存
一、介绍
我们使用redis的时候,一般都是以下这个步骤
查询指定的redis缓存
如果有直接返回,(异步执行查询,更新redis缓存)
如果没有则执行查询,(同时设置redis缓存)
此外,如果是增删改操作,将触发一次设置redis缓存的操作。
上面的一些步骤高度重复,我决定造个轮子,基于注解、切面和反射来完成此项功能。
二、相关代码
1)依赖
处于SpringBoot中,redis、aop等相关依赖不要忘记
123456789101112<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web</artifactId></dependency><dependency> <groupId>org.springframework.boot</groupId> < ...
SpringBoot中的@Conditional注解
SpringBoot中的@Conditional注解
一、介绍
在Spring的应用下,我们希望一些bean可以通过一些条件来判断是否需要实例化,并加载到spring容器中。
所以,@Conditional注解就是为了解决上面这个需求而制定的注解。@Conditional注解是总接口,可以定制逻辑。
二、详情
1)@Conditional
先看源码,此注解需要传入Condition接口的实现类,可以多个
12345678@Target({ElementType.TYPE, ElementType.METHOD})@Retention(RetentionPolicy.RUNTIME)@Documentedpublic @interface Conditional { Class<? extends Condition>[] value(); }
所以,使用此注解时,我们若是有些高度定制化的一些判断,可以先实现Condition接口,再讲实现类提供给@Conditional注解,使用示例如下。
首先要有一个Condition ...
Java使用NIO实现Socket通信
Java使用NIO实现Socket通信
一、介绍
在上次的博客中,已经了解到NIO当中最为重要的两个对象。分别是缓冲Buffer和通道Channel,也进行了基本的使用,不过使用的是FileChannel,主要用来与文件打交道。
那么,这一次使用NIO实现Socket网络通信,主要是使用到ServerSocketChannel和SocketChannel。
同样,在本次作为NIO的网络通信,建议先了解传统BIO的网络通信,传送门在此。
二、实现
1)服务端
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475package com.banmoon.test;import lombok.extern.slf4j.Slf4j;import java.io.IOException;import java.net.InetSocketAddress;import ja ...
Java的NIO入门
Java的NIO入门
一、介绍
Java NIO是从Java 1.4版本开始引入的一个新的IO ,在传统的IO模型中,使用的是同步阻塞IO,也就是blocking IO。
而NIO指的是New IO,代指新IO模型。有些博客指的是not blocking IO,非阻塞IO,叫哪种都行,都是NIO。
在NIO中,最重要的两个东西就是缓冲Buffer和通道Channel了。继续往下看!
二、Buffer
缓冲区Buffer,可以理解成是一个含数组的容器对象,该对象提供了一组方法,可以更轻松地使用其中的数据。该对象记录了一些状态值,能够跟踪和记录缓冲区的状态变化情况。
后续的通道Channel的读取、写入操作都经过缓冲。
Buffer是一个抽象类,它的实现类有很多,但我们最常用的还是ByteBuffer,因为要和字节打交道嘛
它里面有四个最重要的状态值,分别是
mark:标记
position:当前读取或存储数据的索引位置,位置
limit:当前缓冲最大可以写入或读取到的位置,极限
capacity:当前缓冲的容量,容量
其中,mark<= position&l ...
数据库的三大范式
数据库的三大范式
一、介绍
没有规矩,不成方圆。这句话在数据库的规范中同样适用,所以就有了这几项规定,数据库的三大范式。
我相信很多人都听过三大范式,面试题中也经常会问到,什么是数据库三大范式,这太常见了。
以前我只是机械式的回复面试官,但以后不会,不仅要学会说概念说规范,还能从实际出发,要不要严格遵守三大范式。
二、概念
1)第一范式
概念:每一个列都是不可再分的列
例如下面这张表,由于region字段可以再细分为省份province和城市city,所以此表将不满足第一范式
name
sex
region
半月无霜
男
广东省广州市
将region字段拆分后,满足了第一范式
name
sex
province
city
半月无霜
男
广东省
广州市
2)第二范式
概念:在满足第一范式后,消除非主属性对主属性的部分函数依赖
先看看这张订单表,订单编号、商品ID、用户ID作为联合主键
每一个字段本身都不可再分,满足第一范式。
但其中有个字段用户名称,它依赖于用户ID,所以此表并不满足第二范式
订单编号
商品ID
用户ID
数量
金额
用户名称 ...
SpringBoot整合socket通信
SpringBoot整合socket通信
一、介绍
很多人都不太理解socket通信指的是什么,简单来讲,它是一个完成两个应用程序之间的数据传输的东西。
socket是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象,一个socket就是网络上进程通信的一端,提供了应用层进程利用网络协议交换数据的机制。从所处的地位来讲,socket上联应用进程,下联网络协议栈,是应用程序通过网络协议进行通信的接口,是应用程序与网络协议栈进行交互的接口。
本次使用Java语言去实现socket通信,用的SpringBoot框架,当然直接使用main方法启用也是没有问题的。
二、实现
1)服务端
先设置一下需要用到的配置,主要就是这个端口号,我觉得放配置文件中会比较好
12socket-port: testSocket: 2333
socket服务端启动类
此处使用到了bean的初始化,如果不熟悉的话,使用静态代码块也是一样的
1234567891011121314151617181920212223242526272829303132333435363738394041424344packag ...