package SearchBinaryTree;

public class SearchBinaryTreeNode<T> {
  T data;
  public SearchBinaryTreeNode<T> leftChild;
  public SearchBinaryTreeNode<T> rightChild;

  public SearchBinaryTreeNode(){
    this.data=null;
    this.leftChild=this.rightChild=null;
  }

  public SearchBinaryTreeNode(T da){
    this.data=da;
    this.leftChild=this.rightChild=null;
  }

  public SearchBinaryTreeNode(T da,SearchBinaryTreeNode<T> left,SearchBinaryTreeNode<T>right){
    this.data=da;
    this.leftChild=left;
    this.rightChild=right;
  }

  public T getData() {
    return data;
  }
  public void setData(T data) {
    this.data = data;
  }
  public SearchBinaryTreeNode<T> getLeftChild() {
    return leftChild;
  }
  public void setLeftChild(SearchBinaryTreeNode<T> leftChild) {
    this.leftChild = leftChild;
  }
  public SearchBinaryTreeNode<T> getRightChild() {
    return rightChild;
  }
  public void setRightChild(SearchBinaryTreeNode<T> rightChild) {
    this.rightChild = rightChild;
  }

  public boolean isLeaf(){
    if(this.leftChild==null&&this.rightChild==null){
      return true;
    }
    return false;
  }


}

package SearchBinaryTree;


public class SearchBinaryTree<T> {
  SearchBinaryTreeNode<T> root;

  public boolean isEmpty(){
    if(root==null){
      return true;
    }
    return false;
  }

  public void Visit(SearchBinaryTreeNode<T> root){
    if(root==null){
      System.out.println("this tree is empty!");
    }
    System.out.println(root.getData());
  }

  public SearchBinaryTreeNode<T> getRoot(){
    if(root==null){
      root=new SearchBinaryTreeNode<T>();
    }
    return root;
  }

  public SearchBinaryTree(){
    this.root=null;
  }

  /*
   * 创造一颗二叉树
   */
  public void CreateTree(SearchBinaryTreeNode<T> node, T data) {
    if (root == null) {
      root = new SearchBinaryTreeNode<T>();
    } else {
      if (Math.random() > 0.5) {          //采用随机方式创建二叉树
        if (node.leftChild == null) {
          node.leftChild = new SearchBinaryTreeNode<T>(data);
        } else {
          CreateTree(node.leftChild, data);
        }
      } else {
        if (node.rightChild == null) {
          node.rightChild = new SearchBinaryTreeNode<T>(data);
        } else {
          CreateTree(node.rightChild, data);
        }
      }
    }
  }

  /*
   * 在二查搜索树中进行搜索
   */
  public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){
    SearchBinaryTreeNode<T> current=root;
    while((root!=null)&&(current.getData()!=value)){
      //需要注意的是java中泛型无法比较大小，在实际的使用时我们可以使用常见的数据类型来替代这个泛型，这样就不会出错了
      current=(value<current.getData()?search(current.leftChild,value):search(current.rightChild,value));
    }
    return current;
  }

  public SearchBinaryTreeNode<T> insertNode( T value){
    SearchBinaryTreeNode<T> p=root,pre=null;
    while(p!=null){
      pre=p;
      //需要注意的是java中泛型无法比较大小，在实际的使用时我们可以使用常见的数据类型来替代这个泛型，这样就不会出错了
      if(p.getData()<value){
        p=p.rightChild;
      }else{
        p=p.leftChild;
      }
    }
    if(root==null){
      root=new SearchBinaryTreeNode<T>(value);
    }else if(pre.getData()<value){
      pre.rightChild=new SearchBinaryTreeNode<T>(value);
    }else{
      pre.leftChild=new SearchBinaryTreeNode<T>(value);
    }
  }

  /*
   * 合并删除
   */
  public void deleteByMerging(SearchBinaryTreeNode<T> node){
    SearchBinaryTreeNode<T> temp=node;
    if(node!=null){
      //若被删除节点没有右子树,用其左子树的根节点来代替被删除节点
      if(node.rightChild!=null){
        node=node.leftChild;
      }else if(node.leftChild==null){
        //若被删节点没有左子树，用其有字数的最左端的节点代替被删除的节点
        node=node.rightChild;
      }else{
        //如果被删节点左右子树均存在
        temp=node.leftChild;
        while(temp.rightChild!=null){
          temp=temp.rightChild;   //一直查找到左子树的右节点
        }

        //将查找到的节点的右指针赋值为被删除节点的右子树的根
        temp.rightChild=node.rightChild;
        temp=node;
        node=node.leftChild;
      }
      temp=null;
    }
  }

  /*
   * 复制删除
   */
  public void deleteByCoping(SearchBinaryTreeNode<T> node){
    SearchBinaryTreeNode<T> pre=null;
    SearchBinaryTreeNode<T> temp=node;
    //如果被删节点没有右子树，用其左子树的根节点来代替被删除节点
    if(node.rightChild==null){
      node=node.leftChild;
    }else if(node.leftChild==null){
      node=node.rightChild;
    }else{
      //如果被删节点的左右子树都存在
      temp=node.leftChild;
      pre=node;
      while(temp.rightChild!=null){
        pre=temp;
        temp=temp.rightChild;   //遍历查找到左子树的最右端的节点
      }
      node.data=temp.data;      //进行赋值操作
      if(pre==node){
        pre.leftChild=node.leftChild;
      }else{
        pre.rightChild=node.rightChild;
      }
    }
    temp=null;
  }

}

package SearchBinaryTree;

public class SearchBinaryTreeTest {

  public static void main(String []args){
    SearchBinaryTree<Integer> tree=new SearchBinaryTree<Integer>();
    for(int i=1;i<10;i++){
      tree.CreateTree(new SearchBinaryTreeNode<Integer>(), i);
    }

    //搜索
    tree.search(tree.root, 7);

    //合并删除
    tree.deleteByMerging(new SearchBinaryTreeNode<Integer>(8));

    //复制删除
    tree.deleteByCoping(new SearchBinaryTreeNode<Integer>(6));
  }

}