搜索二叉树——基本概念
二叉搜索树又称 二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的 左右子树也分别为二叉搜索树
注意：二叉搜索树中没有重复的元素
如下图为一个二叉搜索树
搜索二叉树——基本属性
二叉树是由一个一个节点组成的，先定义好节点的属性
代码实现：
public class Node{
int key;//节点值
Node left;//左孩子节点
Node right;//右孩子节点
public Node(int key){//重写一下节点的构造方法
this.key = key;
}
}
Node root = null;//一开始根节点为空
搜索二叉树——查找节点
查找过程：
- 拿着待查元素和根节点比较；
- 如果比根节点小，继续在左子树中查找；
- 如果比根节点大，继续在右子树中查找；
- 如果当前元素查找到null也没找到，说明该元素不存在。
代码实现：
/**
* 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
* @param key
* @return
*/
public Node search(int key){
Node cur = root;//cur从root开始走
while(cur != null){
if(cur.key == key){//如果cur的值与key相等，则返回cur
return cur;
}else if(key > cur.key){//key值比cur的值大，cur往右节点走
cur = cur.right;
}else if(key < cur.key){//key值比cur的值小，cur往左节点走
cur = cur.left;
}
}
return null;//root为空，或者二叉树里没有这个节点，返回空值
}
搜索二叉树——插入节点
插入过程：
- 如果树是空树，即根== null，直接插入即可，返回true
- 如果树不是空树，按照 查找逻辑（大的放左边，小的放右边） 确定插入位置，插入新结点
注意：最后确定的插入位置一定是叶子节点
代码实现：
/**
* 插入
* @param key
* @return true 表示插入成功, false 表示插入失败
*/
public Boolean insert(int key){
if(root == null){//如果根节点空，则第一个节点就是根节点
root = new Node(key);
return true;
}
Node cur = root;//用cur从root位置开始往下走
Node parent = null;//需要用一个parent节点来记录上一个节点
//通过while循环来找插入位置
while(cur != null){
if (key == cur.key){
return false;//如果二叉树里已经有这个值，就无法插入
}
else if (key < cur.key){//key比cur的值小，说明要插到左边
parent = cur;//记录上一个节点
cur = cur.left;//cur往左走
}
else if (key > cur.key){//key比cur的值大，说明要插到右边
parent = cur;//记录上一个节点
cur = cur.right;//cur往右走
}
}
//while走完了，说明是时候插入节点了，因为我们插入节点的位置一定是叶子节点的位置
//这就需要用到parent了
Node node = new Node(key);//创建要插入的新节点
if (node.key > parent.key){//比parent值大放右边
parent.right = node;
}else {
parent.left = node;//反之放左边
}
return true;//插入成功
}
搜索二叉树——删除节点
设待删除结点为 cur, 待删除结点的双亲结点为 parent，删除节点的关键在于对多种情况的分析
- cur.left == null 待删除节点只有右子树
（这种情况下删哪个点，就将其右子树接到这个点的父节点后边）
2.cur.right == null 待删除节点 只有左子树
（这种情况下删哪个点，就将其左子树接到这个点的父节点后边）
- cur.left != null && cur.right != null 待删除节点左右子树都存在
（需要使用替换法进行删除，即在它的右子树中寻找最小值结点，用它的值填补到被删除节点中，再来处理该结点的删除问题，关键就在于这个寻找最小值替代这一步）
总而言之，这第三种情况处理方法就是，从待删除点的右树里找最小值来替换待删除点，然后将替罪羊节点的右树接到替罪羊节点的父节点后边即可，注意点就是替罪羊节点是在父节点左边还是右边
代码实现：
/**
* 删除成功返回 true，失败返回 false
* @param key
* @return
*/
public void removeKey(int key) {
if(root == null) {
return;
}
Node cur = root;
Node parent = null;
while (cur != null) {
if(cur.key == key) {
remove(parent,cur);
return;
}else if(cur.key < key){
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
}
private void remove(Node parent, Node cur) {
if (cur.left == null){//删除只有右孩子的节点
if (cur == root){//要删除的点是根节点
root = cur.right;
}
else if (cur == parent.left){//要删除的点在父亲节点左边
parent.left = cur.right;
}
else if (cur == parent.right){//要删除的点在父亲节点右边
parent.right = cur.right;
}
}
else if(cur.right == null){//删除只有左孩子的节点
if(cur == root) {//要删除的点是根节点
root = cur.left;
}
else if(cur == parent.left) {//要删除的点在父亲节点左边
parent.left = cur.left;
}
else if(cur == parent.right){//要删除的点在父亲节点右边
parent.right = cur.left;
}
}
else {
Node target = cur.right;
Node targetParent = cur;
//找替罪羊target，找右树的最小左子树
while(target.left != null){
targetParent = target;
target = target.left;
}
cur.key = target.key;
if(target == targetParent.left){//如果当前目标值是父节点的左孩子
targetParent.left = target.right;//就把目标节点的右孩子接到父节点的左边
}
else if(target == targetParent.right){//如果当前目标值是父节点的右孩子
targetParent.right = target.right;//就把目标节点的右孩子接到父节点的右边
}
}
}
