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

namespace BinaryTree
{
        public class BinaryNode
    {
        public BinaryNode Left { get; set; } // Левое поддерево
        public BinaryNode Right { get; set; } // Правое поддеревго
        public int value { get; set; } // Числовое значение вершины
        public int level { get; set; } // Уровень дерева, на котором находится вершина

        public BinaryNode(int value)
        {
            // Констркутор вершины
            // На вход даём числовое значение вершины

            this.value = value;
            Left = null;
            Right = null;
        }

        public int GetLevel()
        {
            return level;
        }
    }
        
    public class BinaryTree
    {
        public BinaryNode node_root;
        private int count;
        private int min_value;
        private int max_value;

        public BinaryTree(BinaryNode root_node)
        {
            // Констркутор бинарного дерева
            // На вход даём корневую вершину
            this.node_root = root_node;
            this.count = 1; // Поправка на корневую вершину
        }

        public int GetNodesCount()
        {
            return count;
        }

        public int GetMinValue()
        {
            return min_value;
        }

        public int GetMaxValue()
        {
            return max_value;
        }

        public void AddElement(int new_value)
        {
            if (new_value > max_value)
                max_value = new_value;
            else if (new_value < min_value)
                min_value = new_value;

            int level = 0;

            if (node_root == null)
            {
                node_root = new BinaryNode(new_value);
                node_root.level = level;
                count++;
                return;
            }
            else
                InsertElement(node_root, new_value, level);
        }        

        public void InsertElement(BinaryNode node, int new_value, int level)
        {
            level++;
            if (new_value > node.value) // Новый элемент > элемент
            {
                // Проверяем правую ветвь
                if (node.Right == null)
                {
                    node.Right = new BinaryNode(new_value);
                    node.Right.level = level + 1;
                    count++;
                }
                else
                    InsertElement(node.Right, new_value, level);
            }
            else // Новый элемент < элемент
            {
                // Проверяем левую ветвь
                if (node.Left == null)
                {
                    node.Left = new BinaryNode(new_value);
                    node.Left.level = level + 1;
                    count++;
                }
                else
                    InsertElement(node.Left, new_value, level);
            }
        }

        public bool FindValue(BinaryNode node, int search_value)
        {
            // На вход подаём корневую вершину

            if (search_value == node.value)
                return true;
            else if (search_value < node.value)
            {
                if (node.Left == null)
                    return false;
                else
                    return FindValue(node.Left, search_value);
            }
            else if (search_value > node.value)
            {
                if (node.Right == null)
                    return false;
                else
                    return FindValue(node.Right, search_value);
            }

            return false;
        }

        public bool FindNode(BinaryNode node, int search_value, ref BinaryNode result_node)
        {
            // На вход подаём корневую вершину

            if (search_value == node.value)
            {
                result_node = node;
                return true;
            }
            else if (search_value < node.value)
            {
                if (node.Left == null)
                    return false;
                else
                    return FindNode(node.Left, search_value, ref result_node);
            }
            else if (search_value > node.value)
            {
                if (node.Right == null)
                    return false;

                else
                    return FindNode(node.Right, search_value, ref result_node);
            }

            return false;
        }

        public bool FindNodeParent(BinaryNode node, int search_value, ref BinaryNode result_node)
        {
            // На вход подаём корневую вершину

            if (node.Left != null)
            {
                if (node.Left.value == search_value)
                {
                    result_node = node;
                    return true;
                }
                if (FindNodeParent(node.Left, search_value, ref result_node))
                    return true;
            }
            if (node.Right != null)
            {
                if (node.Right.value == search_value)
                {
                    result_node = node;
                    return true;
                }
                if (FindNodeParent(node.Right, search_value, ref result_node))
                    return true;
            }

            return false;
        }

        public void TraversePreorder(BinaryNode node) // Прямой обход дерева
        {
            // На вход подаём корневую вершину

            // Здесь можем выполнять какие-нибудь действия

            MessageBox.Show(Convert.ToString(node.value));

            if (node.Left != null)
                TraversePreorder(node.Left);
            if (node.Right != null)
                TraversePreorder(node.Right);
        }

        public void TraverseInorder(BinaryNode node) // Симметричный обход дерева
        {
            // На вход подаём корневую вершину

            if (node.Left != null)
                TraversePreorder(node.Left);

            // Здесь можем выполнять какие-нибудь действия

            MessageBox.Show(Convert.ToString(node.value));

            if (node.Right != null)
                TraversePreorder(node.Right);
        }

        public void TraversePostorder(BinaryNode node) // Обход дерева в обратном порядке
        {
            // На вход подаём корневую вершину

            if (node.Left != null)
                TraversePreorder(node.Left);
            if (node.Right != null)
                TraversePreorder(node.Right);

            // Здесь можем выполнять какие-нибудь действия

            MessageBox.Show(Convert.ToString(node.value));
        }

        public void TraverseDepth(BinaryNode node) // Обход дерева в ширину
        {
            // На вход подаём корневую вершину

            Queue<BinaryNode> children = new Queue<BinaryNode>();

            children.Enqueue(node); // Помещаем корень в очередь

            while(children.Count != 0) // Пока очередь не пуста
            {
                BinaryNode nodeT = children.Dequeue(); // Берём следующую вершину из очереди

                // Здесь можем выполнять какие-нибудь действия

                MessageBox.Show(Convert.ToString(nodeT.value));

                if (nodeT.Left != null)
                    children.Enqueue(nodeT.Left);
                if (nodeT.Right != null)
                    children.Enqueue(nodeT.Right);
            }
        }



        public bool RemoveNode(int value)
        {
            BinaryNode nodeT = new BinaryNode(6666);

            if (!FindNode(node_root, value, ref nodeT)) // Не найдена вершина для удаления
                return false;
            else
            {
                if (nodeT.Left == null && nodeT.Right == null) // Терминальная вершина
                {
                    BinaryNode nodeT2 = new BinaryNode(7777);

                    FindNodeParent(node_root, nodeT.value, ref nodeT2); // Ищем родительскую вершину для удаляемой вершины

                    if (nodeT2.Left == nodeT)
                    {
                        nodeT2.Left = null;
                        count--; // Уменьшаем счётчик количества вершин в дереве
                        return true;
                    }
                    else
                    {
                        nodeT2.Right = null;
                        count--; // Уменьшаем счётчик количества вершин в дереве
                        return true;
                    }
                }
                else if (nodeT.Left != null && nodeT.Right == null) // Имеет только левого потомка
                {
                    BinaryNode nodeT3 = new BinaryNode(8888);
                    FindNodeParent(node_root, nodeT.value, ref nodeT3); // Ищем родительскую вершину для удаляемой вершины
                    nodeT3.Left = nodeT.Left;
                    count--; // Уменьшаем счётчик количества вершин в дереве
                    return true;
                }
                else if (nodeT.Left == null && nodeT.Right != null) // Имеет только правого потомка
                {
                    BinaryNode nodeT4 = new BinaryNode(9000);
                    FindNodeParent(node_root, nodeT.value, ref nodeT4); // Ищем родительскую вершину для удаляемой вершины
                    nodeT4.Right = nodeT.Right;
                    count--; // Уменьшаем счётчик количества вершин в дереве
                    return true;
                }
                else if (nodeT.Left != null && nodeT.Right != null) // Имеет левого и правого потомка
                {
                    BinaryNode nodeT5 = new BinaryNode(9001);
                    FindNodeParent(node_root, nodeT.value, ref nodeT5); // Ищем родительскую вершину для удаляемой вершины

                    if (nodeT.Left.Right == null) // Левый потомок не имеет правого потомка
                    {
                        BinaryNode nodeTT = new BinaryNode(9002);
                        nodeTT = nodeT.Right;
                        nodeT5.Left = nodeT.Left;
                        nodeT.Left.Right = nodeTT;
                        count--; // Уменьшаем счётчик количества вершин в дереве
                        return true;
                    }
                    else if (nodeT.Left.Right != null) //Левый потомок имеет правого потомка
                    {
                        BinaryNode nodeT6 = new BinaryNode(9003);
                        FindNodeParent(node_root, nodeT.value, ref nodeT6); // Ищем родительскую вершину для удаляемой вершины

                        if (nodeT.Left.Right.Right == null) // Правый потомок левого потомка не имеет правого потомка
                        {
                            if (nodeT6.Left == nodeT) // Удаляемая вершина является левым потомком родительской вершины
                            {
                                nodeT6.Left = nodeT.Left.Right.Right;
                                
                            }
                            else
                            {
                                nodeT6.Right = nodeT.Left.Right.Right;

                            }
                        }
                    }
                }
            }

            return false;
        }
            
        private void FindRightNode()
        {

        }

            

    }
}