Бинарное поисковое дерево

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
 
 
namespace bts_sharp
{
    /// <summary>
    /// Класс "Бинарное поисковое дерево"
    /// </summary>
    public class Tree
    {
        /// <summary>
        /// Класс "узел БПД"
        /// </summary>
        private class Item
        {
            /// <summary>
            /// info - значение, хранящееся в узле
            /// lSon, rSon, father - ссылки на левого, правого сына и отца
            /// </summary>
            public int info;
            public int height;
            public Item lSon, rSon, father;
            /// <summary>
            /// Конструктор узла БПД
            /// </summary>
            /// <param name="x">значение, хранящееся в узле</param>
            public Item(int x)
            {
                info = x;
                lSon = rSon = father = null;
            }
        }
 
        /// <summary>
        /// ссылка на корень дерева
        /// </summary>
        private Item root;
        private List<int> list_1 = new List<int>();
        private List<int> list_2 = new List<int>();
        /// <summary>
        /// конструктор дерева
        /// </summary>
        public Tree()
        {
            root = null;
        }
 
        /// <summary>
        /// внутренняя процедура поиска
        /// </summary>
        /// <param name="x">искомое значение</param>
        /// <param name="p">ели найдено - ссылка на соответствующий узел, иначе - ссылка на то место, где остановились</param>
        /// <returns>нашли или нет</returns>
        private bool Find(int x, out Item p)
        {
            p = root;
            Item q = p;
            while (q != null)
            {
                p = q;
                if (q.info == x)
                    return true;
                if (q.info < x)
                    q = q.rSon;
                else
                    q = q.lSon;
            }
            return false;
        }
 
        /// <summary>
        /// внешняя процедура поиска
        /// </summary>
        /// <param name="x">искомое значение</param>
        /// <returns>нашли или нет</returns>
        public bool Find(int x)
        {
            Item p;
            return Find(x, out p);
        }
 
        /// <summary>
        /// втавка в БПД
        /// </summary>
        /// <param name="x">вставляемое значение</param>
        /// <returns>смогли вставить или нет</returns>
        public bool Insert(int x)
        {
            Item r, p;
            if (root == null)
            {
                r = new Item(x);
                root = r;
                return true;
            }
            if (Find(x, out r))
                return false;
            p = new Item(x);
            p.father = r;
            if (r.info < x)
                r.rSon = p;
            else
                r.lSon = p;
            return true;
        }
 
        /// <summary>
        /// удалить вершину (оборвать все ссылки)
        /// </summary>
        /// <param name="x">удаляемая вершина</param>
 
        public void Print()
        {
            PostOrder(root);
            check(root);
            PreOrder(root);
 
        }
 
        private void PreOrder(Item node)
        {
            if (node == null)
                return;
 
            Delete(vr);
            list_1.Add(node.info);
            PreOrder(node.lSon);
            PreOrder(node.rSon);
 
        }
 
        private void PostOrder(Item node)
        {
            if (node == null)
                return;
 
            PostOrder(node.lSon);
            PostOrder(node.rSon);
            node.height = Height(node);
 
            //Console.WriteLine(node.info + " " + node.height);
            if (node.height >= 2)
            {
                list_2.Add(node.info);
            }
        }
        private int Height(Item p)
        {
            if (p == null)
                return 0;
            int left, right;
            if (p.lSon != null)
                left = Height(p.lSon);
            else
                left = -1;
            if (p.rSon != null)
                right = Height(p.rSon);
            else
                right = -1;
            int max = left > right ? left : right;
            return max + 1;
        }
 
        public int vr;
 
        private void check(Item p)
        {       
            if(list_2.Count%2!=0)
                vr = list_2[list_2.Count / 2];          
        }
 
        public void p()
        {
            using (StreamWriter sw = new StreamWriter("tst.out"))
            {
                foreach (var s in list_1)
                    sw.WriteLine(s);
 
            }
        }
        private void deleteItem(Item x)
        {
            if (x.father == null)
                if (x.lSon != null)
                {
                    root = x.lSon;
                    x.lSon.father = null;
                }
                else
                {
                    root = x.rSon;
                    if (x.rSon != null)
                        x.rSon.father = null;
                }
            else
                if (x.father.lSon == x)
                    if (x.lSon != null)
                    {
                        x.father.lSon = x.lSon;
                        x.lSon.father = x.father;
                    }
                    else
                    {
                        x.father.lSon = x.rSon;
                        if (x.rSon != null)
                            x.rSon.father = x.father;
                    }
                else
                    if (x.lSon != null)
                    {
                        x.father.rSon = x.lSon;
                        x.lSon.father = x.father;
                    }
                    else
                    {
                        x.father.rSon = x.rSon;
                        if (x.rSon != null)
                            x.rSon.father = x.father;
                    }
            x.father = x.lSon = x.rSon = null;
        }
 
        /// <summary>
        /// Удалить вершину по значению
        /// </summary>
        /// <param name="x">удаляемое значение</param>
        /// <returns>смогли удалить или нет</returns>
        public bool Delete(int x)
        {
            Item r, p;
            if (!Find(x, out r))
                return false;
            if ((r.lSon == null) || (r.rSon == null))
            {
                deleteItem(r);
                return true;
            }
            p = r.lSon;
            while (p.rSon != null)
                p = p.rSon;
            r.info = p.info;
            deleteItem(p);
            return true;
        }
 
    }
    class Program
    {
        static void Main()
        {
 
            Tree tr = new Tree();
            var array = File.ReadAllLines("tst.in").Select(int.Parse).ToArray();
 
            foreach (int i in array)
            {
                tr.Insert(i);
            }
 
            tr.Print();
            tr.p();
 
 
        }
    }
}