21 - II

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;


public class BinaryTree
{
    //    static int cnt = 0;
    // public void Reset() => cnt = 0;
    //  public int Solve() => cnt;
    private class Node
    {
        public object inf;
        public Node left;
        public Node rigth;

        public Node(object nodeInf)
        {
            inf = nodeInf;
            left = null;
            rigth = null;
        }
        public static void Add(ref Node root, object nodeInf)
        {
            if (root == null)
            {
                root = new Node(nodeInf);
            }
            else
            {
                if (((IComparable)(root.inf)).CompareTo(nodeInf) > 0)
                {
                    Add(ref root.left, nodeInf);
                }
                else
                {
                    Add(ref root.rigth, nodeInf);
                }
            }
        }
        public static void Solve(ref Node root) //прямой обход дерева
        {




            while (root != null && (int)root.inf < 0)
            {
                if (root.rigth != null)
                    root = root.rigth;
                else
                    root = null;
            }
            if (root != null)
            {
                Solve(ref root.left);
                Solve(ref root.rigth);
            }

        }
        public static void Preorder(Node root) //прямой обход дерева
        {
            if (root != null)
            {

                Console.Write("{0} ", root.inf);
                Preorder(root.left);
                Preorder(root.rigth);

            }
        }
        public static void Inorder(Node root) //симметричный обход дерева
        {
            if (root != null)
            {
                Inorder(root.left);
                Console.Write("{0} ", root.inf);
                Inorder(root.rigth);
            }
        }
        public static void Postorder(Node root) //обратный обход дерева
        {
            if (root != null)
            {
                Postorder(root.left);
                Postorder(root.rigth);
                Console.Write("{0} ", root.inf);
            }
        }
        //поиск ключевого узла в дереве
        public static void Search(Node r, object key, out Node item)
        {
            if (r == null)
            {
                item = null;
            }
            else
            {
                if (((IComparable)(r.inf)).CompareTo(key) == 0)
                {
                    item = r;
                }
                else

                {
                    if (((IComparable)(r.inf)).CompareTo(key) > 0)
                    {
                        Search(r.left, key, out item);
                    }
                    else
                    {
                        Search(r.rigth, key, out item);
                    }
                }
            }
        }
        //методы Del и Delete позволяют удалить узел в дереве так, чтобы дерево при этом
        //оставалось деревом бинарного поиска
        private static void Del(Node t, ref Node tr)
        {
            if (tr.rigth != null)
            {
                Del(t, ref tr.rigth);
            }
            else
            {
                t.inf = tr.inf;
                tr = tr.left;
            }
        }
        public static void Delete(ref Node t, object key)
        {
            if (t == null)
            {
                throw new Exception("Данное значение в дереве отсутствует");
            }
            else
            {
                if (((IComparable)(t.inf)).CompareTo(key) > 0)
                {
                    Delete(ref t.left, key);
                }
                else
                {
                    if (((IComparable)(t.inf)).CompareTo(key) < 0)
                    {
                        Delete(ref t.rigth, key);
                    }
                    else
                    {
                        if (t.left == null)
                        {
                            t = t.rigth;
                        }
                        else
                        {

                            if (t.rigth == null)
                            {
                                t = t.left;
                            }
                            else
                            {
                                Del(t, ref t.left);
                            }
                        }
                    }
                }
            }
        }
    } //конец вложенного класса
    Node tree; //ссылка на корень дерева
               //свойство позволяет получить доступ к значению информационного поля корня дерева

    public object Inf
    {
        set { tree.inf = value; }
        get { return tree.inf; }
    }
    public BinaryTree() //открытый конструктор
    {
        tree = null;
    }
    private BinaryTree(Node r) //закрытый конструктор
    {
        tree = r;
    }
    public void Add(object nodeInf) //добавление узла в дерево
    {
        Node.Add(ref tree, nodeInf);
    }
    //организация различных способов обхода дерева
    public void Preorder()
    {
        Node.Preorder(tree);
    }
    public void Solve()
    {
        Node.Solve(ref tree);
    }
    public void Inorder()
    {
        Node.Inorder(tree);
    }
    public void Postorder()
    {
        Node.Postorder(tree);
    }
    //поиск ключевого узла в дереве
    public BinaryTree Search(object key)
    {

        Node r;
        Node.Search(tree, key, out r);
        BinaryTree t = new BinaryTree(r);
        return t;
    }
    //удаление ключевого узла в дереве
    public void Delete(object key)
    {
        Node.Delete(ref tree, key);
    }
}


class Program
{
    static void Main(string[] args)
    {
        //добавить input
        BinaryTree tree = new BinaryTree();
        tree.Add(-5);
        tree.Add(10);
        tree.Add(-6);
        tree.Add(6);
        tree.Add(-4);
        tree.Add(-3);
        tree.Add(12);
        tree.Solve();
        tree.Preorder();
        Console.WriteLine();
        //Console.WriteLine($"Answer : {tree.Solve()} ");

    }

}