关于自定义二分排序树的删除节点的逻辑还是需要屡清楚！！！！
删除二分搜索树任意节点分四种情况：
1.删除的节点有左右子树
2.删除的节点只有左子树
3.删除的节点只有右子树
4.删除的节点左右子树都没有
在第一种条件下：需要遍历到待删除节点的 右子树中的最小值
package Map;
/**
* 支持泛型 此时key是可以比较的
* extends Comparable
*
* @Author: lixwu
* @Data : 2019/2/4 17:44
*/
public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {
/**
* 定义节点 及 节点多的初始化
*/
public class Node {
public K key;
public V value;
public Node left, right;
//构造函数就是用来初始化的
public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
}
}
private Node root;
private int size;
/**
* 类的构造方法
*/
public BSTMap() {
root = null;
size = 0;
}
/**
* 需要采用递归的方法
*
* @param key
* @param value
*/
@Override
public void add(K key, V value) {
root = add(root, key, value);
}
//向node为根的二分搜索树中插入元素（KEY,VALUE)采用递归算法
//返回新节点后二分搜索树中的根
private Node add(Node node, K key, V value) {
//对于递归到底的情况
if (node == null) {
size++;
return new Node(key, value);
}
//没有递归到底
if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, value);
} else if (key.compareTo(node.key) > 0) {
node.right = add(node.right, key, value);
} else {//key.compareTo(node.key) ==0;
node.value = value;
}
return node;
}
private Node getNode(Node node, K key) {
/**
* 根节点为空
*/
if (node == null) {
return null;
}
/**
* 如果根节点不为空
*/
if (key.compareTo(node.key) == 0) {
return node;
} else if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else{
return getNode(node.right, key);
}
}
@Override
public boolean contains(K key) {
return false;
}
/**
* 传入的根节点 寻找key
* 所有的逻辑都是从根节点开始的
* 从根节点开始遍历 查找链表中的元素
*
* @param key
* @return
*/
@Override
public V get(K key) {
//设计是需要传入根节点 及 指定的 key
Node node = getNode(root, key);
return node == null ? null : node.value;
}
/**
* 更改指定key的节点中保存的数据
* <p>
* 边界条件是真的烦
*
* @param key
* @param newValue
*/
@Override
public void set(K key, V newValue) {
//先判断这个节点在不在
Node node = getNode(root, key);
//如果节点不存在 直接抛异常
if (node == null) {
throw new IllegalArgumentException(key + "doesn't exit");
}
//如果节点是存在的 将值设置为指定的值
node.value = newValue;
}
/**
* 返回node为节点的二分搜索树的最下值所在的节点
* <p>
* 二分搜索的树 的特点 直接遍历左子树就行
*
* @param node
* @return
*/
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
/**
* 删除二分搜索树中的最小的元素
* 返回删除节点后的 二分搜索树的根
* <p>
* 需要使用在草稿纸上画图进行理解
* <p>
* 将运行逻辑结合栈 进行 入栈出栈
*
* @param node
* @return
*/
private Node removeMin(Node node) {
//递归的结束条件
if (node.left == null) {
//如果左边的节点为空 直接返回根节点？？？
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
/**
* 二叉搜索树 ：节点的删除设计节点的替换
* 节点的替换 设计父节点 孩子节点的信息的更新
* <p>
* 会很复杂
*
* @param key
* @return
*/
@Override
public V remove(K key) {
//同一个类中的方法之间的调用时不需要的new 对象的
Node node = getNode(root, key);
Node delNode = node;
if (key.compareTo(node.key) == 0) {
remove(key);
}
while (key.compareTo(node.key) < 0) {
node = getNode(node.left, key);
}
delNode = node;
node = null;
return null;
}
private Node remove(Node node, K key) {
if (node == null)
return node;
/**
* 根据 key 的大小，遍历到 key
*
*/
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
return node;
} else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
return node;
}
/**
* key 等于根节点
* 待删除节点左子树为空的情况 e.key == 0;
*/
else {
//左子树为空
if(node.left == null && node.right != null){
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
//右子树为空
if (node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
//待删除节点左右子树均不为空
//找到比待删除节点的最小节点，即待删除节点的右子树的最小节点
//用这个节点顶替待删除的节点的位置
Node successor = minimum(node.right); //待替换的节点替换为其的右子树中的最小值
successor.right = removeMin(node.right); //待删除节点的有右子树中用来替代的节点被 删除 与此同时被保存
successor.left = node.left; //替换后的节点的左几点 设置为原来待删除节点处的左节点
node.left = node.right = null; //将待删除节点的左右节点置为空，方便回收
//返回 待替换多的节点
return successor;
}
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
}