二叉搜索树基于int类型key与Object类型value简单实现

403行代码没有一句废话,写的太累,后续闲下来了再补全注释与思路,后面可能还会实现基于泛型K,V key与value的实现

以下只提供代码(部分方法使用递归与非递归两种方法实现):

import java.util.ArrayList;
public class BSTree1 {
    BSTNode root;
    static class BSTNode {
        int key;
        Object value;
        BSTNode left;
        BSTNode right;
        public BSTNode(int key) {
            this.key = key;
        }
        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }
        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
/*
查找关键字对应的值
递归实现
@param key - 关键字
@return 关键字对应的值
*/
/*    
      public Object get(int key) {
          return doGet(root, key);
      }
  
      private Object doGet(BSTNode node, int key) {
          if (node == null) {
              return null;
          }
          if (node.key < key) {
              return doGet(node.right, key);
          } else if (key < node.key) {
              return doGet(node.left, key);
          } else {
              return node.value;
          }
      }
*/
    /**
     <h3>查找关键字对应的值</h3>
     非递归实现
     
     @param key 关键字
     @return 关键字对应的值
     */
    public Object get(int key) {
        BSTNode node = root;
        while (node != null) {
            if (node.key < key) {
                node = node.right;
            } else if (key < node.key) {
                node = node.left;
            } else {
                return node.value;
            }
        }
        return null;
    }

      /**
       * 查找最小关键字对应的值
       * 递归实现
       *
       * @return 关键字对应的值
       */
//    public Object min() {
//        return doMin(root);
//    }
//
//    private Object doMin(BSTNode node) {
//        if (node == null) {
//            return null;
//        }
//        if (node.left == null) {
//            return node.value;
//        }
//        return doMin(node.left);
//    }

    /**
     * <h3>查找最小关键字对应的值</h3>
     * 非递归实现
     *
     * @return 关键字对应的值
     */
    public Object min() {
        return min(root);
    }

    private Object min(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

      /**
       * 查找最大关键字对应的值
       * 递归实现
       * @return 关键字对应的值
       */
      public Object max() {
          return doMax(root);
      }
  
      private Object doMax(BSTNode node){
          if (node == null){
              return null;
          }
          if (node.right == null){
              return node.value;
          }
          return doMax(node.right);
      }


    /**
     * <h3>查找最大关键字对应的值</h3>
     * 非递归实现
     *
     * @return 关键字对应的值
     */
    public Object max() {
        return max(root);
    }

    private Object max(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    /**
     * <H3>存储关键字和对应值</h3>
     *
     * @param key   关键字
     * @param value 值
     */
    public void put(int key, Object value) {
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null) {
            parent = node;
            if (node.key < key) {
                node = node.right;
            } else if (key < node.key) {
                node = node.left;
            } else {
                node.value = value;
                return;
            }
        }
        if (parent == null) {
            root = new BSTNode(key, value);
            return;
        }
        if (key < parent.key) {
            parent.left = new BSTNode(key, value);
        } else {
            parent.right = new BSTNode(key, value);
        }
    }

    /**
     * <h3>查找关键字的后驱值</h3>
     * <p>
     * 情况1:节点有右子树,此时后任就是右子树的最小值<br>
     * 情况2:节点没有右子树,若离它最近的,自右而来的祖先就是后任
     *
     * @param key 关键字
     * @return 前驱值
     */
    public Object successor(int key) {
        BSTNode p = root;
        BSTNode ancestorFromRight = null;
        //这个循环先查找该key在树中是否存在
        while (p != null) {
            if (key < p.key) {
                ancestorFromRight = p;
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        if (p.right != null) {
            return min(p.right);
        }
        return ancestorFromRight != null ? ancestorFromRight.value : null;
    }

    /**
     * <h3>查找关键字的前继值</h3>
     * <p>
     * 情况1:节点有左子树,此时前任就是左子树的最大值<br>
     * 情况2:节点没有左子树,若离它最近的,自左而来的祖先就是前任
     *
     * @param key 关键字
     * @return 后继值
     */
    public Object predecessor(int key) {
        /*
            思路:
                先找当当前节点,如果没找到直接返回null
                然后判断第一种情况,当左子树不为null时,找到左子树中最大的并返回
                然后判断第二种情况,创建一个指针用于记录从左而来的祖先节点,最后如果从左而来的祖先节点不为null则返回
         */
        BSTNode p = root;
        BSTNode ancestorFromLeft = null;
        //这个循环先查找该key在树中是否存在
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (p.key < key) {
                ancestorFromLeft = p;
                p = p.right;
            } else {
                break;
            }
        }

        if (p == null) {
            return null;
        }
        if (p.left != null) {
            return max(p.left);
        }
        return ancestorFromLeft != null ? ancestorFromLeft.value : null;
    }

    /**
     * <h3>根据关键字删除</h3>
     * 非递归实现
     * <p>
     * 情况1:删除节点没有左孩子,将右孩子托孤给Parent<br>
     * 情况2:删除节点没有右孩子,将左孩子托孤给Parent<br>
     * 情况3:删除的是叶子节点,这种情况处理方法可以涵盖到情况1,2中<br>
     * 情况4:删除节点的左右孩子都有,可以将它的后继节点(称为S) 托孤给Parent,再称S的父亲为SP,又分两种情况:<br>
     * <p>1:SP就是被删除节点,此时D与S紧邻,只需要将S托孤给Parent</p>
     * <p>2:SP不是被删除节点,此时D与S不相邻,此时需要将S的后代托孤给SP,再将S托孤给Parent</p>
     *
     * @param key 关键字
     * @return 被删除关键字对应的值
     */
    public Object delete(int key) {
        //首先也应该先找到该节点与该节点的父节点
        BSTNode p = root;
        BSTNode parent = null; //用于记录待删除节点的父亲
        while (p != null) {
            if (key < p.key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        //这是情况1
        if (p.left == null) {
            shift(parent, p, p.right);
        }
        //这是情况2
        else if (p.right == null) {
            shift(parent, p, p.left);
        }
        //这是情况4
        else {
            //首先找到被删除节点的后继
            BSTNode s = p.right;
            BSTNode sParent = p; //用来记录后继节点的父亲
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            //循环结束后 s 就是后继节点
            //接下来判断是否需要处理被删除节点的后事
            /*
                思路:
                    如果后继节点的sParent还是被删除节点,那么意味着被删除节点与后继节点紧邻,不用处理后事
                    如果后继节点的sParent不再是被删除节点,那么意味着被删除节点不与后继节点相邻,需要处理后事
                    因此先判断后继节点的sParent还是不是被删除节点
             */
            //不相邻,处理后继节点的后事
            if (sParent != p) {
                shift(sParent, s, s.right); //s的后继节点不可能有左孩子,因为s就是最小的
                s.right = p.right; //改变指针,顶上去的后继节点的右指针应该指向被删除节点的右指针
            }
            //最后让后继节点顶上被删除节点就完成
            shift(parent, p, s);
            //删除后,改变顶上来的节点的左右指针,指向被删除节点的左右孩子
            s.left = p.left;
        }
        return p.value;
    }

      /**
       * 根据关键字删除
       * <p>递归实现</p>
       *
       * @param key 关键字
       * @return 被删除关键字对应的值
       */
      public Object delete(int key) {
          ArrayList<Object> result = new ArrayList<>(); //保存被删除节点的值
          root = doDelete(root, key, result);
          return result.isEmpty() ? null : result.get(0);
      }
  	   /*
      /**
       * 用于递归delete方法的内部方法
       *
       * @param node 代表递归删除的起点
       * @param key  关键字
       * @return 被删除节点删除后剩下的孩子节点
       */
      private BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result) {
          //如下三个if条件在于找要删除节点
          if (node == null) {
              return null;
          }
          if (key < node.key) {
              node.left = doDelete(node.left, key, result);
              return node;
          } else if (node.key < key) {
              node.right = doDelete(node.right, key, result);
              return node;
          }
          result.add(node.value);
          //如果执行到这里,代表已经找到了要删除节点
          //如果被删除节点只有一个孩子
          /*
          if (node.left == null) {
              return node.right;
          }
          if (node.right == null) {
              return node.left;
          }
          */
          //如果被删除节点有两个孩子
          //先找到后继节点,也就是右子树中最小的
//        BSTNode s = node.right;
          //一直向左走,走到头就是后继节点
          /*
          while (s.left != null) {
              s = s.left;
          }
          */
          //这里已经拿到了后继节点
          //顶上去之后,修改后继节点的指针
          //第四种情况,如果后继节点与被删除节点不相邻,那么应该先处理后继节点的后事
          //再次递归调用
//        s.right = doDelete(node.right, s.key, new ArrayList<>());
//        s.left = node.left;
          //最后返回s,也就是被删除节点剩下的孩子节点
//        return s;
//    }

    /**
     * 托孤方法,用于将被删除节点的子树移交给被删除节点的父节点<br>
     *
     * @param parent  被删除节点的父节点
     * @param deleted 要被删除的节点
     * @param child   被顶上去的节点
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        //如果被删除节点本身就是根节点,那么被删除节点没有parent,直接将被删除节点的child变为root
        if (parent == null) {
            root = child;
        } else if (deleted == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }
}