using System;

//using System.IO;

//using System.Collections.Generic;

​

public class Program

{

    public static void Main(string[] args)

    {

        Console.WriteLine("Hello World");

        Test4();

    }

    public static void Test1()

    {

        // https://www.geeksforgeeks.org/heap-sort

        Tree tree = new Tree();

        tree.root = new Node(10);

        tree.root.left = new Node(5);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(1);

        tree.printInorder();

    }

​

    public static void Test2()

    {

        // https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree 

        Tree tree = new Tree();

        tree.root = new Node(50);

        tree.root.left = new Node(17);

        tree.root.right = new Node(72);

        tree.root.left.left = new Node(12);

        tree.root.left.right = new Node(23);

        tree.root.right.left = new Node(54);

        tree.root.right.right = new Node(76);

        tree.printInorder();

    }

    public static void Test3()

    {

        Tree tree = new Tree();

        tree.Add(12);

        tree.Add(17);

        tree.Add(23);

        tree.Add(50); // BST退化成链表 

        tree.printInorder();

    }

    public static void Test4()

    {

        Tree tree = new Tree();

        tree.Add(12);

        tree.Add(17);

        tree.Add(23);

        tree.Add(50); // BST退化成链表 

        tree.Remove(17);

        tree.printInorder();

        Console.WriteLine($"{tree.isContained(17)}");

        Console.WriteLine($"{tree.isContained(50)}");

        tree.Add(12);

        tree.Add(332);

        tree.Add(132);

        tree.Add(81);

        tree.Add(1);

        tree.Add(201);

        tree.Add(43);

        tree.Add(307);

        tree.printInorder();

    }

}

​

public class Tree // 二叉链表

{

    public Node root; // private Node head;

    // const function, won't modify the object

    public void printInorder(){ printInorder(root); }

    public void printInorder(Node n) // printNodes, inOrderDisplayTree

    {

        if (n != null){

            printInorder(n.left);

            Console.Write(n.data + " ");

            printInorder(n.right);

        }

    }

    //public void printPreorder(){

    //  printPreorder(root);

    //}

    //public void printPostorder(){

    //  printPostorder(root); // https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

    //}

    //public void Add(Object data)

    //{

        //

    //}

    public void Add(Object data){ root = Add(root, data); }

    // insert recursively   https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion 

​

    public Node Add(Node root, Object data)

    {

        if (root == null){

            root = new Node(data);

            return root;

        }

​

        if ((int)data < (int)root.data){

            root.left = Add(root.left, data);

        } else if ((int)data > (int)root.data){

            root.right = Add(root.right, data);

        } else {

            // (int)data == (int)root.data

            Console.WriteLine($"invalid data {(int)data}");

        }

        return root;

    }

​

​

    public void Remove(Object data){ root = Remove(root, data); }

    public Node Remove_(Node root, Object data)

    {

        if (root == null) return root;

        if ((int)data < (int)root.data){

            root.left = Remove(root.left, data);

        } else if ((int)data > (int)root.data){

            root.right = Remove(root.right, data);

        } else {

            // found ...

            root.data = root.right.left;

        }

        return root; // return the current status of the position  https://www.geeksforgeeks.org/binary-search-tree-set-2-delete 

    }

​

    public Node Remove(Node root, Object data)

    {

        if (root == null) return root;

        if ((int)data < (int)root.data){

            root.left = Remove(root.left, data); // *

        } else if ((int)data > (int)root.data){

            root.right = Remove(root.right, data);

        } else {

            // found

            if (root.left  == null)

                return root.right;

            else if (root.right == null)

                return root.left;

            root.data  = minValue(root.right);

            root.right = Remove(root.right, root.data);

        }

        return root; // return the current status of the position 

    }

    private int minValue(Node n){

        int min = (int)n.data;

        while (n.left != null){ min = (int)n.left.data; n = n.left; }

        return min;

    }

    public bool isContained(int target) // binary search to check if a value is contained in the array 

    {

    //  https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

        Node r = search(this.root, target);

        if (r == null) return false;

        return true;

    }

    private Node search(Node n, int target)

    {

        if (n == null) return n;

        // if ((int)n.data == target) return n;

        if ((int)n.data < target)

            return search(n.right, target);

        else if ((int)n.data > target)

            return search(n.left, target);

        else

            return n; // found 

    }

​

}

public class Node // 二叉链表的节点

{

    public Node left, right;

    public Object data;

    // 构造函数

    public Node(Object data){

        this.data = data;

        this.left = this.right = null;

    }

}

​

​

​

​

​

​

​

​