一、概念
一、概念
二叉搜索树又称二叉排序树，是一种可以进行快速查询的二叉树类型。
所具有的性质：
- 若节点不为空，根节点的值大于其左子树任一节点的值。
- 若节点不为空，根节点的值小于其右子树任一节点的值。
- 任一节点的左右子树均为二叉搜索树
其性质的特点在于中序遍历的结果一定是升序的（如下图）
二、基本操作实现
准备工作：
创建二叉树结点，以及根节点：
//创建二叉树结点
public static class Node{
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
//根节点
private static Node root =null;
1、查找元素
思路：结合二叉搜索树的特性，节点的左树节点值都比其小，右树节点都比其大的特性，我们从根节点的值与寻找元素比较，如果根节点小就向右树进行寻找，反之向左树寻找。
//查询元素
public Node search(int key) {
if (root == null) {
return null;
}
//定义一个遍历节点
Node cur = root;
while (cur != null) {
//寻找到返回节点
if (key == cur.val) {
return cur;
//节点值小时向右树寻找
}else if (key > cur.val) {
cur = cur.right;
//节点值大时向左树寻找
} else {
cur = cur.left;
}
}
return null;
}
2、插入元素
思路：同样结合二叉搜索树的特性，节点的左树节点值都比其小，右树节点都比其大的特性。用cur节点去遍历二叉树，如果插入元素大于节点值就向树的右边遍历，反之向左边遍历。找到合适的位置即可（插入的元素一定都是放在叶子节点上）
为什么插入的元素一定在叶子节点上呢？
这里的8是我们插入的元素，为什么会放在叶子节点上？是因为我们这个元素要不是比节点小要不就是大（二叉搜索树不可以包含相同的元素）并且不会存在大小相同的元素，那么他就会一直遍历下去寻找要插入的位置直到叶子节点结束（相对于叶子节点要不大就放在叶子右边要不小就放在叶子左边）
public boolean insert(int key) {
if (root == null) {
root = new Node(key);
return true;
}
//cur为遍历节点
Node cur = root;
//因为cur一直遍历最后会变成null无法找到上一个节点
//所以创建一个parent标记cur上一个节点
Node parent = null;
while (cur != null) {
//插入元素比节点值大向右遍历
if (cur.val > key) {
parent = cur;
cur = cur.left;
//插入元素比节点值小向左遍历
} else if (cur.val < key) {
parent = cur;
cur = cur.right;
} else return false;
}
Node node = new Node(key);
if (parent.val < key) {
parent.right = node;
} else {
parent.left = node;
}
return true;
}
三、删除元素
所要考虑的问题：
一、所要删除的元素需要先找到这个节点所在的位置
二、分情况讨论所要删除元素左右树的情况（是否为null）
三、如果左右树都不为null，删除节点位置应该置为什么？
1.1、寻找所要删除的节点
思路：我们需要遍历二叉搜索树，寻找所要找的节点记录下来，并且记录下它的上一个节点（因为在删除当前节点后，需要让上一个节点与删除节点的下一个节点做链接）。如果找到这个节点就调用removeNode方法去做我们的删除节点操作。
public void remove(int key) {
//遍历节点
Node cur = root;
//遍历节点的上一个节点
Node parent = null;
while (cur != null) {
if (cur.val < key) {
parent = cur;
cur = cur.right;
} else if (cur.val >key) {
parent = cur;
cur = cur.left;
} else {
removeNode(cur,parent);
System.out.println(key+"所在结点删除成功");
return;
}
}
}
2.1、讨论删除节点左右树的情况
所有情况：
1、删除节点的左节点为空（可能为根节点）
if (cur.left == null) {
if (cur == root) {
root = root.right;
} else if(cur == parent.left) {
parent.left = cur.right;
} else {
parent.right = cur.right;
}2、删除节点的右节点为空（可能为根节点）
if (cur.right == null) {
if (cur == root) {
root = root.left;
} else if (cur == parent.left) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}3、删除节点左右树不为空（可能为根节点）
替代的节点只能是：
删除节点左树中最大的节点（最右下边的节点）
删除节点右数中最小的节点（最左下的节点）
先上代码下面详解
Node tParent = cur;
Node t = cur.right;
while (t.left != null) {
tParent = t;
t = t.left;
}
cur.val = t.val;
if (tParent.right == t) {
tParent.right = t.right;
} else {
tParent.left = t.right;
}4、删除节点为null（不存在）
if (cur==null) {
return;
}删除节点左右树不为空的情况是我们最难理解的。先看下面的图
先看7和11的位置。7是 删除节点9作数中最大值的节点，11是删除节点9的右树中最小值的节点。
替代的节点只能是：
删除节点左树中最大的节点（最右下边的节点）
删除节点右数中最小的节点（最左下的节点）
因为节点的左数比其都小，右树都比其大的特性（仔细理解这个话）。只有这两个与删除节点最近值的节点才能代替删除的节点。
完整代码：
public class BinarySearchTree {
public static void main(String[] args) {
BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(8);
binarySearchTree.insert(12);
binarySearchTree.insert(3);
binarySearchTree.insert(6);
binarySearchTree.insert(9);
binarySearchTree.insert(1);
binarySearchTree.insert(13);
System.out.println();
binarySearchTree.order(root);
binarySearchTree.remove(8);
binarySearchTree.order(root);
}
public static class Node{
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
//根节点
private static Node root =null;
//插入元素
/**
*
* @param key 搜索树的性质不能有重复的值
* @return 是否成功
*/
public boolean insert(int key) {
if (root == null) {
root = new Node(key);
return true;
}
//cur为遍历节点
Node cur = root;
//因为cur一直遍历最后会变成null无法找到上一个节点
//所以创建一个parent标记cur上一个节点
Node parent = null;
while (cur != null) {
//插入元素比节点值大向右遍历
if (cur.val > key) {
parent = cur;
cur = cur.left;
//插入元素比节点值小向左遍历
} else if (cur.val < key) {
parent = cur;
cur = cur.right;
} else return false;
}
Node node = new Node(key);
if (parent.val < key) {
parent.right = node;
} else {
parent.left = node;
}
return true;
}
//查询元素
public Node search(int key) {
if (root == null) {
return null;
}
//定义一个遍历节点
Node cur = root;
while (cur != null) {
//寻找到返回节点
if (key == cur.val) {
return cur;
//节点值小时向右树寻找
}else if (key > cur.val) {
cur = cur.right;
//节点值大时向左树寻找
} else {
cur = cur.left;
}
}
return null;
}
public void order(Node node) {
if (node == null) {
return;
}
order(node.left);
System.out.print(node.val+" ");
order(node.right);
}
//删除元素
public void remove(int key) {
//遍历节点
Node cur = root;
//遍历节点的上一个节点
Node parent = null;
while (cur != null) {
if (cur.val < key) {
parent = cur;
cur = cur.right;
} else if (cur.val >key) {
parent = cur;
cur = cur.left;
} else {
removeNode(cur,parent);
System.out.println(key+"所在结点删除成功");
return;
}
}
}
public void removeNode(Node cur,Node parent) {
//删除元素左边为null
if (cur==null) {
return;
}
if (cur.left == null) {
if (cur == root) {
root = root.right;
} else if(cur == parent.left) {
parent.left = cur.right;
} else {
parent.right = cur.right;
}
} else if (cur.right == null) {
if (cur == root) {
root = root.left;
} else if (cur == parent.left) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
} else {
Node tParent = cur;
Node t = cur.right;
while (t.left != null) {
tParent = t;
t = t.left;
}
cur.val = t.val;
if (tParent.right == t) {
tParent.right = t.right;
} else {
tParent.left = t.right;
}
}
}
}