1.概念
a.是个二叉树(每个节点最多有两个子节点)
b.对于这棵树中的节点的节点值
左子树中的所有节点值
二分搜索树中一般不考虑值相等的情况(元素不重复)JDK中的搜索树就不存在相同的值(TreeMap-key)

最大特点:也是判断是否是搜索树的方法
对该树进行中序遍历,就可以得到一个升序集合0 1 2 3 4 5 6 7 8 9
在一个有序区间上进行二分查找的时间复杂度? logn不断将集合/2/2 / 2 ==1为止logN
logN =》联想到"树"
2.重点操作

FilePond 是一个 JavaScript 文件上传库,支持通过拖拽、粘贴和 API 方式处理文件、目录、URL 和 Data URI。它包含内置的图像优化功能、异步分块上传功能,并提供了适用于 React、Vue、Angular 和 Svelte 的适配器。
当删除58时,此节点左右子树都不为空
Hibbard Deletion 1962
在BST中删除一个左右子树都存在的节点
找到当前以58为根节点的前驱或者后继节点作为删除后的新节点
前驱:在以58为根的BST中最后一个小于58的节点->53
后继:在以58为根的BST中第一个大于58的节点->59
当我们使用后继节点时,先连removeMin(root.right),在连root.left
TreeNode successor = findMin(root.right); successor.right = removeMin(root.right); successor.left = root.left;
3.完整代码
import java.util.NoSuchElementException;
/**
* 基于整型的
* 普通的二分搜索树
*/
public class BST {
private class TreeNode{
private int val;
private TreeNode left;
private TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
private int size;
private TreeNode root;
/**
* 向以root为根的BST中插入一个新的结点val
* @param val
*/
public void add(int val){
root = add(root,val);
}
private TreeNode add(TreeNode root, int val) {
if(root == null){
//创建一个新节点
TreeNode newNode = new TreeNode(val);
size++;
return newNode;
}
//左子树插入
if(val root.val){
root.right = add(root.right,val);
}
return root;
}
/**
* 判断当前以root为根的BST中是否包含了val
* @param val
* @return
*/
public boolean contains(int val){
return contains(root,val);
}
private boolean contains(TreeNode root, int val) {
if(root == null){
return false;
}
if(val == root.val){
//找到了
return true;
}else if(val root.val){
root.right = removeValue(root.right,value);
return root;
}else {
//此时value == root.value
if(root.left == null){
//删除最小数
TreeNode right = root.right;
root = root.right = null;
size--;
return right;
}
if(root.right == null){
//删除最大数
TreeNode left = root.left;
root = root.left =null;
size--;
return left;
}
//找到当前该删除节点的前驱或者后继节点作为删除后的新节点
//当我们使用后继节点时,先连removeMin(root.right),在连root.left
TreeNode successor = findMin(root.right);
successor.right = removeMin(root.right);
successor.left = root.left;
return successor;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
generateBSTString(root,0,sb);
return sb.toString();
}
//直观打印,可以看到树的深度
private void generateBSTString(TreeNode root, int height, StringBuilder sb) {
if(root == null){
sb.append(generateHeightString(height)).append("NULL\n");
return;
}
sb.append(generateHeightString(height)).append(root.val).append("\n");
generateBSTString(root.left,height+1,sb);
generateBSTString(root.right,height+1,sb);
}
private String generateHeightString(int height) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i
Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南










