二叉搜索树(java实现)

目录
　　1 .插入元素思想与实现
　　2 .删除元素思想与实现
　　3 .完整代码

二叉搜索树定义

二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 任意节点的左、右子树也分别为二叉查找树。

4. 没有键值相等的节点。

构造节点：

class Node<T extends Comparable> {
    int key;
    T val;
    Node<T> left;
    Node<T> right;

    public Node() {

    }

    public Node(int key, T val) {
        this.key = key;
        this.val = val;
    }
}

二叉搜索树插入

　　插入的过程是：比较当前结点，如果小于当前结点，就往左子树查找。如果大于当前结点，就往右子树查找。直到查找的子树为空树的时候，就是其插入的位置。

private void insertKV(int key, T val) {
        // 如果是空树，则插入的节点为根节点
     if (root == null) {
        root = new Node<T>(key, val);
        return;
     }
     Node cur = root;
     Node parent = root;
     boolean isLeftNode = true;
     while (cur != null) {//直到找到该插入的位置
        parent = cur;
        if (key < cur.key) { // 如果小于当前节点的值，往左子树查找
           cur = cur.left;
           isLeftNode = true;
        } else { // 如果大于当前节点的值，往右子树查找
           cur = cur.right;
           isLeftNode = false;
        }
     }
     Node newNode = new Node(key, val);
     if (isLeftNode) {
         parent.left = newNode;
     } else {
         parent.right = newNode;
   }
}

二叉搜索树的删除

删除应该属于二叉搜索树中最复杂的情况了。

有对应4种情况：

• 删除的元素为叶子节点
  　　把该节点的父节点指向该节点的引用指向null就可以
• 删除元素只有右孩子
  　　将该节点的右子数上移一层
• 删除元素只有左孩子
  　　将该节点的左子数上移一层
• 删除的元素既有左孩子，又有右孩子(这个情况最为复杂)
  　　需要在保持排序树的结构下进行上旋和下旋

1.1 先将当前结点定位到要删除的节点

 /**
 * 找到要删除的节点，并把当前结点定位到要删除的节点
*/
while (cur.key!=key){
    parent = cur;
    if(key<cur.key){ //如果删除的元素在左子树
        isLeftChild = true;//在左子树设为true
        cur = cur.left;
    }else { //如果删除的元素在右子树
        isLeftChild = false;
        cur = cur.right;
    }
    if(cur == null){//不存在该节点
        return false;
    }
}

1.2.1 删除叶子节点

if(cur.left == null&&cur.right==null){//当前结点是叶子节点的时候
    if(cur == root){ //是根节点，且根节点没有叶子节点的时候
        root = null; // 树为空树
    }
    else if(isLeftChild){// 当前结点是左孩子节点
        parent.left = null; //父节点的左孩子设为空
    }else {// 当前结点是右孩子节点
        parent.right = null;//父节点的左孩子设为空
    }
}

1.2.2 删除元素只有右孩子

else if(cur.left == null){//当前结点没有左孩子，只有右孩子
    if (cur == root){ //当前结点为根
        root = cur.right;//左子树上移
    }else if(isLeftChild){ // 当前结点是其父节点的左孩子
        parent.left = cur.right;
    }else { // 当前结点是其父节点的右孩子
        parent.right = cur.right;
    }
}

1.2.3 删除元素只有左孩子

else if(cur.right == null){//当前结点没有右孩子，只有左孩子
    if (cur == root){ //当前结点为根
        root = cur.left;//左子树上移
    }else if(isLeftChild){ // 当前结点是其父节点的左孩子
        parent.left = cur.left;
    }else { // 当前结点是其父节点的右孩子
        parent.right = cur.left;
    }
}

1.2.4 删除的元素既有左孩子，又有右孩子

else {//当前结点有左孩子，也有右孩子
    Node<T> successor = getSuccessor(cur);
    if(cur == root){
        root = successor;
    }
    else if(isLeftChild){
        parent.left = successor;
    }
    else {
        parent.right = successor;
    }
    //将删除节点的左子树接到旋好的树的左子树上
    successor.left = cur.left;
}

/**
* 将要删除节点为根节点的树
* 进行旋转操作
* @param delNode 要删除的节点
* @return 旋好的子树
*/
private Node<T> getSuccessor(Node delNode) {
    Node<T> successorParent = delNode;
    Node<T> successor = delNode;
    Node<T> cur = delNode.right;
    while(cur!=null){
        successorParent = successor;
        successor = cur;
        cur = cur.left;
    }
    if(successor!=delNode.right){
        successorParent.left = successor.right;
        successor.right = delNode.right;
    }
    return successor;
}

删除18节点，代码执行过程。经过旋转结果的到以18为根的树变成了右图，虚线是转完之后接上18的左子树

同样是删除18节点，18的子树变复杂了，转后的子树如右

看了这几张转后的图片，可以知道我旋转子树的思想。

首先看删除节点的右子树，如果为空，就把该节点的右孩子节点往上提一层。

如果右子树不为空，在看右子树的左子树，如果左子树为空，把整个右子树往上提一层。

如果右子树的左子树不为空，且左子树没有孩子节点的时候，直接把右子树的左子树提到要删除节点的位置

有左孩子的时候，像以上的循环就可以，直到左孩子为空，循环停止。

以上是我个人的实现时的理解方式。大致可以对比这几张图，就能达到理解的目的。
注意：旋转实现，只要能保证二叉搜索树的特点，定义就可以。旋转也不只是一种实现方式。

完整代码

完整代码地址：我的代码