using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Tree
{



    class Wezel
    {
        public Wezel rodzic;
        public Wezel lewe;
        public Wezel prawe;
        public int numer;
        public int wartosc;
    }
    class Drzewo : Wezel
    {
        public
        Wezel root = null;
        int length = 0;

        public void push(int liczba)
        {
            Wezel nowy = new Wezel();
            nowy.wartosc = liczba;
            nowy.numer = length + 1;
            if (length == 0)
            {
                root = nowy;
            }
            else
            {
                int tmp = nowy.numer;
                List<int> kierunek = new List<int>();
                while (tmp > 1)
                {
                    kierunek.Add(tmp % 2);
                    tmp /= 2;
                }
                Wezel rodzic = root;
                for (int i = kierunek.Count() - 1; i >= 1; i--)
                {
                    if (kierunek[i] == 0)
                    {
                        rodzic = rodzic.lewe;
                    }
                    else
                    {
                        rodzic = rodzic.prawe;
                    }
                }
                if (kierunek[0] == 0)
                {
                    rodzic.lewe = nowy;
                }
                else
                {
                    rodzic.prawe = nowy;
                }
                nowy.rodzic = rodzic;
            }
            length++;
        }

        public void pop()
        {
            int wynik;
            if (length < 1)
            {
                Console.WriteLine("Brak drzewa");
            }
            else
            {
                Wezel nowy = new Wezel();
                if (length == 1)
                {
                    wynik = root.wartosc;
                    Console.WriteLine("Usunięto Drzewo: " + wynik);
                    root = null;
                }
                else
                {
                    int tmp = length;
                    List<int> kierunek = new List<int>();
                    while (tmp > 1)
                    {
                        kierunek.Add(tmp % 2);
                        tmp /= 2;
                    }
                    Wezel rodzic = root;
                    for (int i = kierunek.Count() - 1; i >= 1; i--)
                    {
                        if (kierunek[i] == 0)
                        {
                            rodzic = rodzic.lewe;
                        }
                        else
                        {
                            rodzic = rodzic.prawe;
                        }
                    }
                    if (kierunek[0] == 0)
                    {
                        wynik = rodzic.lewe.wartosc;
                        Console.WriteLine("Usunięto lewe dziecko: " + wynik);
                        rodzic.lewe = null;
                    }
                    else
                    {
                        wynik = rodzic.prawe.wartosc;
                        Console.WriteLine("Usunięto prawe dziecko: " + wynik);
                        rodzic.prawe = null;
                    }
                }
                length--;
                Console.WriteLine();
            }
        }

        public int Length()
        {
            return length;
        }
        public void show()
        {
            if (length < 1)
            {
                root = null;
                Console.WriteLine("Brak drzewa");
            }
            else
            {
                int tmp;
                List<int> kierunek = new List<int>();
                Wezel rodzic = root;
                Console.WriteLine("Korzeń " + rodzic.wartosc);
                for (int i = 2; i <= length; i++)
                {
                    rodzic = root;
                    tmp = i;
                    while (tmp > 1)
                    {
                        kierunek.Add(tmp % 2);
                        tmp /= 2;
                    }
                    for (int j = kierunek.Count() - 1; j > 0; j--)
                    {
                        if (kierunek[j] == 0)
                        {
                            rodzic = rodzic.lewe;
                        }
                        else
                        {
                            rodzic = rodzic.prawe;
                        }
                    }
                    if (kierunek[0] == 0)
                    {
                        Console.WriteLine("Lewe dziecko " + rodzic.lewe.wartosc + " Rodzic " + rodzic.wartosc);
                    }
                    else
                    {
                        Console.WriteLine("Prawe dziecko " + rodzic.prawe.wartosc + " Rodzic " + rodzic.wartosc);
                    }
                    kierunek.Clear();
                }
                Console.WriteLine();
            }
        }
        public void show2()
        {
            if (length < 1)
            {
                root = null;
                Console.WriteLine("Brak drzewa");
            }
            else
            {
                int tmp;
                List<int> kierunek = new List<int>();
                Wezel rodzic = root;
                Console.WriteLine("Korzeń " + rodzic.wartosc);
                for (int i = 2; i <= length; i++)
                {
                    rodzic = root;
                    tmp = i;
                    while (tmp > 1)
                    {
                        kierunek.Add(tmp % 2);
                        tmp /= 2;
                    }
                    for (int j = kierunek.Count() - 1; j > 0; j--)
                    {
                        if (kierunek[j] == 0)
                        {
                            rodzic = rodzic.lewe;
                        }
                        else
                        {
                            rodzic = rodzic.prawe;
                        }
                    }
                    if (kierunek[0] == 0)
                    {
                        Console.WriteLine("Lewe dziecko " + rodzic.lewe.wartosc);
                    }
                    kierunek.Clear();
                }
            }
            if (length < 1)
            {
                root = null;
                Console.WriteLine("Brak drzewa");
            }
            else
            {
                int tmp;
                List<int> kierunek = new List<int>();
                Wezel rodzic = root;
                for (int i = 2; i <= length; i++)
                {
                    rodzic = root;
                    tmp = i;
                    while (tmp > 1)
                    {
                        kierunek.Add(tmp % 2);
                        tmp /= 2;
                    }
                    for (int j = kierunek.Count() - 1; j > 0; j--)
                    {
                        if (kierunek[j] == 0)
                        {
                            rodzic = rodzic.lewe;
                        }
                        else
                        {
                            rodzic = rodzic.prawe;
                        }
                    }
                    if (kierunek[0] != 0)
                    {
                        Console.WriteLine("Prawe dziecko " + rodzic.prawe.wartosc);
                    }
                    kierunek.Clear();
                }
                Console.WriteLine();
            }
        }
        public void preorder(Wezel root)
        {
            Console.Write(root.wartosc + " ");
            if (root.lewe != null)
            {
                preorder(root.lewe);
            }
            if (root.prawe != null)
            {
                preorder(root.prawe);
            }
        }
        public void inorder(Wezel root)
        {
            if (root.lewe != null)
            {
                inorder(root.lewe);
            }
            Console.Write(root.wartosc + " ");
            if (root.prawe != null)
            {
                inorder(root.prawe);
            }
        }
        public void postorder(Wezel root)
        {
            if (root.lewe != null)
            {
                postorder(root.lewe);
            }
            if (root.prawe != null)
            {
                postorder(root.prawe);
            }
            Console.Write(root.wartosc + " ");
        }



        static void Main(string[] args)
        {
            Drzewo x = new Drzewo();
            x.push(9);
            x.push(13);
            x.push(14);
            x.push(15);
            x.push(16);
            x.push(17);
            x.push(19);
            x.show2();
            x.preorder(x.root);
            Console.WriteLine();
            Console.WriteLine();
            x.inorder(x.root);
            Console.WriteLine();
            Console.WriteLine();
            x.postorder(x.root);
            Console.WriteLine();
            Console.ReadKey();
        }
    }
}