数据结构——二叉排序树（BST）_数据结构bst_木易三水良的博客-程序员秘密
技术标签： 数据结构
基本介绍：
- 二叉排序树BST（Binary Sort(Search) Tree）,对于二叉排序树的任何一个非叶子节点要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
- 特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点，如果二叉排序树中存在节点值相同的时候，示例代码中给出的获取节点的方法，只会返回第一个相同值的节点，这就致使在进行删除操作的时候会报栈溢出（StackOverflowError），所以，二叉排序中尽量避免值相同的情况
针对数组｛7，3，10，12，5，1，9｝对应的排序二叉树如下：
- BST添加（添加逻辑详见示例代码）完成后，通过中序遍历一定是有序的。
- BST的删除操作较复杂，逻辑如下：
示例代码
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {
8, 4, 5, 7, 3, 33, 18, 16,4};
// int[] arr = { 9, 6,12,33};
BinarySortTree binarySortTree = new BinarySortTree();
for (int item : arr) {
binarySortTree.addNode(new Node(item));
}
binarySortTree.infixOrder();
Node node = binarySortTree.get(10);
System.out.println("查找的节点：" + node);
node = binarySortTree.getParent(56);
System.out.println("查找节点的父节点：" + node);
for (int item : arr) {
binarySortTree.delNode(item);
}
System.out.println("删除节点后：");
binarySortTree.infixOrder();
}
}
@Data
class BinarySortTree {
private Node root;
/**
* 中序遍历
*/
public void infixOrder() {
if (root == null) {
System.out.println("空树，无法进行遍历");
} else {
root.infixOrder();
}
}
/**
* 添加节点
*
* @param node
*/
public void addNode(Node node) {
if (node == null) {
return;
}
/*如果根节点为空，待添加的节点直接加到根节点即可*/
if (root == null) {
root = node;
} else {
root.add(node);
}
}
/**
* 查找指定节点
*
* @param value
* @return
*/
public Node get(int value) {
if (root == null) {
return null;
}
return root.get(value);
}
/**
* 查找指定节点的父节点
*
* @param value
* @return
*/
public Node getParent(int value) {
if (root == null) {
return null;
}
return root.getParent(value);
}
/**
* 删除节点
*
* @param value
*/
public void delNode(int value) {
/*如果节点为空，直接返回*/
if (root == null) {
return;
}
/*获取到待删除的节点*/
Node targetNode = get(value);
/*如果未查找到待删除节点，待删除节点为空，直接返回*/
if (targetNode == null) {
return;
}
/*如果root没有子节点，说明root节点就是待删除节点*/
if (root.getLeft() == null && root.getRight() == null) {
root = null;
return;
}
/*获取到待删除节点的父节点*/
Node parent = getParent(value);
/*待删除节点是叶子节点*/
if (targetNode.getLeft() == null && targetNode.getRight() == null) {
/*判断待删除节点是父节点的左子节点还是右子节点*/
if (parent.getLeft() != null && parent.getLeft().getValue() == value) {
parent.setLeft(null);
} else if (parent.getRight() != null && parent.getRight().getValue() == value) {
parent.setRight(null);
}
/*待删除节点右左右两个子节点*/
} else if (targetNode.getLeft() != null && targetNode.getRight() != null) {
int min = delRightTreeMin(targetNode.getRight());
targetNode.setValue(min);
/*待删除节点只有左或右一个子节点*/
} else {
/*待删除节点只有一个左子节点*/
if (targetNode.getLeft() != null) {
/*如果父节点为NULL，表示待删除节点就是root节点*/
if (parent == null) {
/*直接将root节点指向待删除节点的子节点即可*/
root = targetNode.getLeft();
} else {
/*判断待删除节点是父节点的左子节点还是右子节点*/
if (parent.getLeft() != null && parent.getLeft().getValue() == value) {
parent.setLeft(targetNode.getLeft());
} else if (parent.getRight() != null && parent.getRight().getValue() == value) {
parent.setRight(targetNode.getLeft());
}
}
/*待删除节点只有个右子节点*/
} else {
/*如果父节点为NULL，表示待删除节点就是root节点*/
if (parent == null) {
/*直接将root节点指向待删除节点的子节点即可*/
root = targetNode.getRight();
} else {
/*判断待删除节点是父节点的左子节点还是右子节点*/
if (parent.getLeft() != null && parent.getLeft().getValue() == value) {
parent.setLeft(targetNode.getRight());
} else if (parent.getRight() != null && parent.getRight().getValue() == value) {
parent.setRight(targetNode.getRight());
}
}
}
}
}
/**
* 1、返回以node为根节点的二叉排序树的最小节点的值
* 2、删除node为根节点的二叉排序树的最小节点
*
* @param node 作为二叉树根节点的节点
* @return 返回最小值
*/
public int delRightTreeMin(Node node) {
if (node == null) {
throw new RuntimeException("节点不能为空！");
}
Node targetNode = node;
/*向左子树递归查找，直到叶子节点*/
while (targetNode.getLeft() != null) {
targetNode = targetNode.getLeft();
}
/*此时 targetNode就指向了最小节点*/
delNode(targetNode.getValue());
return targetNode.getValue();
}
/**
* 1、返回以node为根节点的二叉排序树的最大节点的值
* 2、删除node为根节点的二叉排序树的最大节点
*
* @param node 作为二叉树根节点的节点
* @return 返回最大值
*/
public int delLeftTreeMax(Node node) {
if (node == null) {
throw new RuntimeException("节点不能为空！");
}
Node targetNode = node;
/*向右子树递归查找，直到叶子节点*/
while (targetNode.getRight() != null) {
targetNode = targetNode.getRight();
}
/*此时 targetNode就指向了最大节点*/
delNode(targetNode.getValue());
return targetNode.getValue();
}
}
@Data
class Node {
private int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
/**
* 中序遍历
*/
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
/**
* 添加节点
*
* @param node
*/
public void add(Node node) {
/*如果当前节点的值大于待添加节点的值，则待添加节点应加入到当前节点的左子树*/
if (node.value < 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);
}
}
}
/**
* 根据值获取节点
* 切记：如果值相同的时候返回的都是第一值的节点，
*
* @param value 值
* @return 如果找到就返回该节点，未找到返回NULL
*/
public Node get(int value) {
/*找到该节点*/
if (this.value == value) {
return this;
}
/*如果待查找的值小于当前节点的值，递归向左子树查找*/
if (value < this.value) {
if (this.left == null) {
return null;
}
return this.left.get(value);
/**
* 如果待查找的值大于等于当前节点的值，递归向右子树查找
* 如果在添加的时候将等于节点放在左子树，这是等于将放在向左递归查找中
*/
} else {
if (this.right == null) {
return null;
}
return this.right.get(value);
}
}
public Node getParent(int value) {
/*当前节点就是待查找值的父节点*/
if ((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
}
if (value < this.value && this.left != null) {
return this.left.getParent(value);
}
if (value >= this.value && this.right != null) {
return this.right.getParent(value);
}
return null;
}
}
智能推荐
Nosql介绍（一）_沉泽·的博客-程序员秘密
一、Nosql概述1.1 为什么使用Nosql1、单机Mysql时代90年代,一个网站的访问量一般不会太大，单个数据库完全够用。随着用户增多，网站出现以下问题数据量增加到一定程度，单机数据库就放不下了数据的索引（B+ Tree）,一个机器内存也存放不下访问量变大后（读写混合），一台服务器承受不住。2、Memcached(缓存) + Mysql + 垂直拆分（读写分离）网站80%的情况都是在读，每次都要去查询数据库的话就十分的麻烦！所以说我们希望减轻数据库的压力，我们可以使用缓存来保证效
程序猿的10层楼_iOS_huyajun的博客-程序员秘密
自西方文艺复兴以来，中国在自然科学方面落后西方很多，软件领域也不例外。当然现在中国的许多程序员们对此可能有许多不同的意见，有些人认为中国的程序员水平远落后于西方，有些则认为中国的程序员个人能力并不比西方的程序员差，只是整个软件产业落后而已。 那么，到底中国的程序员水平比西方程序员水平差，还是中国有许多优秀的程序员达到或超过了西方程序员同等水平呢？要解决这个问题，必须先知道程序员有多少种技
Android ListView拖动效果（互换，删除，插入）_android listview 拖动_赤耳A狼的博客-程序员秘密
对于ListView的拖动效果，其实也没什么神秘的，在android packages/apps/Music中例子中就有这样的效果实现，这是android系统自带的。如果大家没有这部分源码，最后的实例我会一起打包放在rar文件中，有兴趣的可以自己读一下。 说起这个拖动效果，其实以前也做过，不过不是用android自己的实现方法，而是自己使用逻辑实现的。看了Music那部分代码之后，发现其实也
数据库管理及增删改查基本操作小结_weixin_30376453的博客-程序员秘密
一. 数据库查询语言1）查询employees数据表中的所有数据记录:select * from employees;2）查询employees表中的employee_id, first_name记录：select employee_id,first_name from employees;3）查询test表中score列数据的所有平均值：select AV...
解决maven项目中pom.xml添加依赖文件的繁琐操作的办法_小城里的小陈的博客-程序员秘密
创建一个maven工程项目，命名为pomModule，该工程作为以后SSM工程项目的基础，我们对该工程只配置其pom.xml文件，即添加SSM框架所需要的全部jar包,pom.xml的代码如下：&amp;lt;project xmlns=&quot;http://maven.apache.org/POM/4.0.0&quot; xmlns:xsi=&quot;http://www.w3.org/2001/XMLSchema-inst...
VMware中的虚拟机和本地物理机共享文件_小白啥时候能进阶成功的博客-程序员秘密
1.虚拟机设置：共享文件夹->添加2.安装VMware-tools 设置->重新安装VMware-tools，在linux中找到压缩包->复制到其他目录解压缩后->执行vmware.pl一路yes,（不要默认的选项，看清提示）...
随便推点
Java进阶之路——从初级程序员到架构师，从小工到专家(转载)_Simon站起来的博客-程序员秘密
怎样学习才能从一名Java初级程序员成长为一名合格的架构师，或者说一名合格的架构师应该有怎样的技术知识体系，这是不仅一个刚刚踏入职场的初级程序员也是工作三五年之后开始迷茫的老程序员经常会问到的问题。希望这篇文章会是你看到过的最全面最权威的回答。一： 编程基础不管是C还是C++，不管是Java还是PHP，想成为一名合格的程序员，基本的数据结构和算法基础还是要有的。下面几篇文章从思想到
语音合成TTS | AI产品经理需要了解的AI技术概念_mandagod的博客-程序员秘密
TTS（Text-To-Speech，语音合成），目前是一个“小而美”的AI领域，但我个人觉得非常有意思，感觉TTS在未来会被行业真正重视起来，并且会出现做得不错的创业公司。本文，是我收集了很多线上/线下的相关信息后，提炼出的AI产品经理“最必要”了解的TTS技术知识和行业现状（多了没必要，少了又不足以入门、准备面试或工作实战）；不仅帮大家节省了时间，更是过滤了很多无用信息和过于技术的内容。...
【C/C++】程序在main之前/之后执行代码|main之前打印编译日期_bdview的博客-程序员秘密
目录 程序在main之前/之后执行代码 打印编译日期 程序在main之前/之后执行代码 http://www.mamicode.com/info-detail-2087871.html 在main函数之前，会有一系列初始化的操作，这样的操作通常是由链接器等完成的。 具体说来，程序最早执行的函数其实并不是main ，比如在windows中...
Pytorch教程：CIFAR-10分类_pytorch cifar100分类_LittleEmperor的博客-程序员秘密
学教程、自己敲、融会贯通# coding=utf-8import torchimport torchvisionimport torchvision.transforms as transformstransform = transforms.Compose( [transforms.ToTensor(), transforms.Normalize((0.5, 0....
OFDM基础与多径信道Matlab仿真_ofdm多径信道_王川云泽的博客-程序员秘密
原理参考文章：OFDM的基本原理剖析 基于matlab的ofdm系统设计与仿真…程序%% 参数设置close all;clc;n_c=4; %子载波数 N=4; %IFFT数 M=4; %psk进制数l_cp=4; %保护间隔长度 n_ofdm=100000
rac库grid目录权限(6751)导致数据库宕机案例 此方法仅用于紧急救助_weixin_34067980的博客-程序员秘密
问题： 我的rac环境不小心通过chown命令改变了/u01目录及其子目录的权限，导致rac节点2数据库宕掉，sqlplus下打开数据库报错如下： [[email protected] ~]$ sqlplus / as sysdba SQL*Plus: Release 11.2.0.4.0 Production on Fri Mar 25 19:53:58 2016 Copyright (c) 1982, ...