Red Dragon

  • 归档

  • 标签

  • 分类

  • 关于

kotlin学习笔记1:kotlin基础语法,与java交互

Posted on 2020-05-29

环境

android studio
创建项目时需要点击:include kotlin
创建kotlin文件:new Kotlin File(位置在new java class下面一格)

基础语法

var age :int = 18//声明一个变量
val name : String = “zhang san”//声明不可变变量,非常量
val name2 : String = null//编译器会报错不能为空
fun 关键字来定义函数
$符调用参数

package kt.zj.com.ktlearn

import android.support.v7.app.AppCompatActivity
import android.os.Bundle

class MainActivity : AppCompatActivity() {

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)

        var age: Int = 18;
        val name: String = "lucy";

        who(name,age);

    }

    fun who(name :String,age :Int){
//      println(name + "_________" + age);
        println("$name" + "_________" + "$age" );
    }
}

与java互调用

.举例1:静态互调

ktolin函数能直接写在文件里面,而不用写在类里面的
kotlin文件在编译之后依旧是jvm平台的一个class
一个用java调用kotlin函数的例子:

注意:kotlin文件名带kt后缀,且java调用者函数是静态。

JavaUseKotlin.java

package kt.zj.com.ktlearn;

public class JavaUseKotlin {

    public static void main(String[] args) {
        UtilsKt.sayHello();;
    }
}

Utils.kt

package kt.zj.com.ktlearn

fun sayHello(){
    println("hello");
}

.举例2:将类作为参数传递

1.kotlin文件被编译成的并不是class字节码,而是叫做Kclass的字节码文件
2.kotlin文件必须声明类名,否则不识别
class KotlinMain
3.实验场景:

  • 创建一个javaMain.class
  • 创建一个kotlinMain.kt(并声明类名)
  • 在kotlin测试类里定义2个函数testClass,并实验测试函数
    //测试函数
    fun main(args : Array<String>){
      testClass(javaMain::class.java)//入参为javaClass时,记得添加后缀.java
      testClass(KotlinMain::class)//入参为KClass时,直接调
    }
    //ps:在实际过程中,.java后缀由ide自己给我们补全了。
    

//入参为javaClass时,记得添加后缀.java
fun testClass(clazz :Class){
println(clazz.simpleName);
}

//入参为kClass
fun testClass(clazz :KClass){
println(clazz.simpleName);
}



### .举例3:kotlin与java在关键字上的冲突
问题条件1:
在java中又一个变量,变量名叫in;

public class javaMain {
public static String in = “in”;
}

在kotlin中,in是一个关键字,所以kotlin在调这个变量时,不能直接调用,需要用2个反引号包裹,表示去解决这个冲突;

println(javaMain.in);

ps:在实际过程中,反引号包裹由ide自己给我们补全了。

## 排错

Kotlin reflection implementation is not found at runtime. Make sure you have kotlin-reflect.jar in the classpath
at …
``` 解决:
https://majing.io/posts/10000007151189

AVL树

Posted on 2019-12-26 | In 数据结构/算法

概念

当按顺序往二分搜索树中添加元素时,其会退化成链表,为了让树结构能够有自平衡性,科学家们定义了一种新的平衡树——AVL树,名字取自几个科学家姓名的首字母。

AVL树的一些基本特性:
第一点,满足二分搜索树所有性质;
第二点,带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

感性认识

如下演算:

已知10 9 6数列 ,插入一个4;

已知10 9 6数列,以10为轴,左子树高度为2,右子树高度为0,差值大于1,即平衡因子大于1,判定该树为不平衡,其中10为<不平衡起始节点>,6为<不平衡节点>,且由于<以10为起始节点,在它左孩子的左孩子处发生了不平衡(LL)>,需进行<右单旋>让其恢复平衡

              10
              /
             9
            /
           6

           ↓

           9
          / \
         6   10

旋转完成后插入一个4:

           9
          / \
         6   10
        /  
       4

四种情况(LL\RR\LR\RL)

在第一个例子中,我们有了<不平衡起始节点>,<不平衡节点>, <…(LL)>,<右单旋>这么一些认识。接下来进行挨个举例。一波操作下来应该大家都理解了。

  • LL
    见上面列出都例子。

  • RR

旋转前
10
/
9 15

16

22

旋转后
10
/
9 16
/
15 22


已知10 9 15 16 22 数列,以15为轴,左子树高度为0,右子树高度为2,差值大于1,即平衡因子大于1,判定该树为不平衡,其中15为<不平衡起始节点>,22为<不平衡节点>,且由于<以15为起始节点,在它**右孩子的右孩子处**(RR)发生了不平衡>,需进行<左单旋>让其恢复平衡。

- LR
```java
旋转前
          9
          / 
         6   
          \ 
          8

旋转中     
           9
          / 
         8   
        /  
       6

旋转后

           8
          /  \
         6    9

已知9 6 8 数列,以9为轴,左子树高度为2,右子树高度为0,差值大于1,即平衡因子大于1,判定该树为不平衡,其中9为<不平衡起始节点>,8为<不平衡节点>,且由于<以9为起始节点,在它左孩子的右孩子处(LR)发生了不平衡>,需进行<先左再右旋>让其恢复平衡。

  • RL
旋转前
          10          
          /\
         9  15    
              \
              22
              /
             16

旋转中
          10          
          /\
         9  15    
              \
              16
                \
                22


旋转后
          10          
          /\
         9  16    
            / \
          15   22

已知10 9 15 16 22 数列,以15为轴,左子树高度为0,右子树高度为2,差值大于1,即平衡因子大于1,判定该树为不平衡,其中15为<不平衡起始节点>,16为<不平衡节点>,且由于<以15为起始节点,在它右孩子的左孩子处(RL)发生了不平衡>,需进行<先右后左旋>让其恢复平衡。

总结

  • 确保该树是哥bst树
  • 从最深节点往跟节点追溯进行旋转
  • 4种情况 左左右单旋 you you

参考链接:
https://www.sohu.com/a/270452030_478315
https://www.jianshu.com/p/fa7db1bb2577

LeetCode#206:反转链表之递归实现

Posted on 2019-12-26 | In 数据结构/算法

不废话,直入主题(我是个很直接的人):

已知单链表,求反转:
1->2->3->4->5->null

期望效果:
null<-1<-2<-3<-4<-5

答题模版:


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

    }
}

冷静分析:(自行脑补熊猫头抽烟表情包)
我们要反转,那么涉及到俩个元素,当前节点currentNode,和currentNode.next节点,我们主要做的,是将curremtNode.next.next = currnetNode。
结合递归,我们肯定是从1递归到2,从2递归到3这样,举个例:


reverseList (currentNode = 1) {
   saveNextNode = currentNode.mext = 2;
   reverseList(1.next = 2)
}

reverseList (currentNode = 2) {
   saveNextNode = currentNode.mext = 3;
   reverseList(2.next = 3)
}

reverseList (currentNode = 3) {
   saveNextNode = currentNode.mext = 4;
   reverseList(3.next =4)
}

reverseList (currentNode = 4){
   saveNextNode = currentNode.mext = 5;
   reverseList(4.next = 5)

}

......

然后加上:递归返回条件,就是12345顺序递归那个条件:

    //退出条件: < 1 - 2 - 3 - 4 - 5 - null >
    if (currhead == null || currhead.next == null) {
        return currhead;
    }

然后我们再加上这行:核心替换逻辑

   saveNextNode.next = currentNode;

最后再加上:斩断老的指向逻辑:

   currentNode.next = null; //斩断老的指向

于是有代码:

  private static ListNode reverse(ListNode currhead) {

        //退出条件: < 1 - 2 - 3 - 4 - 5 - null >
        if (currhead == null || currhead.next == null) {
            return currhead;
        }

        //12345
        ListNode nextNode = currhead.next;//保存下一个节点 4
        ListNode newHead = reverse(nextNode);//递归 5
        nextNode.next = currhead;//连上头与递归部分
        currhead.next = null;//调整尾部
        return newHead;//返回头节点
    }

最后解释:
这个newHead,是返回到新的头节点,细品这个newHead,其实他就在第一次的时候用到了,之后对链表对改变并没有再用到这个newHead,只是一直传递到新的结尾处。至于为什么要返回这个头节点,只能说是惯例吧,一个链表肯定是先知道其head才好next下去嘛。

LeetCode_237_删除链表中的节点

Posted on 2019-11-26

题干

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9]

示例1

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例2

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明(审题)

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 class Solution {
    public void deleteNode(ListNode node) {
       。。。。。。
    }
}

获得的信息,关键信息

  • 入参为1个,即需要被删除的节点
  • Node结构中没有pre节点,无法访问前驱节点

解题

4,5,1,9
没有前驱则只能用后继next节点做文章。
如要删5,则只需把5的后继节点1的内容拷贝过来,并断掉5对1的指向,思路图如下;

答案:
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

思考

答案是这样没错,但本题的关键点是,为什么不能用node = node.next,而必须要这样做进行全量的拷贝;
众人表示:这样做只是将5引用进行赋值成1的引用,并未改变链表本身的结构。

好,接下来我们演算一下:

链表4,5,1,9四个ListNode,从内存角度来写写伪代码:

Node a = 0x11;
a = new Node{
  val = 4;
  next = b = 0x22;
}
Node b = 0x22;
b = new Node{
  val = 5;
  next = c = 0x33;
}
Node c = 0x33;
c = new Node{
  val = 1;
  next = d = 0x44;
}
Node d = 0x44;
d = new Node{
  val = 9;
  next = null;
}

4个引用a.b.c.d带边4个内存地址,与之对应的在堆里面有4块内存,即引用->对象。并有堆里每个对象都包含一个字段next,该字段的内容指向为一个地址(后继节点地址)

ok,现在我们用node = node.next来试试删除第二个节点5,有如下:

Node a = 0x11;
a = new Node{
  val = 4;
  next = b = 0x22;
}
Node b = 0x33;
b = new Node{
  val = 1;
  next = d = 0x44;
}
Node c = 0x33;
c = new Node{
  val = 1;
  next = d = 0x44;
}
Node d = 0x44;
d = new Node{
  val = 9;
  next = null;
}

可以看到,我们b这个对象是复制c成功了,我们看a,它的next还是指向的0x22这个地址,我们之前对b进行了一次赋值,赋值的内容包括了b的引用地址,也就是说,b现在是0x33及其所包含的字段及值,但它已经不再是a所指向的next节点0x22。仔细想想,a本来指向b(0x22),现在b赋值成了c,变成了0x33,a现在的next还是指向的之前的旧的0x22,但此时的0x22已经不再被之前的b所引用了。换作一张图如下:

从上到下,由原有的链表经过赋值之后并没有改变链表原本的结构,另外,途中绿色框只是为了方便理解,实际上堆里并没有2个0x33的对象.

所以说,不能用node = node.next 替代当前的实现方案(全量拷贝,即保持地址不变(才能保持前驱节点的指向)改变节点内容,实现伪删除效果)

来源

https://leetcode-cn.com/problems/delete-node-in-a-linked-list

Hexo使用笔记

Posted on 2019-11-18 | Edited on 2019-11-20

Preface

本文是一片自己使用过程笔记,程度有限,如果本文未能满足你的要求可移步文末链接,2个大神的教程。

WHAT

hexo不是博客系统,而是静态页面生成、上传的工具

hexo 可以理解为是基于node.js制作的一个博客工具,不是我们理解的一个开源的博客系统。它不需要部署到我们的服务器上,我们的服务器上保存的是hexo帮我们生成静态的html页面(hexo编译.md生成html)
关键词:GITHUB PAGES -> 页面生成,github pages存放的都是静态文件,博客存放的不只是文章内容,还有文章列表、分类、标签、翻页等动态内容,假如,每次写完一篇文章都要手动更新博文目录和相关链接信息,相信谁都会疯掉,所以hexo所做的就是将这些md文件都放在本地,每次写完文章后调用写好的命令来批量完成相关页面的生成,然后再将有改动的页面提交到github。

官网: http://hexo.io
Github: https://github.com/hexojs/hexo
命令doc:https://hexo.io/zh-cn/docs/commands.html


HOW

INSTALL FOR MAC(鉴于篇幅原因,简单写,安装过程中的坑自行百度)

  • step_1 >
    确保有一个git仓库。 repository创建规则,域名:githubUserName + “.github.io”,如:zj614android.github.io //zj614android是我的github用户名。
    电脑中需要已安装Git、Node.js(6.9以上,没有的百度装一下)

  • step_2 > 安装hexo
    npm install -g hexo

  • step_3 > cd /Desktop/Workspaces/hexo/ //随意新建一个Dir,用来放hexo文件

  • step_4 > hexo init

  • step_5 > hexo s //本地运行hexo服务器,跑起来表示安装ok
    INFO Start processing
    INFO Hexo is running at http://localhost:4000 . Press Ctrl+C to stop.

  • step_6 > 目录说明,过一遍就行,忘记了回头来查

    |– demo//项目跟目录名
    |– .gitignore//git时忽略的文件或目录
    |– package-lock.json
    |– package.json//应用程序的信息
    |– _config.yml//网站的配置信息
    |– scaffolds//模板文件夹,Hexo的模板是指在新建的markdown文件中默认填充的内容。
    | |– draft.md
    | |– page.md
    | |– post.md//博文模板
    |– source//资源文件夹,存放用户资源
    | |– _posts//博文目录
    | |– hello-world.md//博文
    |– themes//主题文件夹,Hexo 会根据主题来生成静态页面
    |– landscape.//默认主题
    …

  • step_7 > 初始化配置,如果第一次预装是没有配置的,只显示一个地球的图片。具体配置些啥呢?最直接比如说主题,也就是基本的页面布局,再比如说你这个本地hexo和远程github的关联。这俩个是必修改的。配置文件–> hexo根目录/_config.yml

    url:网站地址,必须修改,此处博文是托管在github上,故此使用http://你的网站名.github.io格式作为网站名字
    language:语言,设置中文,根据需要修改,中文为zh-CN
    注意:配置值与配置名需要隔一个空格,否则会编译报错
    另外选择一个自己喜欢的主题也是必要的,这里就拿Next说,主要就2步,第一步先安装,Next主题的安装方式很简单,只需要在博客主目录下执行(git clone https://github.com/theme-next/hexo-theme-next themes/next
    );第二步就是在配置文件里进行一个theme的配置即可。


Release Blog

安装并跑起来之后,接下来就是发表博客了。
发表就是把本地文件A放到本地指定目录B下执行相应命令C,该文件就会推到我们之前安装并部署好的线上Github地址D了。

||||||||||||||||||||查看目录||||||||||||||||||||
cd blogs //这个blogs是自己本地目录(2.1的step3)
ls

_config.yml
node_modules
public
themes
db.json
package-lock.json
scaffolds
yarn.lock
debug.log
package.json
source //hexo子目录,文章在这个路径下,点进去

||||||||||||||||||||cd进source目录||||||||||||||||||||
cd source/

_posts //文章最终存储目录
about
categories
debug.log
schedule
tags

||||||||||||||||||||发布文章到posts目录||||||||||||||||||||
准备好一篇文章:本例中是《Hexo使用笔记.md》
cd _posts/
localhost:_posts xx$ ls
Hexo基本操作.md bst-tree_houjijiedian.md
bst-tree_delete.md bst-tree_introduce.md

执行hexo g //g即generate简写,生成静态文件
执行hexo d //d即deploy,部署


主线流程就酱

Q&A

发布文章时标题为Untitled

需要md文章头部条件如下语句:(注意冒号后面有空格,hexo内都是这样,注意一下就好)

title: Hexo使用笔记
date: 2019年11月18日15:49:36
tags: tool

换电脑之后如何维护管理博客

username.github.io这个项目并不包含我们博客的md源文件,它保存的是我们本地通过hexo生成的html文件,所以我们为了保险起见最好还是提交俩个repo。
既然要提交就需要注意ignore文件,目前建议的ignore配置文件:

/.deploy_git
/public
/_config.yml

更多请参考:
https://www.jianshu.com/p/a04d75ee9ab6 //关系
https://www.jianshu.com/p/7776b777f3a1 //ignore

更多请参考

hexo入门教程https://www.jianshu.com/p/f7a84b4c5bca
hexo使用教程:https://blinkfox.github.io/tags/Hexo/

bst-tree_delete

Posted on 2019-06-06 | In 数据结构/算法

1.前言

通过上一篇的学习,我们知道bst树的插入操作和遍历等操作;

当我们按照如下顺序插入一堆数字时:

50;29;8;2;5;4;3;44;77;82;10;

呈现出来的树结构如下:


50 
/   \
29     77
/  \     \
8   44     82
/ \
2  10
\    
5
/
4
/
3

本文主要讨论bst树的删除;
那么接下来就以上面这个例子开始说吧;

2.bst树的删除操作

BST树删除一个节点分3种情况:
Q1:被删除节点是叶子节点(即没有左子树和右子树);
IMAGE
Q2:被删除节点不是叶子节点,且只有单个子树(左/右);
IMAGE
Q3:被删除节点不是叶子节点,且同时具有左右子树;
IMAGE

接下来对这三种情况进行深入分析;

2.1.没有子节点

最简单的一种情况,当被删除元素节点是叶子节点时,直接将该叶子节点与其父子关系解除即可;

图示:
IMAGE

代码:

if (srcNode.left == null && srcNode.right == null) {//叶子节点

if (srcNode.parent.left.value.compareTo(srcNode.value) == 0) {
srcNode.parent.left = null;
srcNode.parent = null;
return true;
} else if (srcNode.parent.right.value.compareTo(srcNode.value) == 0) {
srcNode.parent.right = null;
srcNode.parent = null;
return true;
}else {
System.out.println("异常:叶子节点情况");
}

} 

测试结果(删除3):

Node{value=2__height=4, left=null, right=5, parent=8}
Node{value=4__height=2, left=null, right=null, parent=5}
Node{value=5__height=3, left=4, right=null, parent=2}
Node{value=8__height=6, left=2, right=10, parent=29}
Node{value=10__height=1, left=null, right=null, parent=8}
Node{value=29__height=8, left=8, right=44, parent=50}
Node{value=44__height=1, left=null, right=null, parent=29}
Node{value=50__height=8, left=29, right=77, parent=null}
Node{value=77__height=0, left=null, right=82, parent=50}
Node{value=82__height=0, left=null, right=null, parent=77}


50
/\
29  77
/\   \
8 44  82
/\
5 10
/
4

2.2.有一个子节点

删除只有单个孩子节点的元素时,只需要将其父节点指向其原本拥有单个孩子,并将其孩子的父节点指向为被删除元素的父节点即可。
一个不恰当的比喻,关系就像是剔除原本的“父亲”,由原本的“爷爷”元素和原本的“儿子”元素重新构成新的“父子”关系。

图示:
IMAGE

代码:

/**
* 处理节点删除
*
* @param srcNode 源节点,这个参数传进来的是
* @return
*/
private boolean handleDeleteNode(Node srcNode) {

if (srcNode.left == null && srcNode.right == null) {//叶子节点
......

} else if ((srcNode.left != null && srcNode.right == null) || (srcNode.left == null && srcNode.right != null)) {//瘸子子树

BinarySearchTree.Node tempValNode = null;
if (srcNode.left != null && srcNode.right == null) {//右瘸时

tempValNode = srcNode.left;

//判断当前删除节点是父节点的左或者右
if (srcNode.parent.left.value.compareTo(srcNode.value) == 0) {//如果当前待删除节点是其父节点的左节点时
srcNode.parent.left = tempValNode;
} else if (srcNode.parent.right.value.compareTo(srcNode.value) == 0) {//如果当前待删除节点是其父节点的右节点时
srcNode.parent.right = tempValNode;
} else {
System.out.println("异常:判断当前删除节点是父节点的左或者右");
}

} else if (srcNode.left == null && srcNode.right != null) {//左瘸时

tempValNode = srcNode.right;

if (srcNode.parent.left.value.compareTo(srcNode.value) == 0) {//如果当前待删除节点是其父节点的左节点时
srcNode.parent.left = tempValNode;
} else if (srcNode.parent.right.value.compareTo(srcNode.value) == 0) {//如果当前待删除节点是其父节点的右节点时
srcNode.parent.right = tempValNode;
} else {
System.out.println("异常:判断当前删除节点是父节点的左或者右");
}

} else {//异常
System.out.println("异常:瘸子子树情况");
return false;
}

if(null != tempValNode){
tempValNode.parent = srcNode.parent;
}else {
System.out.println("异常:瘸子子树情况:改变爷孙关系为父子关系");
return false;
}

} else if (srcNode.left != null && srcNode.right != null) {//左右子树都有
......
} else {//异常
System.out.println("异常:3种情况之外");
}
return true;
}

测试结果(中序遍历/删除元素2):

Node{value=3__height=1, left=null, right=null, parent=4}
Node{value=4__height=2, left=3, right=null, parent=5}
Node{value=5__height=3, left=4, right=null, parent=8}
Node{value=8__height=6, left=5, right=10, parent=29}
Node{value=10__height=1, left=null, right=null, parent=8}
Node{value=29__height=8, left=8, right=44, parent=50}
Node{value=44__height=1, left=null, right=null, parent=29}
Node{value=50__height=8, left=29, right=77, parent=null}
Node{value=77__height=0, left=null, right=82, parent=50}
Node{value=82__height=0, left=null, right=null, parent=77}

50
/\
29  77
/\   \
8 44  82
/\
5 10
/
4
/
3 

再加一题(中序遍历/删除元素77):
图示:
IMAGE

测试结果:

Node{value=2__height=4, left=null, right=5, parent=8}
Node{value=3__height=1, left=null, right=null, parent=4}
Node{value=4__height=2, left=3, right=null, parent=5}
Node{value=5__height=3, left=4, right=null, parent=2}
Node{value=8__height=6, left=2, right=10, parent=29}
Node{value=10__height=1, left=null, right=null, parent=8}
Node{value=29__height=8, left=8, right=44, parent=50}
Node{value=44__height=1, left=null, right=null, parent=29}
Node{value=50__height=8, left=29, right=82, parent=null}
Node{value=82__height=0, left=null, right=null, parent=50}

50
/\
29 82    
/\
8 44
/\
2 10  
\ 
5
/
4
/ 
3

2.3.有2个子节点

终于进入删除节点的主菜了,我们先用一张图来说明当删除节点具备2个孩子时该怎么操作;

IMAGE

图中8是具有2个孩子的,要删除8该遵循什么操作呢?废话不多说,直接给出答案:

当删除当节点同时具备左右子树时,首先解除这个被删除节点当父子关系,然后用其中序遍历当后继节点进行补位替代其父子关系。

(如何找出后继节点在之前的文章里已经讲过)

这里就用直观的形式来观察:
2_3_4_5_8_10_29_44_50_77_82

8的后继节点是10,用其补位的结果就是下图所示:可以看出这也是一颗合法的bst树;

50
/\
29 82    
/\
10  44
/
2   
\ 
5
/
4
/ 
3

那么方法就出来了:

1.找出中序遍历下的当前待删除节点A的后继节点B
2.将B的value赋值给A
3.删除B

代码:

if (srcNode.left != null && srcNode.right != null) {//左右子树都有
//取出后继节点
BinarySearchTree.Node successorNode = getSuccessorNode(srcNode);
System.out.println(srcNode.value + "    后继节点:  " + successorNode.value);

//1.值的替换
srcNode.value = (T) successorNode.value;

//2.置位空
if (successorNode.parent.left.value.compareTo(successorNode.value) == 0){//左
successorNode.parent.left = null;
}else {//右
successorNode.parent.right = null;
}

successorNode = null;
}

3.Demo

https://github.com/zj614android/designPattern/blob/master/app/src/main/java/com/zj/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%A0%91/bst/BinarySearchTree.java

bst-tree_后继节点

Posted on 2019-06-06 | In 数据结构/算法

1.前言

前一篇我们对BST树做了一个入门,这一篇我们来对BST树找后继节点做个学习,为什么要学这个,因为后面再做删除节点的时候会用到这个知识点。废话不多说,直接开始。

前驱后继节点针对的是树的三种遍历模式下各个节点在不同排列顺序下的位置关系。比如树A在先序遍历下的排列顺序是{3 5 8 7 6},3是5的前驱节点,8是5的后继节点。

但是说前中后序三种遍历方式都有各自的前驱后继节点找法。

本文只讨论以BST树以中序遍历找后继节点为例当做一个入门,更多相关的知识请自行google。

另外本文如有错误请直接指出,感谢。

2.如何寻找后继节点?

2.0:这个树:


50 
/   \
29     77
/  \     \
8   44     82
/ \         /\
2  10       80 99
/\    \
1  5   11
/      \
4       12
/          \
3           13

后继节点是什么意思?比如这棵树用中序遍历列出来是如下数列:

「 1 2 3 4 5 8 10 11 12 13 29 44 50 77 82 」

8的后继节点就是10,29后继节点就是44,82的后继节点就是null;

但是我们要如何取出某个节点的后继节点呢?不可能每次都去遍历存个集合取相邻元素吧,这样是不科学的。

2.1.那么科学的姿势是:

1:如果node结点有右子树,返回该右子树上的最小值(即挂在该右子树上的左子树的最深元素)若没有左子树则返回该元素本身(因其右子树肯定比其本身要大))

比如77,它有右子树82,返回82这棵树上的最小值,由于82这棵树上没有左子树,所以其最小值就是其本身,所以77的后继节点为82

2:如果node结点没有右子树,那么要分两种情况:

a>如果node结点没有右子树,判断当前结点node是不是它父亲的左孩子,如果是,那么它父亲就是它的后继;
比如:1,它首先没有右子树,然后当前节点1又是它父亲的左孩子,所以它的后继就是它的父亲2.

b>如果node结点没有右子树,判断当前结点是不是它父亲的右孩子,如果是,那么一路往父节点方向回溯,直到找到某一个父节点(ParentA)是其自己父节点(ParentA’s Fathter)的左子树,那么这个ParentA’s Fathter就是当前节点Node的后继节点
比如:13,它没有右子树,且是它自己父节点(12)的右孩子,那么开始回溯,回溯到它的父节点12,12并非它自己父节点的左子树,于是继续回溯,11,11也不是它自己父节点的左子树,于是再回溯,10,同样不是,再回溯,8是它自己父节点(29)的左子树,这里的8相当于上面说的”某个父节点ParentA”,这里的29相当于上面说的PaerentA’s Father,所以由此可以推出29是13的后继节点。

3.代码怎么写?

说了这么多还是要落实到代码上。

/**
* 获取指定元素的后继节点
* @return
*/
public Node getSuccessorNode(BinarySearchTree.Node node) {

if(node == null)
return null;

if(node.right == null){//如果该节点没有右子树,那么要分两种情况:
//a>如果node结点没有右子树,判断当前结点node是不是它父亲的左孩子,如果是,那么它父亲就是它的后继;
//比如:1,它首先没有右子树,然后当前节点1又是它父亲的左孩子,所以它的后继就是它的父亲2.

if (null != node.parent.left && node.parent.left.value.compareTo(node.value) == 0) {//node是不是它父亲的左孩子
//那么它父亲就是它的后继;
return node.parent;
} else if (null != node.parent.right && node.parent.right.value.compareTo(node.value) == 0) {//b>如果node结点没有右子树, 判断当前结点是不是它父亲的右孩子,
return getParentFather(node);
} else {
System.out.println("异常:getSuccessorNode");
}

}else {//如果该节点有右子树
//返回该右子树上的最小值(即左子树的最深元素)若没有左子树则返回该元素本身(因其右子树肯定比其本身要大))
if(node.right.left == null)
return node.right;

return getLeftMost(node.right.left);
}

return null;
}

//返回该右子树上的最小值(即左子树的最深元素)
private Node getLeftMost(Node node) {

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

return getLeftMost(node.left);
}


/**
* 如果是,那么一路往父节点方向回溯,直到找到某一个父节点(ParentA)是其自己父节点(ParentA’s Fathter)的左子树,
* 那么这个ParentA’s Fathter就是当前节点Node的后继节点
* @param node
* @return
*/
private Node getParentFather(Node node) {
if(null != node.parent.parent.left && node.parent.value.compareTo(node.parent.parent.left.value) == 0){
return node.parent.parent;
}

return getParentFather(node.parent);
}


Client测试代码:

BinarySearchTree bst = new BinarySearchTree();
bst.add(50);
bst.add(29);
bst.add(8);
bst.add(2);
bst.add(5);
bst.add(4);
bst.add(3);
bst.add(44);
bst.add(77);
bst.add(82);
bst.add(10);
bst.add(1);
bst.add(11);
bst.add(12);
bst.add(13);

bst.traverse();
BinarySearchTree<Integer>.Node qNode = new BinarySearchTree<Integer>().new Node(new Integer(13));
BinarySearchTree.Node successorNode = bst.getSuccessorNode(bst.getOnEle(qNode));
System.out.println(qNode.value + " 的后继节点是:  "+successorNode.value);
//        bst.remove(new Integer(13));
bst.traverse();


输出结果:
13 的后继节点是:  29

bst-tree_introduce

Posted on 2019-06-06 | In 数据结构/算法

1.什么是BST树

Bst树又名二分搜索树,binary search tree,它是遵循一定规律的二叉树;

  • 1.二分搜索树是二叉树;
  • 2.二分搜索树每个节点的值:
    a.大于其左子树所有节点的值;
    b.小于其右子树所有节点的值;
  • 3.每一棵子树也是二分搜索树;

如图:

就是说每往一个根节点添加元素时,左孩子要比根节点小,右孩子要比根节点大,不允许元素重复(可选项);

2.手写一个基本的BST树

下面开始用java写一个Bst树,主要分为几步:

  • 基本节点
  • add元素流程
  • query元素流程 //todo
  • 遍历(先中后序)
  • 删除元素 //todo

另外补充下:为何说是”基本的”,因为还存在可优化的情况,但是不揉在一起,先把最基本的怼出来,下一小节再来考虑优化问题(基本流程,递归);

2.1.定义基本节点

定义好左孩子右孩子,根节点;

public class BinarySearchTree<T extends Comparable> {

Node root;
int size;

class Node {

Node left;
Node right;
T value = null;

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

}

}

2.2.add元素流程

1.如果root为空则直接new一个,并将值添加给该节点;
2.如果不为空,则将值添加进节点,根据之前描述的二分搜索树的特性,左孩子比根小,右孩子比根大,那么就涉及对比(这里用的java泛型+比较器的方式),那么就需要另开一个函数接受一个Node和新传进来的值进行对比,就是下面代码的私有方法nodeadd();

public class BinarySearchTree<T extends Comparable> {

......

class Node {
......
}

public void add(T value) {

if (root == null) {
root = new Node(value);//1
size++;
return;
} else {
nodeAdd(root, value);//2
}

}

/**
* @param currNode 当前根节点
* @param newValue 新插入元素
*/
/**
* 二分搜索树每个节点的值:
* a.大于其左子树所有节点的值;
* b.小于其右子树所有节点的值;
*/
private void nodeAdd(Node currRoot, T newValue) {

//无重复元素
if (currRoot.value.compareTo(newValue) == 0) {
return;
}

//compareTo 前一个元素和后一个元素比较--返回整数,1,0,-1;返回1表示大于,返回-1表示小于,返回0表示相等;
if (currRoot.value.compareTo(newValue) > 0) {//左插

//当前根节点大于插入值,且当前根节点的左子树为空,所以该值应该插入左子树
if (currRoot.left == null) {
currRoot.left = new Node(newValue);
size++;
return;
} else {
//当前根节点大于插入值,且当前根节点的左子树不为空,则递归到一次的左子树查询当中去
nodeAdd(currRoot.left, newValue);//递归
}
} else if (currRoot.value.compareTo(newValue) < 0) {//右插

//右插同理左插
if (currRoot.right == null) {
currRoot.right = new Node(newValue);
size++;
return;
} else {
nodeAdd(currRoot.right, newValue);//递归
}

}

}

}

2.3.add流程优化

......

private void nodeAdd(Node currRoot, T newValue) {

if (currRoot.value.compareTo(newValue) > 0) {//左插

//当前根节点大于插入值,且当前根节点的左子树为空,所以该值应该插入左子树
if (currRoot.left == null) {
currRoot.left = new Node(newValue);
size++;
return;
} else {
//当前根节点大于插入值,且当前根节点的左子树不为空,则递归到一次的左子树查询当中去
nodeAdd(currRoot.left, newValue);//递归
}
}
......
}

......

问题出在哪?为什么要优化?要优化哪儿?
1.终止条件臃肿
2.外部干预,外层调用的add方法会初始化树根节点root
3.没有访问到null节点(在访问之前就已经进行了判断)
综合起来就是”不美”; (“▔㉨▔)!

优化思路
主要解决矛盾:解除外部干预,终止条件简化;
考虑方向:让元素先到空节点,如果是空节点必然就插入元素作为新根,否则再进行递归
产生的问题:树结构的维护;

具体实现

public void add(T value) {
root = nodeAdd(root, value);
}

/**
* @param currRoot 当前根节点
* @param newValue 新插入元素
*/
private Node nodeAdd(Node currRoot, T newValue) {

if(currRoot == null){
size++;
return new Node(newValue);
}


if (currRoot.value.compareTo(newValue) > 0) {//左插
?=  nodeAdd(currRoot.left, newValue);//1
} else if (currRoot.value.compareTo(newValue) < 0) {//右插
?=  nodeAdd(currRoot.right, newValue);//递归
}

return currRoot;

}

如上代码是个未完成的代码,主要体现问题所在,主要是递归的时候返回根节点并没有和整棵树关联起来,比如:

  • 第一个元素进去,5,树根为空,new了一个Node返回并赋值给root,这一步没问题;
  • 第二个元素进去,1,树根是5不为空,判断为左插,这时候递归就有问题

啥问题?看注释1处,nodeAdd(currRoot.left, newValue),currRoot是5的left,为空,在递归调用中会新创建一个Node,这个Node返回给的是递归之前的函数,也就是说,它仅仅创建了一个对象,而这个对象并没有挂载到整棵树上;在该函数末尾return到currRoot5实际上本该插入的子树却没有插入,到下一个元素进来判断它的左子树还是为空;

之前不出问题是因为,之前的root是全局变量,它创建新node的时候就可以做子树关联,而这个写法在它递归时找到null节点创建的节点没有做父节点关联;

那么要做关联该怎么做?递归调用时遇见null元素返回的地方就是注释1处,我们只需要在?处加上父节点绑定即可,如下:


public void add(T value) {
root = nodeAdd(root, value);
}

/**
* @param currRoot 当前根节点
* @param newValue 新插入元素
*/
private Node nodeAdd(Node currRoot, T newValue) {

if(currRoot == null){
size++;
return new Node(newValue);
}

if (currRoot.value.compareTo(newValue) > 0) {//左插
currRoot.left = nodeAdd(currRoot.left, newValue);//递归
} else if (currRoot.value.compareTo(newValue) < 0) {//右插
currRoot.right = nodeAdd(currRoot.right, newValue);//递归
}

return currRoot;

}

2.4.遍历:(前中后序)遍历粗浅理解,以及递归实现

先中后序遍历主要是根据访问根节点时机来进行的,什么意思?

前序就是先访问根节点,再访问左节点(递归左子树),然后访问右节点(递归右子树);
中序就是先访问左节点(递归左子树),再访问根节点,然后访问右节点(递归右子树);
后序就是先访问右节点(递归右子树),再访问左节点(递归左子树),然后访问根节点;

等于就是先序就是先访问根,中序就是根在中间,后续就是根在最后,且左子树永远要比右子树更优先遍历;

贴上代码:



public class BinarySearchTree<T extends Comparable> {

......

class Node {
......
}

public void add(T value) {

......
}


private void nodeAdd(Node currRoot, T newValue) {
......
}

/**
* 暴露给用户
*/
public void traverse() {
traversePre(root);
}

/**
* 先序遍历
*/
private void traversePre(Node node) {
if (node == null)
return;

System.out.println(node.toString());//访问元素
traversePre(node.left);
traversePre(node.right);
}


/**
* 中序遍历
*/
private void traverseMid(Node node) {

if (node == null)
return;

traversePre(node.left);
System.out.println(node.toString());//访问元素
traversePre(node.right);
}


/**
* 后序遍历
*/
private void traverseAfter(Node node) {

if (node == null)
return;

traversePre(node.left);
traversePre(node.right);
System.out.println(node.toString());//访问元素
}
}

2.5.验证测试

在客户端内添加一波元素看看效果;

public class BstTest {

public static void main(String[] args) {

BinarySearchTree bst = new BinarySearchTree();
bst.add(5);
bst.add(1);
bst.add(3);
bst.add(6);
bst.add(6);
bst.add(7);
bst.add(11);
bst.add(1);

bst.traverse();
}
}

推测一下数据应该有的样子,然后再看输出的结果对不对的上;

打印结果:5,1,3,6,7,11

value == 5:::left value == 1__right value == 6
value == 1:::left value ==  null __right value == 3
value == 3:::left value ==  null __right value ==  null 
value == 6:::left value ==  null __right value == 7
value == 7:::left value ==  null __right value == 11
value == 11:::left value ==  null __right value ==  null 

可以看见结果是能对的上的,但是,这只是最简单的理解;

3.深入理解BST树的遍历

3.1.(前中后序)遍历深入理解

之前讨论的前中后序遍历重点关注的只是结果,这一小节准备揪出这个遍历的本质,即当我们去遍历这个树时,每个节点具体的访问顺序是怎样的,这个就有点像是程序debug打断点,一步步的走;

还是这个树:

先说结论:在递归的前提下,每个节点都会被访问三次,用先序遍历举例,这个树实际节点访问的顺序是;

⑤①①③③③①⑤⑥⑥⑦⑦⑪⑪⑪⑦⑥⑤

一共6个元素,每个元素访问3次,总共18个步骤,接下来将一个个分析每一步的理由:

⑤:第一个元素开始,访问5,
①:由于是先序(后面将不再强调先序),访问5的左子树,于是来到1
①:1接着访问1点左子树,由于1没有左子树(null),于是返回1
③:接着访问1的右子树,就来到了3
③:接着访问3的左子树,为空,返回3
③:接着访问3的右子树,为空,返回3
①:3访问完了,返回父亲节点,也就是1
⑤:1访问完了,返回父亲节点,也就是树根节点5
⑥:5的左子树访问完了,于是访问5的右子树,于是来到6
⑥:6访问左子树,发现为空,返回自己,也就是6
⑦:6访问右子树,于是来到7
⑦:7访问左子树,发现为空,于是返回自己,也就是7
⑪:7访问右子树,于是来到11
⑪:11访问自己的左子树,发现为空,返回自己,也就是11
⑪:11访问自己的右子树,发现为空,返回自己,也就是11
⑦:11遍历完成之后,返回自己的父亲节点,也就是7
⑥:7遍历完成之后,返回自己的父亲节点,也就是6
⑤:6遍历完成之后,返回自己的父亲节点,也就是树根节点5,整个遍历结束;

在理解了每个节点的具体访问步骤之后,我们知道每个元素都会访问3次,也就是说,每个节点都会第一次被访问,第二次被访问,第三次被访问;

而先序列遍历就是在节点第一次被访问的时候进行数据处理(比如打印自己的值);
中序遍历就是在节点第二次被访问的时候进行数据处理,同样后序遍历就是在节点第三次被访问的时候进行数据处理,所以我们发现不同的遍历方式出来的值顺序不一样;

知道了先序的这个流程之后,中后序根这个一个意思,就不写了,验证这个可以用后面贴出的Demo代码进行测试,这里也不赘述了;

3.2.(前中后序)遍历的非递归实现

非递归实现的核心思想就是用”循环+栈来替代递归”;
栈是后进先出,比如一个最简单的树:

⑤
/\
①  ⑦

用先序举例,访问结果是517,那么stack实现的流程就是:

//伪码
stack.push(5);
stack.pop();
stack.push(7);
stack.push(1);
stack.pop();
stack.pop();

理解了这一层之后来写代码:

/**
* 先序遍历,非递归
*/
private void traversePre(Node rootnode) {

Stack<Node> stack = new Stack<>();
stack.push(rootnode);

while(!stack.isEmpty()){
Node currNode = stack.pop();

if(currNode == null)
return;
else
System.out.println(currNode);//访问元素

if(null != currNode.right)
stack.push(currNode.right);

if(null != currNode.left)
stack.push(currNode.left);
}

}

根据之前的结果结合这个代码来反推算一算:⑤①③⑥⑦⑪

第一趟:

  • 5先入栈
  • stack不为空,进入循环,从stack内拿出5,打印5(访问数据)
  • 5的right,6,不为空,入栈
  • 5的left,1,不为空,入栈
  • 本趟结果:⑤
  • 栈内情况:
    1
    6

第二趟:

  • stack不为空,进入循环,从stack内拿,不为空,拿到1,打印
  • 1的right,3,不为空,入栈
  • 1的left,为空,什么都不做
  • 本趟结果:①
  • 栈内情况:
    3
    6

第三趟:

  • stack不为空,进入循环,从stack内拿,不为空,拿到3,打印
  • 3的right,为空,什么都不做
  • 3的left,为空,什么都不做
  • 本趟结果:③
  • 栈内情况:
    6

第四趟:

  • stack不为空,进入循环,从stack内拿,不为空,拿到6,打印
  • 6的right,7,不为空,入栈
  • 6的left,为空,什么都不做
  • 本趟结果:⑥
  • 栈内情况:
    7

第五趟:

  • stack不为空,进入循环,从stack内拿,不为空,拿到7,打印
  • 7的right,11,不为空,入栈
  • 7的left,为空,什么都不做
  • 本趟结果:⑦
  • 栈内情况:
    11

第六趟:

  • stack不为空,进入循环,从stack内拿,不为空,拿到11,打印
  • 11的right,为空,什么都不做
  • 11的left,为空,什么都不做
  • 本趟结果:⑪
  • 栈内情况:
    无

第七趟:

  • stack为空,结束循环;

对比打印结果一致:

//递归先序
value == 5:::left value == 1__right value == 6
value == 1:::left value ==  null __right value == 3
value == 3:::left value ==  null __right value ==  null 
value == 6:::left value ==  null __right value == 7
value == 7:::left value ==  null __right value == 11
value == 11:::left value ==  null __right value ==  null 

//非递归先序
value == 5:::left value == 1__right value == 6
value == 1:::left value ==  null __right value == 3
value == 3:::left value ==  null __right value ==  null 
value == 6:::left value ==  null __right value == 7
value == 7:::left value ==  null __right value == 11
value == 11:::left value ==  null __right value ==  null 

在验证了这个流程之后,中后序,无非就是调整入栈出栈时机的问题;

总结一下就是:非递归遍历树借助了辅助容器(stack)来实现的,当要压进一个元素的意思就是我们即将访问这个元素;然后压栈的时候主要它先进后出的特性,顺序要反着压;

另外,我在想一个问题,bst树遍历非递归实现有何实际意义?
后来度娘了一波,似乎是和性能有关系,意思就是递归耗性能:

递归和非递归只是解决问题的方法的不同,本质还是一样的。
2. 递归算法相对于非递归算法来说效率通常都会更低
2.1 递归算法会有更多的资源需要压栈和出栈操作(不仅仅是参数,还有函数地址等)
2.2 由于编译器对附加的一些栈保护机制会导致递归执行的更加低效
3. 使用循环代替递归算法,通常可以获得更好的执行效率和空间效率,在二叉树层次较深的情况下,采用非递归方式遍历能够有效的提升遍历的性能。

4.Demo

https://github.com/zj614android/designPattern/tree/master/app/src/main/java/com/zj/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%A0%91/bst

Red Dragon

Red Dragon

8 posts
1 categories
5 tags
© 2020 Red Dragon
Powered by Hexo v3.8.0
|
Theme – NexT.Gemini v7.1.2