zad8

using System;
using System.Collections.Generic;

namespace zad8
{
    class Węzeł
    {
        public int wartość;
        public Węzeł lewy;
        public Węzeł prawy;
    }

    class Drzewo
    {
        public Węzeł korzeń;
    }

    class Program
    {
        static Węzeł UtwórzWęzeł(int wartość)
        {
            Węzeł węzeł = new Węzeł();
            węzeł.wartość = wartość;
            return węzeł;
        }

        static void InicjujWęzeł(Węzeł węzeł, int wartość)
        {
            węzeł.wartość = wartość;
        }

        static void Wypisuj(Węzeł węzeł, int poziom)
        {
            string wcięcie = "";
            int p = poziom;
            while (p-- > 0) wcięcie += " ";
            if (węzeł == null) Console.WriteLine(wcięcie + "*");
            else
            {
                if (węzeł.lewy != null || węzeł.prawy != null)
                    Wypisuj((Węzeł)węzeł.prawy, poziom + 3);
                Console.WriteLine(wcięcie + węzeł.wartość);
                if (węzeł.lewy != null || węzeł.prawy != null)
                    Wypisuj((Węzeł)węzeł.lewy, poziom + 3);
            }
        }

        static void Wstaw(Drzewo drzewo, Węzeł węzeł)
        {
            if (drzewo.korzeń == null) drzewo.korzeń = węzeł;
            else
            {
                Węzeł tmp = drzewo.korzeń;
                while (tmp != null)
                {
                    if (tmp.wartość > węzeł.wartość)
                    {
                        if (tmp.lewy != null) tmp = tmp.lewy;
                        else
                        {
                            tmp.lewy = węzeł; return;
                        }
                    }
                    else
                    {
                        if (tmp.prawy != null) tmp = tmp.prawy;
                        else
                        {
                            tmp.prawy = węzeł; return;
                        }
                    }
                }
            }
        }

        static void LewaRotacja(Węzeł w)
        {
            if (w.prawy == null)
            {
                Console.WriteLine("Nie można obrócić!");
                return;
            }

            Drzewo poddrzewo = new Drzewo();
            Węzeł pomocniczy = UtwórzWęzeł(w.wartość);

            poddrzewo.korzeń = pomocniczy;
            poddrzewo.korzeń.prawy = w.prawy.lewy;
            poddrzewo.korzeń.lewy = w.lewy;

            w.wartość = w.prawy.wartość;
            w.lewy = poddrzewo.korzeń;
            w.prawy = w.prawy.prawy;
        }

        static void PrawaRotacja(Węzeł w)
        {
            if (w.lewy == null)
            {
                Console.WriteLine("Nie można obrócić!");
                return;
            }

            Drzewo poddrzewo = new Drzewo();
            Węzeł pomocniczy = UtwórzWęzeł(w.wartość);

            poddrzewo.korzeń = pomocniczy;
            poddrzewo.korzeń.lewy = w.lewy.prawy;
            poddrzewo.korzeń.prawy = w.prawy;

            w.wartość = w.lewy.wartość;
            w.prawy = poddrzewo.korzeń;
            w.lewy = w.lewy.lewy;
        }

        static int Wysokość(Węzeł węzeł)
        {
            int wysokość = 0;
            if (węzeł == null) return 0;
            if (węzeł.lewy != null)
                wysokość = Math.Max(wysokość, Wysokość(węzeł.lewy) + 1);
            if (węzeł.prawy != null)
                wysokość = Math.Max(wysokość, Wysokość(węzeł.prawy) + 1);
            return wysokość;
        }

        static void WstawJakoKorzeń(ref Drzewo drzewo, Węzeł węzeł)
        {
            int k = 0;
            int[] tab = new int[Wysokość(drzewo.korzeń) + 1];

            if (drzewo.korzeń == null) drzewo.korzeń = węzeł;
            else
            {
                Węzeł tmp = drzewo.korzeń;
                while (tmp != null)
                {
                    if (tmp.wartość > węzeł.wartość)
                    {
                        tab[k] = 0;
                        k++;
                        if (tmp.lewy != null) tmp = tmp.lewy;
                        else
                        {
                            tmp.lewy = węzeł;
                            break;
                        }
                    }
                    else
                    {
                        tab[k] = 1;
                        k++;
                        if (tmp.prawy != null) tmp = tmp.prawy;
                        else
                        {
                            tmp.prawy = węzeł;
                            break;
                        }
                    }
                }
            }
            for (int i = tab.Length - 1; i >= 0; --i)
            {
                Węzeł rodzic = drzewo.korzeń;

                for (int j = 0; j < i; ++j)
                {
                    if (tab[j] == 1)
                    {
                        rodzic = rodzic.prawy;
                    }
                    else
                    {
                        rodzic = rodzic.lewy;
                    }
                }
                if (tab[i] == 0)
                {
                    PrawaRotacja(rodzic);
                }
                else
                {
                    LewaRotacja(rodzic);
                }
            }
        }

        static void Main(string[] args)
        {
            int[] tab = { 10, 16, 12, 7, 9, 2, 21, 6, 17, 1, 15 };

            Drzewo drzewoA = new Drzewo();

            for (int i = 0; i < tab.Length; i++)
            {
                Węzeł w = new Węzeł();
                InicjujWęzeł(w, tab[i]);
                Wstaw(drzewoA, w);
            }

            Console.WriteLine("====PRZED WSTAWIENIEM====");
            Wypisuj(drzewoA.korzeń, 0);
            Węzeł nowy = UtwórzWęzeł(14);
            WstawJakoKorzeń(ref drzewoA, nowy);
            Console.WriteLine("====PO WSTAWIENIU====");
            Wypisuj(drzewoA.korzeń, 0);
            Console.ReadKey();
        }
    }
}