Java刪除二叉搜索樹的任意元素的方法詳解

//從二叉搜索樹中刪除元素為e的節(jié)點
  public void remove(E e) {
    root = remove(root, e);
  }

  //刪除以node為根的二叉搜索樹中值為e的節(jié)點，遞歸算法
  //返回刪除節(jié)點后更新的二叉搜索樹的根
  private Node remove(Node node, E e) {
    if (node == null)
      return null;

    if (e.compareTo(node.e) < 0) {//e<node.e (被刪除元素e小于當(dāng)前節(jié)點值e)
      node.left = remove(node.left, e);
      return node;
    }
    if (e.compareTo(node.e) > 0) {//e>node.e (被刪除元素e大于當(dāng)前節(jié)點值e)
      node.right = remove(node.right, e);
      return node;
    } else {//e==node.e (被刪除元素e等于當(dāng)前節(jié)點值e)

      //待刪除節(jié)點左子樹為空情況
      if (node.left == null) {
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
      }

      //待刪除節(jié)點右子樹為空情況
      if (node.right == null) {
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
      }

      //左右子樹均不為空
      //方法：找到比待刪除節(jié)點大的最小節(jié)點，即待刪除節(jié)點右子樹的最小節(jié)點
      //用這個節(jié)點頂替待刪除節(jié)點的位置
      Node successor = minimum(node.right);
      successor.right = removeMin(node.right);
      successor.left = node.left;
      node.left = node.right = null;

      return successor;
    }
  }

// 尋找二分搜索樹的最小元素
  public E minimum() {
    if (size == 0) {
      throw new IllegalArgumentException("BST is empty");
    }

    Node ninNode = minimum(root);
    return ninNode.e;
  }

  // 返回以node為根的二分搜索樹的最小值所在的節(jié)點
  private Node minimum(Node node) {
    if (node.left == null) {
      return node;
    }

    //返回相應(yīng)的節(jié)點的左子樹的最小值
    return minimum(node.left);
  }