using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarySearchTree
{
    class TreeNode
    {
        public int data;
        public TreeNode parent;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int data)
        {
            this.data = data;
        }
    }
    class Tree
    {
        public TreeNode root;
        
        public void Insert(int data)
        {
            if (root == null)
            {
                root = new TreeNode(data);
                return;
            }
            TreeNode current = root;
            TreeNode parent = null;
            while (current != null)
            {
                parent = current;
                if(data < current.data)
                    current = current.left;
                else
                    current = current.right;
            }
            current = new TreeNode(data);
            current.parent = parent;
            if (data < parent.data)
                parent.left = current;
            else
                parent.right = current;
        }
        public void Remove(int data)
        {
            TreeNode node = FindNode(data);
            Remove(node);
        }
        private void Remove(TreeNode node)
        {
            if (node == null)
                return;
            if(node.left != null && node.right != null)
            {
                TreeNode s = Successor(node);
                node.data = s.data;
                node = s;
            }
            TreeNode replacement = node.left != null ? node.left : node.right;
            if (replacement != null)
            {
                replacement.parent = node.parent;
                if (node.parent == null)
                    root = replacement;
                else if (node == node.parent.left)
                    node.parent.left = replacement;
                else
                    node.parent.right = replacement;
            }
            else if(node.parent == null)//是叶子结点，并且是根节点
            {
                root = null;
            }
            else//是叶子结点，但不是根节点
            {
                if (node == node.parent.right)
                    node.parent.right = null;
                else
                    node.parent.left = null;
            }
        }
        private TreeNode Successor(TreeNode root)
        {
            if (root == null)
                return null;
            TreeNode node = root.right;
            if (node != null)
            {
                while (node.left != null)
                {
                    node = node.left;
                }
                return node;
            }
            while (node.parent != null && node == node.parent.right)
            {
                node = node.parent;
            }
            return node.parent;
        }
        public TreeNode FindNode(int data)
        {
            TreeNode current = root;
            while (current != null)
            {
                if (data < current.data)
                    current = current.left;
                else if (data > current.data)
                    current = current.right;
                else
                    return current;
            }
            return null;
        }
        public void PreOrder(TreeNode root)
        {
            if (root == null)
            {
                return;
            }
            Console.Write(root.data + " ");
            PreOrder(root.left);
            PreOrder(root.right);
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Tree tree = new Tree();
            int[] arr = new int[] { 7, 4, 9, 2, 5, 8, 11, 3, 12, 1 };
            foreach (var item in arr)
            {
                tree.Insert(item);
            }
            tree.Remove(7);
            tree.PreOrder(tree.root);
            Console.ReadKey();
        }
    }
}