using System;

 public class TreeNode
 {
  public int data;//节点数据
  public TreeNode LeftNode;//左子女
  public TreeNode RightNode;//右子女
  ///
  /// 构造函数，初始化左右子女为空
  ///
  public TreeNode()
  {
   LeftNode = RightNode = null;
  }
 }

 public class Node
 {
  private TreeNode root;//根节点
  bool temp = false;//默认查找不存在
  ///
  /// 构造函数
  ///
  public Node()
  {
   root = null;
  }
  // 获得该节点最小左子女，用于删除元素使用
  //
  //
  //
  TreeNode Min(TreeNode parent)
  {
   TreeNode temp = parent;
   while(temp != null)
   {
    if(temp.LeftNode == null)
     return temp;
    else
     temp = temp.LeftNode;
   }
   return null;
  }

  ///
  /// 删除元素
  ///
  ///
  public void Remove(int data)
  {
   if (root == null)
    return;
   if(root.data == data)
   {
    TreeNode tmp = Min(root.RightNode);
    if(tmp == null)
    {
     root = root.LeftNode;
    }
    else
    {
     root.data = tmp.data;
     Remove(root,root.RightNode,1,tmp.data);
    }
   }
   else if(root.data!=data)
   {
    Remove(root,root.RightNode,1,data);
   }
   else
    Remove(root,root.LeftNode,0,data);

  }

  //在二叉排序树中删除值为data的结点
  public TreeNode Remove2(int data)
  {
   TreeNode p,f,s,q;
   p=root;f=null;
   //如果p不空就一直找下去
   while(p!=null)
   {
    //找到了就跳出循环
    if(p.data==data)
     break;
    f=p;
    if(p.data>data)
     p=p.LeftNode;
    else
     p=p.RightNode;
   }
   
   //找不到返回原根节点
   if(p==null) return root;
   //如果p无左子树
   if(p.LeftNode==null)
   {
    //p是原二叉排序树的根
    if(f==null)
     root=p.RightNode;
    //如果p是f的左孩子
    else if(f.LeftNode==p)
     f.LeftNode=p.RightNode;
    else
    //如果p是f的右孩子 
     f.RightNode=p.RightNode;
    //free(p);
   }

   //p有左子树
   else
   {
    q=p;s=p.LeftNode;
    //寻找p左子树的最右下节点
    while(s.RightNode!=null)
    {q=s;s=s.RightNode;}
    if(q==p)
     //将s的左子树链到q上
     q.LeftNode=s.LeftNode;
    else
     q.RightNode=s.LeftNode;
    //将s的值赋给p
    p.data=s.data;
    //free(s);
   }
   return root;

  }
  ///
  /// 删除元素递归
  ///
  ///
  ///
  ///
  ///
  private void Remove(TreeNode parent,TreeNode cur,int direction,int data)
  {
   if(cur.data == data)
   {
    if(cur.LeftNode == null)
    {
     if(direction == 0)
      parent.LeftNode = cur.RightNode;
     else
      parent.RightNode = cur.RightNode;
    }
    else if(cur.RightNode == null)
    {
     if(direction == 0)
      parent.LeftNode = cur.LeftNode;
     else
      parent.RightNode = cur.LeftNode;
    }
    else
    {
     TreeNode tmp =Min(cur.LeftNode);
     cur.data = tmp.data;
     Remove(cur,cur.LeftNode,1,tmp.data);
    }
   }
   else if(cur.data > data)
   {
    Remove(cur,cur.LeftNode,0,data);
   }
   else
   {
    Remove(cur,cur.RightNode,1,data);
   }
  }

  ///
  /// 查找是否存在该元素
  ///
  ///
  ///
  public bool Search(int data)
  {
   bool temp = false;
   if(root.data == data)
   {
    temp = true;
   }
   else
   {
    temp = Search(root,data);
   }
   return temp;
  }
  ///
  ///查找是否存在该元素，递归
  ///
  ///
  ///
  ///
  public bool Search(TreeNode node,int data)
  {
   if(node.data == data)
   {
    temp = true;
    Console.WriteLine("find");
   }
   else
   {
    if(node.data > data)
    {
     if(node.LeftNode != null)
     {
      Search(node.LeftNode,data);
     }
    }
    else
    {
     if(node.RightNode != null)
     {
      Search(node.RightNode,data);
     }
    }
   }
   return temp;
  }

  public void Search2(int data)
  {
   if(root==null)
    return;
   else
     Search(root,data);
  }
  ///
  /// 插入元素
  ///
  ///
  public  void Insert(int data)
  {
   if( root == null)
   {
    root = new TreeNode();
    root.data = data;
   }
   else
   {
    Insert(root,data);
   }
  }
  ///
  ///插入元素，递归
  ///
  ///
  ///
  public  void Insert(TreeNode node,int data)
  {
   if(node.data>data)
   {
    if(node.LeftNode == null)
    {
     TreeNode temp = new TreeNode();
     temp.data = data;
     node.LeftNode = temp;
    }
    else
    {
     Insert(node.LeftNode,data);
    }
   }
   else
   {
    if(node.RightNode== null)
    {
     TreeNode temp = new TreeNode();
     temp.data = data;
     node.RightNode = temp;
    }
    else
    {
     Insert(node.RightNode,data);
    }
   }
  }

  public  void PrintTree(TreeNode node,int layer)
  {
   if(node==null)
     return;
   PrintTree(node.RightNode, layer+3);
   for(int i=0; i<layer; i++)
    Console.Write(" ");
   Console.Write("{0}",node.data);
   Console.WriteLine();
            PrintTree(node.LeftNode, layer+3);
  
  }
       
  public  void PrintTree2()
  {
   if(root==null)
    return;
   else
    PrintTree(root,9);
   
  }
 }

class myApp
{
 public static void Main()
 {
  int z=0;
  string buff;
  TreeNode first = new TreeNode();
  Node Tfirst = new Node();
  for(;;)
  {
    Console.WriteLine("please intput a int");
    Console.WriteLine("if input -1 then break");
    buff= Console.ReadLine();
    z= Convert.ToInt32(buff);
          if(z==-1)
     break;
    Tfirst.Insert(z);
     }
  Tfirst.PrintTree2();
        Console.WriteLine("please intput a int which you want to search");
        buff= Console.ReadLine();
  z= Convert.ToInt32(buff);
        Tfirst.Search2(z);
  Console.WriteLine("please intput a int which you want to remove");
  buff= Console.ReadLine();
  z= Convert.ToInt32(buff);
  Tfirst.Remove2(z);
        Tfirst.PrintTree2();
  Console.ReadLine();

   
 }
}