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

namespace BST_1
{
    class Program
    {
        public class BinarySearchTree
        {
            class Węzeł
            {
                public int wartość;
                public Węzeł lewy;
                public Węzeł prawy;

                public Węzeł(int wartość)
                {
                    this.wartość = wartość;
                    lewy = prawy = null;
                }
            }

            Węzeł korzeń;

            public BinarySearchTree()
            {
                korzeń = null;
            }

            //DODAWANIE DO DRZEWA W WERSJI REKURENCYJNEJ
            public void dodaj(int wartość)
            {
                korzeń = DodajRekurencyjnie(korzeń, wartość);
            }
            Węzeł DodajRekurencyjnie(Węzeł korzeń, int wartość)
            {

                if (korzeń == null)
                {
                    korzeń = new Węzeł(wartość);
                    return korzeń;
                }

                if (wartość < korzeń.wartość)
                {
                    korzeń.lewy = DodajRekurencyjnie(korzeń.lewy, wartość);

                }
                else if (wartość > korzeń.wartość)
                {
                    korzeń.prawy = DodajRekurencyjnie(korzeń.prawy, wartość);
                }
                return korzeń;
            }



            //DODAWANIE DO DRZEWA W WERSJI ITERACYJNEJ
            public void DodajIteracyjnie(int wartość)
            {
                if (korzeń == null)
                {
                    korzeń = new Węzeł(wartość);
                }
                else
                {
                    Węzeł tmp = korzeń;
                    while (true)
                    {
                        if (wartość < tmp.wartość)
                        {
                            if (tmp.lewy == null)
                            {
                                tmp.lewy = new Węzeł(wartość);
                                return;
                            }
                            else
                            {
                                tmp = tmp.lewy;
                            }
                        }
                        else
                        {
                            if (tmp.prawy == null)
                            {
                                tmp.prawy = new Węzeł(wartość);
                                return;
                            }
                            else
                            {
                                tmp = tmp.prawy;
                            }
                        }
                    }
                }
            }


            //wypisywanie in-order
            public void InOrder()
            {
                InOrderRekurencyjnie(korzeń);
            }
            void InOrderRekurencyjnie(Węzeł korzeń)
            {
                if (korzeń != null)
                {
                    InOrderRekurencyjnie(korzeń.lewy);
                    Console.Write(korzeń.wartość + " ");
                    InOrderRekurencyjnie(korzeń.prawy);

                }
            }


            public void PostOrder()
            {
                PostOrderRekurencyjnie(korzeń);
            }
            void PostOrderRekurencyjnie(Węzeł korzeń)
            {
                if (korzeń != null)
                {
                    PostOrderRekurencyjnie(korzeń.lewy);
                    PostOrderRekurencyjnie(korzeń.prawy);
                    Console.WriteLine(korzeń.wartość);
                }
            }



            public void PreOrder()
            {
                PreOrderRekurencyjnie(korzeń);
            }
            void PreOrderRekurencyjnie(Węzeł korzeń)
            {
                if (korzeń != null)
                {
                    Console.WriteLine(korzeń.wartość);
                    PreOrderRekurencyjnie(korzeń.lewy);
                    PreOrderRekurencyjnie(korzeń.prawy);
                }
            }

            public void Usun(int wartość)
            {
                korzeń = UsunRekurencyjnie(korzeń, wartość);
            }
            Węzeł UsunRekurencyjnie(Węzeł korzeń, int wartość)
            {
                //jezeli puste
                if (korzeń == null) return korzeń;
                if (wartość < korzeń.wartość)
                {
                    korzeń.lewy = UsunRekurencyjnie(korzeń.lewy, wartość);
                }
                else if (wartość > korzeń.wartość)
                {
                    korzeń.prawy = UsunRekurencyjnie(korzeń.prawy, wartość);
                }
                else
                {
                    if (korzeń.lewy == null)
                        return korzeń.prawy;
                    if (korzeń.prawy == null)
                        return korzeń.lewy;
                    korzeń.wartość = Najmniejsza_Wartość(korzeń.prawy);

                    korzeń.prawy = UsunRekurencyjnie(korzeń.prawy, korzeń.wartość);

                }
                return korzeń;
            }


            public void Najmniejsza_Wartość()
            {
                Console.Write("Najmniejsza wartość " + Najmniejsza_Wartość(korzeń));
            }
            int Najmniejsza_Wartość(Węzeł korzeń)
            {
                int minimum = korzeń.wartość;
                while (korzeń.lewy != null)
                {
                    minimum = korzeń.lewy.wartość;
                    korzeń = korzeń.lewy;
                }
                return minimum;
            }


            public void Największa_Wartość()
            {
                Console.WriteLine("Największa wartość: " + Największa_Wartość(korzeń));
            }

            private int Największa_Wartość(Węzeł węzeł)
            {
                int maksimum = węzeł.wartość;
                if(korzeń.prawy != null)
                {
                    maksimum = węzeł.prawy.wartość;
                    węzeł = węzeł.prawy;
                }
                return maksimum;
            }



            //sprawdzenie czy drzewo binarne
            //czy występuje wartość w drzewie

            public bool CzyWystępuje(int wartość)
            {
                return CzyWystepujeRekurencyjnie(korzeń, wartość);
            }
            bool CzyWystepujeRekurencyjnie(Węzeł korzeń, int wartość)
            {
                if (korzeń == null)
                {
                    return false;
                }
                if (korzeń.wartość == wartość)
                {
                    return true;
                }
                if (wartość < korzeń.wartość)
                {
                    return CzyWystepujeRekurencyjnie(korzeń.lewy, wartość);
                }
                return CzyWystepujeRekurencyjnie(korzeń.prawy, wartość);
            }


        }

        static void Main(string[] args)
        {
            BinarySearchTree drzewo = new BinarySearchTree();
            //drzewo.WstawIter(50);
            //drzewo.WstawIter(30);
            //drzewo.WstawIter(20);
            //drzewo.WstawIter(40);
            drzewo.DodajIteracyjnie(6);
            drzewo.DodajIteracyjnie(3);
            drzewo.DodajIteracyjnie(1);
            drzewo.DodajIteracyjnie(2);
            drzewo.DodajIteracyjnie(4);
            drzewo.DodajIteracyjnie(5);
            drzewo.DodajIteracyjnie(7);
            drzewo.Usun(50);

            //drzewo.dodaj(50);
            //drzewo.dodaj(30);
            //drzewo.dodaj(20);
            //drzewo.dodaj(40);
            //drzewo.dodaj(70);
            //drzewo.dodaj(60);
            //drzewo.dodaj(80);
            //Console.WriteLine("Wypisywanie in-order");
            //drzewo.InOrder();
            //Console.WriteLine(" \n Delete 20");
            //drzewo.Usun(20);
            //Console.WriteLine("Wypisywanie in-order");
            drzewo.InOrder();
            //drzewo.Najmniejsza_Wartość();
            //drzewo.Największa_Wartość();
            //Console.WriteLine(" \n Delete 50");
            //drzewo.Usun(50);
            ////drzewo.dodaj(20);
            //drzewo.InOrder();
            //Console.WriteLine("Czy występuje wartość 70: " + drzewo.CzyWystępuje(70));
            //Console.WriteLine("Czy występuje wartość 120: " + drzewo.CzyWystępuje(120));
            //Console.WriteLine("Wypisywanie post-order");
            //drzewo.PostOrder();
            //Console.WriteLine("Wypisywanie pre-order");
            //drzewo.PreOrder();
            Console.ReadKey();

        }
    }
}