数据结构之查找（二）二叉查找树

一、二叉查找树

    

        1.定义特点维基百科

        2.我当时在写实例化的方法的时候很犯愁

           =》理解RootNode为整个数中的一个中间节点key

                 =》Quick Sort的概念

           =》实例化的时候不用找到某两个节点的范围

           =》按照InOrder Traversal 结构式排序的顺序

 

二、基本实现

       =》节点结构

       =》查询

       =》添加

       =》实例化

       =》中序遍历

       =》效果图

       =》删除节点（实现了在）

 

//节点的基本结构 
 class TreeNode {
      private int num;
      private TreeNode leftChilder;
      private TreeNode rightChilder;

      //get\set method

}

 

//查询
  //当根为空
  //不为空
    //找到  
    //找不到
//search the BST
        public static Boolean searchBST(int key) { 
            // the root is null
            TreeNode temp = head;
            if (temp == null) return false;

            while (temp != null)
            {
                int num = temp.getNum();
                if (key == num) return true;
                if (key > num) temp = temp.getRightChilder();
                if (key < num) temp = temp.getLeftChilder();
            }
         return false;
        }

 

//插入数据
//首先查询数据
  //存在继续插入
  //不存在
    //如果Head为空新建
    //如果不为空找到位置
      //左边、右边知道它左边、右边为空
  public static void insertBST(int insertNum) {
            //first judege if exist it?
              //exist then continue
              //not exist then
                  //judge head
                  // find it
            if (searchBST(insertNum))
            {
                return;
            }
            else {
                if (head == null)
                {
                    head = new TreeNode();
                    head.setLeftChilder(null);
                    head.setRightChilder(null);
                    head.setNum(insertNum);
                    Console.WriteLine("===>insert ok...");
                    return;
                }
                else {
                    TreeNode headCopy = head;
                    TreeNode temp = new TreeNode();
                    temp.setNum(insertNum);
                    temp.setLeftChilder(null);
                    temp.setRightChilder(null);
                 
                    while (true)
                    {                          //find the left or right position
                        if (headCopy.getNum() > insertNum)
                        {
                            if (headCopy.getLeftChilder() == null)
                            {
                                headCopy.setLeftChilder(temp);
                                break;
                            }
                            headCopy = headCopy.getLeftChilder();
                        }
                        else
                        {
                            if (headCopy.getRightChilder() == null)
                            {
                                headCopy.setRightChilder(temp);
                                break;
                            }
                            headCopy = headCopy.getRightChilder();
                        }
                    }
                    Console.WriteLine("===>insert ok...");
                    return;
                }
             
            }
        }

 

//实例化查询树
//实例化很特别，不跟实例化二叉树一一样
//                    二叉树可以直接递归插入
//这里多了一个位置的查找过程
   //init a binary search tree;
        //special positon is the insert is not remove is a not change
        public static void initBST() { 
            try
            {
                while (true)
                {
                    Console.WriteLine("===>If you input -1 it will be end!");
                        Console.Write("===>Input you num:");

                    int data = Int32.Parse(Console.ReadLine());

                    if (data == -1) {
                        Console.WriteLine("The BST init successful...");
                        break;                                 //input the end
                    }
                    else
                    {
                        insertBST(data);
                    }
                }
            }
            catch (Exception)
            {
                Console.WriteLine("\n===>Yon Input Error! So this node is null!!!");
            }
        }

 

//外加一个左子树遍历
//刚好一个排序效果
  public static void inorderTravers(TreeNode t) {
            if (t != null && t.getNum() != -1) {
                inorderTravers(t.getLeftChilder());
                Console.WriteLine(t.getNum());
                inorderTravers(t.getRightChilder());
            }
   }

 

 

//删除效果
//首先判断节点存在不
  //不存在继续
  //存在
    //如果是叶子结点直接父节点指向NULL
      //如果只有左子树 左子树替代
    //如果只有右子树 右子树替代
    //如果左右子树都有
       //可以求出左边最大值 删除它然后替换
       //也可以求出右边最小值 删除然后替换
========================================
       //delete the BST
        //exists
          //   if not exists return;
          //   if exists
                 //if is the leaf node delete it
                 //if the rightChild is not exist just 
                 //if the leftChild is not exist just 
                 //if the all exists then
        public static void deleteBST(int deleteNum) {
            if (!searchBST(deleteNum))
            {
                Console.WriteLine("The number is not exist...");
            }
            else {
               //get the  node
                TreeNode temp = head;
                TreeNode parent = null;
                while (temp.getNum()!=deleteNum) { //if get the  
                    parent = temp;
                    if (temp.getNum() > deleteNum) temp = temp.getLeftChilder();
                    else if (temp.getNum() < deleteNum) temp = temp.getRightChilder();
                }

                //if the node is the leaf
                if (temp.getLeftChilder() == null && temp.getRightChilder() == null) {
                    if (deleteNum < parent.getNum()) parent.setLeftChilder(null);
                    else {
                        parent.setRightChilder(null);
                    }
                }

                //if the node's left is null
                else if (temp.getLeftChilder() == null)
                {
                    TreeNode right = temp.getRightChilder();

                    temp.setNum(right.getNum());
                    temp.setLeftChilder(right.getLeftChilder());
                    temp.setRightChilder(right.getRightChilder());
                }

                //if the node's right is null
                else if (temp.getRightChilder() == null)
                {
                    TreeNode left = temp.getLeftChilder();

                    temp.setNum(left.getNum());
                    temp.setLeftChilder(left.getLeftChilder());
                    temp.setRightChilder(left.getRightChilder());
                }

                //if have all the node
                    //find the left max
                    //find the right min
                else if (temp.getLeftChilder() != null && temp.getRightChilder() != null)
                {
                    //find the left max
                    TreeNode max = temp.getLeftChilder();
                    while (max.getRightChilder() != null) {
                        max = max.getRightChilder();
                    }
                    deleteBST(max.getNum());
                    temp.setNum(max.getNum());
                }
            }

 

 再来一张图来