static class Node{
    Node parent;
    Node leftChild;
    Node rightChild;
    int val;
    public Node(Node parent, Node leftChild, Node rightChild,int val) {
      super();
      this.parent = parent;
      this.leftChild = leftChild;
      this.rightChild = rightChild;
      this.val = val;
    }
    public Node(int val){
      this(null,null,null,val);
    }
    public Node(Node node,int val){
      this(node,null,null,val);
    }
  }

 public class SearchBinaryTree {
  private Node root;
  private int size;
  public SearchBinaryTree() {
    super();
  }
}

public boolean add(int val){
    if(root == null){
      root = new Node(val);
      size++;
      return true;
    }
    Node node = getAdapterNode(root, val);
    Node newNode = new Node(val);
    if(node.val > val){
      node.leftChild = newNode;
      newNode.parent = node;
    }else if(node.val < val){
      node.rightChild = newNode;
      newNode.parent = node;
    }else{
      // 暫不做處理
    }
    size++;19     return true;
  }
  /**
   * 獲取要插入的節(jié)點的父節(jié)點，該父節(jié)點滿足以下幾種狀態(tài)之一
   * 1、父節(jié)點為子節(jié)點
   * 2、插入節(jié)點值比父節(jié)點小，但父節(jié)點沒有左子節(jié)點
   * 3、插入節(jié)點值比父節(jié)點大，但父節(jié)點沒有右子節(jié)點
   * 4、插入節(jié)點值和父節(jié)點相等。
   * 5、父節(jié)點為空
   * 如果滿足以上5種情況之一，則遞歸停止。
   * @param node
   * @param val
   * @return
   */
  private Node getAdapterNode(Node node,int val){
    if(node == null){
      return node;
    }
    // 往左子樹中插入，但沒左子樹，則返回
    if(node.val > val && node.leftChild == null){
      return node;
    }
    // 往右子樹中插入，但沒右子樹，也返回
    if(node.val < val && node.rightChild == null){
      return node;
    }
    // 該節(jié)點是葉子節(jié)點，則返回
    if(node.leftChild == null && node.rightChild == null){
      return node;
    }
    if(node.val > val && node.leftChild != null){
      return getAdaptarNode(node.leftChild, val);
    }else if(node.val < val && node.rightChild != null){
      return getAdaptarNode(node.rightChild, val);
    }else{
      return node;
    }
  }

public boolean put(int val){
    return putVal(root,val);
  }
  private boolean putVal(Node node,int val){
    if(node == null){// 初始化根節(jié)點
      node = new Node(val);
      root = node;
      size++;
      return true;
    }
    Node temp = node;
    Node p;
    int t;
    /**
     * 通過do while循環(huán)迭代獲取最佳節(jié)點，
     */
    do{ 
      p = temp;
      t = temp.val-val;
      if(t > 0){
        temp = temp.leftChild;
      }else if(t < 0){
        temp = temp.rightChild;
      }else{
        temp.val = val;
        return false;
      }
    }while(temp != null);
    Node newNode = new Node(p, val);
    if(t > 0){
      p.leftChild = newNode;
    }else if(t < 0){
      p.rightChild = newNode;
    }
    size++;
    return true;
  }

public boolean delete(int val){
    Node node = getNode(val);
    if(node == null){
      return false;
    }
    Node parent = node.parent;
    Node leftChild = node.leftChild;
    Node rightChild = node.rightChild;
    //以下所有父節(jié)點為空的情況，則表明刪除的節(jié)點是根節(jié)點
    if(leftChild == null && rightChild == null){//沒有子節(jié)點
      if(parent != null){
        if(parent.leftChild == node){
          parent.leftChild = null;
        }else if(parent.rightChild == node){
          parent.rightChild = null;
        }
      }else{//不存在父節(jié)點，則表明刪除節(jié)點為根節(jié)點
        root = null;
      }
      node = null;
      return true;
    }else if(leftChild == null && rightChild != null){// 只有右節(jié)點
      if(parent != null && parent.val > val){// 存在父節(jié)點，且node位置為父節(jié)點的左邊
        parent.leftChild = rightChild;
      }else if(parent != null && parent.val < val){// 存在父節(jié)點，且node位置為父節(jié)點的右邊
        parent.rightChild = rightChild;
      }else{
        root = rightChild;
      }
      node = null;
      return true;
    }else if(leftChild != null && rightChild == null){// 只有左節(jié)點
      if(parent != null && parent.val > val){// 存在父節(jié)點，且node位置為父節(jié)點的左邊
        parent.leftChild = leftChild;
      }else if(parent != null && parent.val < val){// 存在父節(jié)點，且node位置為父節(jié)點的右邊
        parent.rightChild = leftChild;
      }else{
        root = leftChild;
      }
      return true;
    }else if(leftChild != null && rightChild != null){// 兩個子節(jié)點都存在
      Node successor = getSuccessor(node);// 這種情況，一定存在后繼節(jié)點
      int temp = successor.val;
      boolean delete = delete(temp);
      if(delete){
        node.val = temp;
      }
      successor = null;
      return true;
    }
    return false;
  }
  
  /**
   * 找到node節(jié)點的后繼節(jié)點
   * 1、先判斷該節(jié)點有沒有右子樹，如果有，則從右節(jié)點的左子樹中尋找后繼節(jié)點，沒有則進行下一步
   * 2、查找該節(jié)點的父節(jié)點，若該父節(jié)點的右節(jié)點等于該節(jié)點，則繼續(xù)尋找父節(jié)點，
   *  直至父節(jié)點為Null或找到不等于該節(jié)點的右節(jié)點。
   * 理由，后繼節(jié)點一定比該節(jié)點大，若存在右子樹，則后繼節(jié)點一定存在右子樹中，這是第一步的理由
   *   若不存在右子樹，則也可能存在該節(jié)點的某個祖父節(jié)點(即該節(jié)點的父節(jié)點，或更上層父節(jié)點)的右子樹中，
   *   對其迭代查找，若有，則返回該節(jié)點，沒有則返回null
   * @param node
   * @return
   */
  private Node getSuccessor(Node node){
    if(node.rightChild != null){
      Node rightChild = node.rightChild;
      while(rightChild.leftChild != null){
        rightChild = rightChild.leftChild;
      }
      return rightChild;
    }
    Node parent = node.parent;
    while(parent != null && (node == parent.rightChild)){
      node = parent;
      parent = parent.parent;
    }
    return parent;
  }

public boolean remove(int val){
    Node node = getNode(val);
    if(node == null){
      return false;
    }
    if(node.leftChild == null){// 1、左節(jié)點不存在，右節(jié)點可能存在，包含兩種情況 ，兩個節(jié)點都不存在和只存在右節(jié)點
      transplant(node, node.rightChild);
    }else if(node.rightChild == null){//2、左孩子存在，右節(jié)點不存在
      transplant(node, node.leftChild);
    }else{// 3、兩個節(jié)點都存在
      Node successor = getSuccessor(node);// 得到node后繼節(jié)點 
      if(successor.parent != node){// 后繼節(jié)點存在node的右子樹中。
        transplant(successor, successor.rightChild);// 用后繼節(jié)點的右子節(jié)點替換該后繼節(jié)點
        successor.rightChild = node.rightChild;// 將node節(jié)點的右子樹賦給后繼節(jié)點的右節(jié)點，即類似后繼與node節(jié)點調(diào)換位置
        successor.rightChild.parent = successor;// 接著上一步 給接過來的右節(jié)點的父引用復(fù)制
      }
      transplant(node, successor);
      successor.leftChild = node.leftChild;
      successor.leftChild.parent = successor;
    }
    return true;
  }
  /**
   * 將child節(jié)點替換node節(jié)點
   * @param root  根節(jié)點
   * @param node  要刪除的節(jié)點
   * @param child  node節(jié)點的子節(jié)點
   */
  private void transplant(Node node,Node child){
    /**
     * 1、先判斷 node是否存在父節(jié)點
     *  1、不存在，則child替換為根節(jié)點
     *  2、存在，則繼續(xù)下一步
     * 2、判斷node節(jié)點是父節(jié)點的那個孩子(即判斷出 node是右節(jié)點還是左節(jié)點)，
     *  得出結(jié)果后，將child節(jié)點替換node節(jié)點 ，即若node節(jié)點是左節(jié)點 則child替換后 也為左節(jié)點，否則為右節(jié)點
     * 3、將node節(jié)點的父節(jié)點置為child節(jié)點的父節(jié)點
     */
    
    if(node.parent == null){
      this.root = child;
    }else if(node.parent.leftChild == node){
      node.parent.leftChild = child;
    }else if(node.parent.rightChild == node){
      node.parent.rightChild = child;
    }
    if(child != null){
      child.parent = node.parent;
    }
  }

public Node getNode(int val){
    Node temp = root;
    int t;
    do{
      t = temp.val-val;
      if(t > 0){
        temp = temp.leftChild;
      }else if(t < 0){
        temp = temp.rightChild;
      }else{
        return temp;
      }
    }while(temp != null);
    return null;
  }

public void print(){
    print(root);
  }
  private void print(Node root){
    if(root != null){
      print(root.leftChild);
      System.out.println(root.val);// 位置在中間，則中序，若在前面，則為先序，否則為后續(xù)
      print(root.rightChild);
    }
  }