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

namespace Lab_Interfaces_10
{
    public interface ILimits<T>
    {
        T GetMinValue();
        T GetMaxValue();
    }

    public interface IOperations<T>
    {
        void AddElement(T data);
        bool RemoveElement(T data);
        bool FindElement(T data);
    }

    public class LinkedList<T> where T : IComparable<T>, IOperations<T>, ILimits<T>
    {
        public class Node<T>
        {
            public Node(T data)
            {
                Data = data;
            }

            public T Data { get; set; }
            public Node<T> Next { get; set; }

        }

        Node<T> head; // Первый элемент
        Node<T> tail; // Последний элемент
        int count;

        public void AddElement(T data)
        {
            Node<T> node = new Node<T>(data);

            if (head == null)
                head = node;
            else
                tail.Next = node;
            tail = node;

            count++;
        }

        public bool RemoveElement(T data)
        {
            Node<T> current = head;
            Node<T> previous = null;

            while (current != null)
            {
                if (current.Data.Equals(data))
                {
                    // Если узел в середине или в конце
                    if (previous != null)
                    {
                        // Убираем узел current, теперь previous ссылается не на current, а на current.Next
                        previous.Next = current.Next;

                        // Если current.Next не установлен, значит узел последний,изменяем переменную tail
                        if (current.Next == null)
                            tail = previous;
                    }
                    else
                    {
                        // Если удаляется первый элемент, переустанавливаем значение head
                        head = head.Next;

                        // Если после удаления список пуст, сбрасываем tail
                        if (head == null)
                            tail = null;
                    }

                    count--;
                    return true;
                }

                previous = current;
                current = current.Next;
            }

            return false;
        }

        public bool FindElement(T data)
        {
            Node<T> current = head;

            while (current != null)
            {
                if (current.Data.Equals(data))
                    return true;
                current = current.Next;
            }

            return false;
        }

        public void Clear()
        {
            head = null;
            tail = null;
            count = 0;
        }

        public T GetMinValue()
        {
            Node<T> val = head;
            Node<T> current = head;

            while (current != null)
            {
                int cv1 = val.Data.CompareTo(current.Data);
                if (cv1 < 0) // Новый элемент > элемент
                    val = current;
                current = current.Next;
            }

            return val.Data;
        }

        public T GetMaxValue()
        {
            Node<T> val = head;
            Node<T> current = head;

            while (current != null)
            {
                int cv1 = val.Data.CompareTo(current.Data);
                if (cv1 > 0) // Новый элемент < элемент
                    val = current;
                current = current.Next;
            }

            return val.Data;
        }

        public string GetStringPresentation()
        {
            string str = "";
            Node<T> current = head;
            if (current.Data != null)
                str += current.Data;

            while (current != null)
            {
                current = current.Next;
                if (current != null)
                    str += current.Data;
            }

            return str;
        }

    }

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

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

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

        // Возвращает уровень, накотором находится вершина
        public int GetLevel()
        {
            return level;
        }

        // Возвращает последнего правого потомка вершины
        public BinaryNode<T> GetLastRight()
        {
            return this.Right == null ? this : this.Right.GetLastRight();
        }

    }

    public class BinaryTree<T> where T : IComparable<T>, ILimits<T>, IOperations<T>
    {
        public BinaryNode<T> node_root; // Корневая вершина
        private int count; // Кол-во вершины
        private T min_value; // Минимальное значение вершины
        private T max_value; // Максимальное значение вершины
        private int max_level; // Уровень дерева

        public BinaryTree(BinaryNode<T> root_node)
        {
            this.node_root = root_node;
            this.count = 1; // Поправка на корневую вершину
            this.max_level = 0;
            //this.min_value = node_root.value;
            //this.max_value = node_root.value;
        }

        public BinaryTree()
        {
            this.node_root = null;
            this.count = 0; // Поправка на корневую вершину
            this.max_level = 0;
            //this.min_value = null;
            //this.max_value = int.MinValue;
        }

        // Возвращает количество вершин в дереве
        public int GetNodesCount() { return count; }
      

        // Возвращает минимальное значение вершины в дереве
        public T GetMinValue() { return min_value; }

        // Возвращает максимальное значение вершины в дереве
        public T GetMaxValue() { return max_value; }
        

        // Возвращает уровень дерева
        public int GetMaxLevel() { return max_level; }

        // Поиск максимального элемента с целью установки значения поля max_value
        public void FindMaxElement(BinaryNode<T> node)
        {
            if (node.Right != null)
                FindMaxElement(node.Right);
            else
                max_value = node.value;
        }

        // Поиск минимального элемента с целью установки значения поля min_value
        public void FindMinElement(BinaryNode<T> node)
        {
            if (node.Left != null)
                FindMinElement(node.Left);
            else
                min_value = node.value;
        }

        public void FindMaxElementTEMP()
        {
            BinaryNode<T> TempNode = node_root;
            while (TempNode.Right != null)
                TempNode = TempNode.Right;
            min_value = TempNode.value;
        }

        public void FindMinElementTEMP()
        {
            BinaryNode<T> TempNode = node_root;
            while (TempNode.Left != null)
                TempNode = TempNode.Left;
            min_value = TempNode.value;
        }

        // Добавление элемента - оболочка
        public void AddElement(T new_value)
        {

            int cv1 = max_value.CompareTo(new_value);
            if (cv1 < 0)
                max_value = new_value;
            int cv2 = min_value.CompareTo(new_value);
            if (cv2 > 0)
                min_value = new_value;



            //FindMaxElementTEMP();
            //FindMinElementTEMP();



            int level = 0;

            if (node_root == null)
            {
                node_root = new BinaryNode<T>(new_value);
                node_root.level = level;
                count++;
                return;
            }
            else
                AddElement(node_root, new_value, level);
        }

        // Добавление элемента - рекурсивная
        private void AddElement(BinaryNode<T> node, T new_value, int level)
        {

            int cv1 = node_root.value.CompareTo(new_value);

            if (cv1 < 0) // Новый элемент > элемент
            {
                // Проверяем правую ветвь
                if (node.Right == null)
                {
                    node.Right = new BinaryNode<T>(new_value);
                    node.Right.level = level;
                    count++; // Увеличение счётчика вершин в дереве
                    level++; // Увеличение уровня вершины

                    if (level > max_level)
                        max_level = level;
                }
                else
                    AddElement(node.Right, new_value, level + 1);
            }
            else if (cv1 > 0) // Новый элемент < элемент
            {
                // Проверяем левую ветвь
                if (node.Left == null)
                {
                    node.Left = new BinaryNode<T>(new_value);
                    node.Left.level = level;
                    count++; // Увеличение счётчика вершин в дереве
                    level++; // Увеличение уровня вершины

                    if (level > max_level)
                        max_level = level;
                }
                else
                    AddElement(node.Left, new_value, level + 1);
            }
        }

        // Удаление элемента
        public void RemoveElement(T value)
        {
            if (!FindElement(value))
                return;

            BinaryNode<T> delNode = FindNode(value);

            // Если это терминальная вершина
            if (delNode.Left == null && delNode.Right == null)
            {
                BinaryNode<T> delNodeParent = FindNodeParent(delNode.value); // Ищем родительскую вершину для удаляемой вершины

                if (delNodeParent.Left == delNode)
                {
                    delNodeParent.Left = null;
                    count--; // Уменьшаем счётчик количества вершин в дереве
                    FindMaxElement(node_root);
                    FindMinElement(node_root);
                    return;
                }
                else
                {
                    delNodeParent.Right = null;
                    count--; // Уменьшаем счётчик количества вершин в дереве
                    FindMaxElement(node_root);
                    FindMinElement(node_root);
                    return;
                }
            }

            // Удаляемая вершина имеет только левого потомка
            if (delNode.Left != null && delNode.Right == null)
            {
                BinaryNode<T> delNodeParent = FindNodeParent(delNode.value); // Ищем родительскую вершину для удаляемой вершины
                delNodeParent.Left = delNode.Left;
                count--; // Уменьшаем счётчик количества вершин в дереве
                FindMaxElement(node_root);
                FindMinElement(node_root);
                return;
            }

            // Удаляемая вершина имеет только правого потомка
            if (delNode.Left == null && delNode.Right != null)
            {
                BinaryNode<T> delNodeParent = FindNodeParent(delNode.value); // Ищем родительскую вершину для удаляемой вершины
                delNodeParent.Right = delNode.Right;
                count--; // Уменьшаем счётчик количества вершин в дереве
                FindMaxElement(node_root);
                FindMinElement(node_root);
                return;
            }

            // Удаляемая вершина имеет и левого, и правого потомка
            if (delNode.Left != null && delNode.Right != null)
            {
                BinaryNode<T> delNodeParent = FindNodeParent(delNode.value); // Ищем родительскую вершину для удаляемой вершины

                // Левый потомок удаляемой вершины не имеет правого потомка
                if (delNode.Left.Right == null)
                {
                    BinaryNode<T> tt = delNode.Right;
                    BinaryNode<T> tt2 = delNode.Left;
                    delNodeParent.Left = tt2;
                    delNode.Left.Right = tt;

                    count--; // Уменьшаем счётчик количества вершин в дереве
                    FindMaxElement(node_root);
                    FindMinElement(node_root);
                    return;
                }

                // Левый потомок удаляемой вершины имеет правого потомка
                if (delNode.Left.Right != null)
                {
                    BinaryNode<T> delNodeLeftLastRight = delNode.Left.GetLastRight();

                    // У крайней правой вершины от левого потомка удаляемой вершины нет левого потомка
                    if (delNodeLeftLastRight.Left == null)
                    {
                        BinaryNode<T> tt = delNode.Left;
                        tt.Right = null;
                        BinaryNode<T> tt2 = delNode.Right;
                        delNodeParent = delNodeLeftLastRight;
                        delNodeLeftLastRight.Left = tt;
                        delNodeLeftLastRight.Right = tt2;

                        count--; // Уменьшаем счётчик количества вершин в дереве
                        FindMaxElement(node_root);
                        FindMinElement(node_root);
                        return;
                    }
                    else
                    {
                        BinaryNode<T> t2 = delNode.Left;
                        BinaryNode<T> t3 = delNode.Right;
                        BinaryNode<T> delNodeLeftLastRightParent = FindNodeParent(delNodeLeftLastRight.value); // Родитель крайней правой вершины от левого потомка удаляемой вершины
                        delNodeLeftLastRightParent.Right = delNodeLeftLastRight.Left;
                        delNodeParent.Left = delNodeLeftLastRight;
                        delNodeParent.Left.Left = t2;
                        delNodeParent.Left.Right = t3;

                        count--; // Уменьшаем счётчик количества вершин в дереве
                        FindMaxElement(node_root);
                        FindMinElement(node_root);
                        return;
                    }
                }

            }
        }

        // Поиск элемента - оболочка
        public bool FindElement(T search_value)
        {
            return Find_Value(node_root, search_value) == true ? true : false;
        }

        // Поиск элемента - рекурсивная
        public bool Find_Value(BinaryNode<T> node, T search_value)
        {
            // На вход подаём корневую вершину

            int cv1 = node_root.value.CompareTo(search_value);

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

            return false;
        }

        // Поиск вершины - возвращает вершину с заданным значением - оболочка
        public BinaryNode<T> FindNode(T search_value)
        {
            return Find_Node(node_root, search_value);
        }

        // Поиск вершины - рекурсивная
        private BinaryNode<T> Find_Node(BinaryNode<T> node, T search_value)
        {
            int cv1 = node_root.value.CompareTo(search_value);

            if (cv1 == 0)
            {
                return node;
            }
            else if (cv1 > 0)
            {
                if (node.Left == null)
                    return null;
                else
                    return Find_Node(node.Left, search_value);
            }
            else if (cv1 < 0)
            {
                if (node.Right == null)
                    return null;

                else
                    return Find_Node(node.Right, search_value);
            }

            return null;
        }

        // Поиск родителя вершины - оболочка
        public BinaryNode<T> FindNodeParent(T search_value)
        {
            return Find_Node_Parent(node_root, search_value);
        }

        // Поиск родителя вершины - рекурсивная
        private BinaryNode<T> Find_Node_Parent(BinaryNode<T> node, T search_value)
        {
            if (node.Left != null)
            {
                int cv1 = node.Left.value.CompareTo(search_value);

                if (cv1 == 0)
                {
                    return node;
                }
                if (Find_Node_Parent(node.Left, search_value) != null)
                    return Find_Node_Parent(node.Left, search_value);
            }
            if (node.Right != null)
            {
                int cv1 = node.Right.value.CompareTo(search_value);

                if (cv1 == 0)
                {
                    return node;
                }
                if (Find_Node_Parent(node.Right, search_value) != null)
                    return Find_Node_Parent(node.Right, search_value);
            }

            return null;
        }

        // Прямой обход дерева
        public void TraversePreorder(BinaryNode<T> 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<T> node)
        {
            // На вход подаём корневую вершину

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

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

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

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

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

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

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

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

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

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

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

            while (children.Count != 0) // Пока очередь не пуста
            {
                BinaryNode<T> 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 void Clear()
        {
            node_root = null;
        }


    }


}