all

//BSF
static class Zadanie4 //BFS
        {
            static int n = 7;
            static List<List<bool>> graph = new List<List<bool>>
            {
                new List<bool>(){false, false, false, false, false, false, false},
                new List<bool>(){false, false, true, false, false, true, false},
                new List<bool>(){false, true, false, true, false, true, false},
                new List<bool>(){false, false, true, false, true, false, false},
                new List<bool>(){false, false, false, true, false, true, true},
                new List<bool>(){false, true, true, false, true, false, false},
                new List<bool>(){false, false, false, false, true, false, false}
            };
            static bool[] visited = new bool[n];

            public static void BFS()
            {
                var paths = Reconstruct(Solve(1, 7), 2);
            }

            public static List<List<int>> Reconstruct(int?[] prev, int s)
            {
                List<List<int>> paths = new List<List<int>>();

                for (int i = s; i < prev.Length; i++)
                {
                    List<int> path = new List<int>();
                    int? val = i;
                    while (val != null)
                    {
                        path.Add((int)val);
                        val = prev[(int)val];

                    }

                    path.Reverse();
                    paths.Add(path);
                }

                return paths;
            }

            public static int?[] Solve(int s, int n)
            {
                int?[] prev = new int?[n];

                Queue<int> q = new Queue<int>();
                q.Enqueue(s);
                visited[s] = true;

                while (q.Count != 0)
                {
                    int node = q.Dequeue();
                    var neighbours = graph[node];

                    for (int i = 0; i < neighbours.Count; i++)
                    {
                        if (neighbours[i] && !visited[i])
                        {
                            prev[i] = node;
                            visited[i] = true;
                            q.Enqueue(i);
                        }
                    }
                }

                return prev;
            }
        }

static void Zadanie4()
        {
             int n = 7;
             List<List<bool>> graph = new List<List<bool>>
            {
                new List<bool>(){false, false, false, false, false, false, false},
                new List<bool>(){false, false, true, false, false, true, false},
                new List<bool>(){false, true, false, false, false, true, false},
                new List<bool>(){false, false, true, false, true, false, false},
                new List<bool>(){false, false, false, true, false, true, true},
                new List<bool>(){false, true, true, false, true, false, false},
                new List<bool>(){false, false, false, false, true, false, false}
            };
             bool[] visited = new bool[7];
             var drzewo = Solve(1, 6, graph, visited);
        }

        static List<List<int>> Solve(int s, int n, List<List<bool>> graph, bool[] visited)
        {
            List<List<int>> drzewo = new List<List<int>>();

            Queue<int> q = new Queue<int>();
            q.Enqueue(s);
            visited[s] = true;

            while (q.Count != 0)
            {
                int node = q.Dequeue();
                var neighbours = graph[node];
                for (int i = 0; i < neighbours.Count; i++)
                {
                    if (neighbours[i] && !visited[i])
                    {
                        drzewo.Add(new List<int>() { node, i });
                        q.Enqueue(i);
                        visited[i] = true;
                    }
                }
            }

            return drzewo;
        }

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

namespace PreORderv2
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] t = { 6, 3, 1, 2, 4, 5, 7 };
            //int[] t = { 6, 3, 1, 2, 4, 7, 5 };
            Tree root = null;

            int i = 0;
            bool badTree = false;

            root = constructTree(t, ref i, Int32.MaxValue);

            WypiszDrzewo(root);

            Console.ReadKey();
        }

        class Tree
        {
            public int val;
            public Tree left;
            public Tree right;

            public Tree(int val)
            {
                this.val = val;
            }
        }

        static void WypiszDrzewo(Tree root)
        {
            if (root == null)
                return;

            Queue<Tree> q = new Queue<Tree>();
            q.Enqueue(root);

            while (true)
            {
                int nodeCount = q.Count;
                if (nodeCount == 0)
                    break;

                while (nodeCount > 0)
                {
                    Tree node = q.Dequeue();
                    Console.Write(node.val + " ");

                    if (node.left != null)
                        q.Enqueue(node.left);
                    if (node.right != null)
                        q.Enqueue(node.right);
                    nodeCount--;
                }
                Console.WriteLine();
            }
        }
        static bool IsValid(int[] pre)
        {
            Stack<int> s = new Stack<int>();
            int? lowerBound = null;

            for (int i = 0; i < pre.Length; i++)
            {
                if (lowerBound != null && pre[i] < lowerBound) return false;
                while (s.Count != 0 && s.Peek() < pre[i]) lowerBound = s.Pop();
                s.Push(pre[i]);
            }

            return true;
        }

        static Tree constructTree(int[] pre, ref int i, int high)
        {
            if (!IsValid(pre)) return null;
            else
            {
                if (i >= pre.Length || pre[i] > high) return null;

                Tree root = new Tree(pre[i++]);
                root.left = constructTree(pre, ref i, root.val);
                root.right = constructTree(pre, ref i, high);
                return root;
            }
        }
    }
}


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

namespace PreOreder
{
    class Program
    { //odtwórz drzewo na bazie przejscia go w PreOrder
        static void Main(string[] args)
        {
            int[] tab = { 6, 3, 1, 2, 4, 5, 7 };
            //int[] tab = { 6, 3, 1, 2, 4, 7, 5 };

            Drzewo d = Drzewo.BudujZPreOrder(tab);

            if (d != null)
                d.Wyswietl();
            else
                Console.WriteLine("Drzewo było null");

            Console.ReadKey();
        }
    }

    class Drzewo
    {
        public Element głowa;

        public static Drzewo BudujZPreOrder(int[] tab)
        {
            Drzewo d = new Drzewo();
            d.głowa = new Element(tab[0]);

            for (int i = 1; i < tab.Length; i++)
            {
                Element tmp = d.głowa;

                while(tmp != null)
                {
                    if (tab[i] < tmp.wartosc)
                    {
                        if (tmp.prawy != null)
                        {
                            return null;
                        }
                        if (tmp.lewy != null)
                        {
                            tmp = tmp.lewy;
                        }
                        else
                        {
                            tmp.lewy = new Element(tab[i]);
                            tmp = null;
                        }
                    }
                    else
                    {
                        if (tmp.prawy != null)
                        {
                            tmp = tmp.prawy;
                        }
                        else
                        {
                            tmp.prawy = new Element(tab[i]);
                            tmp = null;
                        }
                    }
                }
            }
            return d;
        }

        public void Wyswietl()
        {
            if (głowa == null)
            {
                Console.WriteLine("Drzewo bez glowy!");
                return;
            }

            głowa.WyswietlPoddrzewo();
        }


    }
    class Element
    {
        public Element(int w) => wartosc = w;
        public int wartosc;
        public Element lewy;
        public Element prawy;

        public void WyswietlPoddrzewo()
        {
            Console.WriteLine(wartosc + " ");
            if (lewy != null)
            {
                lewy.WyswietlPoddrzewo();
            }
            if (prawy != null)
            {
                prawy.WyswietlPoddrzewo();
            }
        }

        public override string ToString()
        {
            return wartosc.ToString();
        }
    }
}



//metody in, post, pre
using System;
using System.Collections;

//Zadanie 2
//Dla drzewa binarnego w implementacji dowiązaniowej napisz:
//a) metodę wyszukującą czy istnieje element(węzeł) o zadanej wartości.
//b) metodę przechodzenia pre-order nierekurencyjną(wsk.wykorzystaj stos)
// klasa pomocnicza Węzeł
class Węzeł
{
    public String wartość;
    public Węzeł lewy;
    public Węzeł prawy;
}

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

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

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

    static void DodajLewy(Węzeł węzeł, Węzeł dziecko)
    {
        węzeł.lewy = dziecko;
    }
    static void DodajPrawy(Węzeł węzeł, Węzeł dziecko)
    {
        węzeł.prawy = dziecko;
    }

    // pre-order
    static void WypisujPre(Węzeł węzeł)
    {
        if (węzeł == null) return;
        Console.Write(węzeł.wartość + " ");
        WypisujPre((Węzeł)węzeł.lewy);
        WypisujPre((Węzeł)węzeł.prawy);
    }

    // post-order
    static void WypisujPost(Węzeł węzeł)
    {
        if (węzeł == null) return;
        WypisujPost((Węzeł)węzeł.lewy);
        WypisujPost((Węzeł)węzeł.prawy);
        Console.Write(węzeł.wartość + " ");
    }

    // in-order
    static void WypisujIn(Węzeł węzeł)
    {
        if (węzeł == null) return;
        WypisujIn((Węzeł)węzeł.lewy);
        Console.Write(węzeł.wartość + " ");
        WypisujIn((Węzeł)węzeł.prawy);
    }

    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ść;
    }// Zwraca wynik

    // metodę wyszukującą czy istnieje element(węzeł) o zadanej wartości.


    static Węzeł CzyIstniejeWęzeł(Drzewo d, string s)
    {
        return CzyIstniejeWęzeł(d.korzeń, s);
    }
    static Węzeł CzyIstniejeWęzeł(Węzeł w, string s)
    {
        if (w == null) return null;

        if (w.wartość == s) return w; // znalazłem
        if (w.lewy != null)
        {
            Węzeł t = CzyIstniejeWęzeł(w.lewy, s);
            if (t != null) return t; // znalazłem
        }
        return CzyIstniejeWęzeł(w.prawy, s);
    }

    //metodę przechodzenia pre-order nierekurencyjną
    static void WypisujPreNierekurencyjnie(Węzeł węzeł)
    {
        if (węzeł == null) return;
        Stack s = new Stack();
        s.Push(węzeł);
        while(s.Count>0)
        {
            Węzeł tmp = (Węzeł)s.Pop();
            Console.Write(tmp.wartość + " ");
            if(tmp.prawy!=null)
                s.Push(tmp.prawy);
            if(tmp.lewy!=null)
                s.Push(tmp.lewy);
        }
    }
    static void Main()
    {
        Drzewo drzewo = new Drzewo();

        drzewo.korzeń = UtwórzWęzeł("F");
        Węzeł wB = UtwórzWęzeł("B");
        Węzeł wA = UtwórzWęzeł("A");
        Węzeł wC = UtwórzWęzeł("C");
        Węzeł wD = UtwórzWęzeł("D");
        Węzeł wE = UtwórzWęzeł("E");
        Węzeł wG = UtwórzWęzeł("G");
        Węzeł wH = UtwórzWęzeł("H");
        Węzeł wI = UtwórzWęzeł("I");
        Węzeł wX = UtwórzWęzeł("X");

        DodajLewy(wD, wC);
        DodajPrawy(wD, wE);
        DodajPrawy(wA, wX);
        DodajLewy(wB, wA);
        DodajPrawy(wB, wD);

        DodajLewy(wI, wH);
        DodajPrawy(wG, wI);

        DodajLewy(drzewo.korzeń, wB);
        DodajPrawy(drzewo.korzeń, wG);

        WypisujPre(drzewo.korzeń);
        Console.WriteLine();
        WypisujPost(drzewo.korzeń);
        Console.WriteLine();
        WypisujIn(drzewo.korzeń);
        Console.WriteLine();
        Console.WriteLine("wysokość = " + Wysokość(drzewo.korzeń));

        Węzeł t = CzyIstniejeWęzeł(drzewo, "X");
        Console.WriteLine(t != null);
        t = CzyIstniejeWęzeł(drzewo, "A");
        Console.WriteLine(t != null);
        t = CzyIstniejeWęzeł(drzewo, "G");
        Console.WriteLine(t != null);
        t = CzyIstniejeWęzeł(drzewo, "Z");
        Console.WriteLine(t != null);

        WypisujPreNierekurencyjnie(drzewo.korzeń);

        Console.ReadKey();
    }
}

//Gafy zajecia
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

//Zadanie 1
//A)
//Dla prostego grafu nieskierowanego bez wag krawędzi, napisz metodę
//    konwertująca reprezentację w postaci macierzy sąsiedztw na reprezentację w postaci list sąsiedztwa.
//    Przetestuj jej działanie na przykład dla grafu z wykładu.


class Program
{
    // numeracja od 0
    static List<int>[] KonwersjaNaListy(int[,] G)
    {
        List<int>[] graf = new List<int>[G.GetLength(0)];
        for(int i =0; i< graf.Length;i++)
        {
            graf[i] = new List<int>();
            for (int j = 0; j < G.GetLength(0); j++)
                if (G[i, j] != 0) graf[i].Add(j);
        }
        return graf;
    }
    static void Main(string[] args)
    {
        int[,] G = {
        { 0, 1, 0, 0, 1, 0 },
        { 1, 0, 1, 0, 1, 0 },
        { 0, 1, 0, 1, 0, 0 },
        { 0, 0, 1, 0, 1, 1 },
        { 1, 1, 0, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0 }
        };

        List<int>[] graf = KonwersjaNaListy(G);
        for (int i = 0; i < graf.Length; i++)
        {
            Console.Write("L("+i+") = {");
            for (int j = 0; j < graf[i].Count-1; j++)
               Console.Write(graf[i][j]+", ");
            Console.Write(graf[i][graf[i].Count - 1] + "}");
            Console.WriteLine();
        }

        Console.ReadKey();
    }
}

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

//B)
//| 1 0 0 3 0 0 7 |
//| 0 0 2 0 4 0 1 |
//| 0 2 0 4 1 2 3 |
//| 3 0 4 0 5 3 3 |
//| 0 4 1 5 0 1 2 |
//| 0 0 2 3 1 0 2 |
//| 7 1 3 3 2 2 0 |

//Narysuj graf G(w B wartości oznaczają wagi a nie liczbę krawędzi).
//Napisz metodę przechodzenia grafu w głąb i zastosuj dla grafu G

class Program
{
    //    Bierzemy pierwszy wierzchołek, kłADZIEMY NA STOS .
    //    Następnie kolejno pobieramy wierzchołek ze stosu,
    //    jeśli nie był już odwiedzony to odwiedzamy go
    //    i wkładamy wszystkich jego nieodwiedzonych sąsiadów na stos
    //    w kolejności od tego z największym indeksem (czyli od końca).
    //    Kontynuujemy aż stos będzie pusty.

        // NA MACIERZY SASIEDZTWA

    static void DFS(int[,] G, int v)
    {
        Stack<int> stos = new Stack<int>();
        bool[] odwiedzony = new bool[G.GetLength(0)];
        stos.Push(v);
        while (stos.Count > 0)
        {
            v = stos.Pop();
            if (!odwiedzony[v])
            {
                Console.WriteLine(v);
                odwiedzony[v] = true;
                // wkładam od końca wtedy kompatybilnie z rekurencją
                for (int i = G.GetLength(0) -1; i >= 0; i--)
                {
                    if (G[v,i] != 0 && !odwiedzony[i])
                    {
                        stos.Push(i);
                    }
                }
            }
        }
    }

    //REKURENCJA
    // NA MACIERZY SASIEDZTWA

    static bool[] visited ;

    static void DFSRekurencja(int[,] G, int v)
    {
        Console.WriteLine(v);
        visited[v] = true;
        // tu wkładam po kolei, nie od końca
        for (int i = 0; i < G.GetLength(0); i++)
        {
            if (G[v, i] != 0 && !visited[i])
            {
                DFSRekurencja(G, i);
            }
        }
    }

    static void Main(string[] args)
    {
        int[,] G = {
        {  1, 0, 0, 3, 0, 0, 7  },
        {  0, 0, 2, 0, 4, 0, 1  },
        {  0, 2, 0, 4, 1, 2, 3  },
        {  3, 0, 4, 0, 5, 3, 3  },
        {  0, 4, 1, 5, 0, 1, 2  },
        {  0, 0, 2, 3, 1, 0, 2  },
        {  7, 1, 3, 3, 2, 2, 0  }
        };

        DFS(G, 4);
        Console.WriteLine();
        visited = new bool[G.GetLength(0)];
        DFSRekurencja(G,4);
        Console.ReadKey();

    }
}

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

//B)
// WESJA WSZERZ
// NA MACIERZY SASIEDZTWA

//| 1 0 0 3 0 0 7 |
//| 0 0 2 0 4 0 1 |
//| 0 2 0 4 1 2 3 |
//| 3 0 4 0 5 3 3 |
//| 0 4 1 5 0 1 2 |
//| 0 0 2 3 1 0 2 |
//| 7 1 3 3 2 2 0 |

//Narysuj graf G(w B wartości oznaczają wagi a nie liczbę krawędzi).
//Napisz metodę przechodzenia grafu w WsZERZ i zastosuj dla grafu G

class Program
{
    static void BFS(int[,] G, int v)
    {
        Queue<int> kolejka = new Queue<int>();
        bool[] odwiedzony = new bool[G.GetLength(0)];
        kolejka.Enqueue(v);
        while (kolejka.Count > 0)
        {
            v = kolejka.Dequeue();
            if (!odwiedzony[v])
            {
                Console.WriteLine(v);
                odwiedzony[v] = true;
                // do kolejki mogą być włożone powtórnie te które już są
                for (int i = 0; i < G.GetLength(0); i++)
                {
                    if (G[v, i] != 0 && !odwiedzony[i])
                    {
                        kolejka.Enqueue(i);
                    }
                }
            }
        }
    }

    // TERAZ TYLKO RAZ JEST WKLADANY DO KOLEJKI
    //
    // gdyby tak zrobic dla DFS i wkładać na stos tylko niewłożone
    // to wynik byłby inny a dla kolejki wynik jest taki sam jak wyżej

    static void BFS1(int[,] G, int v)
    {
        Queue<int> kolejka = new Queue<int>();
        bool[] wlozony = new bool[G.GetLength(0)];
        kolejka.Enqueue(v);
        wlozony[v] = true;

        while (kolejka.Count > 0)
        {
            v = kolejka.Dequeue();
            Console.WriteLine(v);

            for (int i = 0; i < G.GetLength(0); i++)
            {
                // jak włożony to drugi raz nie włożymy
                if (G[v, i] != 0 && !wlozony[i])
                {
                    kolejka.Enqueue(i);
                    wlozony[i] = true;
                }
            }
        }
    }

    static void Main(string[] args)
    {
        int[,] G =
        {
            {  1, 0, 0, 3, 0, 0, 7  },
            {  0, 0, 2, 0, 4, 0, 1  },
            {  0, 2, 0, 4, 1, 2, 3  },
            {  3, 0, 4, 0, 5, 3, 3  },
            {  0, 4, 1, 5, 0, 1, 2  },
            {  0, 0, 2, 3, 1, 0, 2  },
            {  7, 1, 3, 3, 2, 2, 0  }
        };
        BFS(G, 4);
        Console.WriteLine();
        BFS1(G, 4);
        Console.WriteLine();

        Console.ReadKey();

    }
}

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

//Zadanie 3
//    Zaimplementuj graf z zadania 2 B jako listy sąsiedztwa.
//    Napisz dla takiej reprezentacji metodę przechodzenia grafu w głąb.
class Krawedz
{
   public int wierzcholek;
   public int waga;
    public Krawedz(int v, int w)
    {
        wierzcholek = v;
        waga = w;
    }
}

class Program
{
    static List<List<Krawedz>> KonwertujNaListę(int[,] G)
    {
        List<List<Krawedz>> graf = new List<List<Krawedz>>();
        for (int i = 0; i < G.GetLength(0); i++)
        {
            graf.Add(new List<Krawedz>());
            for (int j = 0; j < G.GetLength(1); j++)
                if (G[i, j] != 0) graf[i].Add(new Krawedz(j, G[i,j]));
        }
        return graf;
    }

    // wypisuję tylko kolejne wierzchołki na ekran
    static void DFS(List<List<Krawedz>> graf, int s)
    {
        int[] wizyty = new int[graf.Count];
        Stack<int> stos = new Stack<int>();
        stos.Push(s);
        while(stos.Count>0)
        {
            int v = stos.Pop();
            if(wizyty[v] == 0)
            {
                Console.WriteLine(v);
                wizyty[v] = 1;
                for(int i =0;i<graf[v].Count;i++)
                {
                    if(wizyty[graf[v][graf[v].Count - i - 1].wierzcholek] == 0)
                    {
                        stos.Push(graf[v][graf[v].Count - i - 1].wierzcholek);
                    }
                }
            }
        }
    }

    static void Main(string[] args)
    {
        int[,] G = {
        { 1, 0, 0, 3, 0, 0, 7 },
        { 0, 0, 2, 0, 4, 0, 1 },
        { 0, 2, 0, 4, 1, 2, 3 },
        { 3, 0, 4, 0, 5, 3, 3 },
        { 0, 4, 1, 5, 0, 1, 2 },
        { 0, 0, 2, 3, 1, 0, 2 },
        { 7, 1, 3, 3, 2, 2, 0 }
        };

        List<List<Krawedz>> graf = KonwertujNaListę(G);
        DFS(graf, 0);
        Console.ReadKey();
    }
}

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

class Krawedz
{
    public int wierzcholek;
    public int waga;
    public Krawedz(int v, int w)
    {
        wierzcholek = v;
        waga = w;
    }
}
//Zadanie 4
//Zaimplementuj algorytm Dijkstry zgodnie z pseudokodem podanym na wykładzie.
//    Dla grafów z zadania 2 wypisz krok po kroku realizację algorytmu Dijkstry,
//    wybierając jako startowy wierzchołek pierwszy(w przypadku B ten z krawędzią cykliczną).
    class Program
    {
    static List<Krawedz>[] KonwersjaNaListy(int[,] G)
    {
        List<Krawedz>[] graf = new List<Krawedz>[G.GetLength(0)];
        for (int i = 0; i < graf.Length; i++)
        {
            graf[i] = new List<Krawedz>();
            for (int j = 0; j < G.GetLength(0); j++)
                if (G[i, j] != 0) graf[i].Add(new Krawedz(j, G[i,j]));
        }
        return graf;
    }

    // NA LISTACH SASIEDZTWA

    static void Dijkstra(List<Krawedz>[] graf, int v)
    {
        int[] poprzednik = new int[graf.Length];
        bool[] policzony = new bool[graf.Length];
        int[] wagi = new int[graf.Length];
        for (int i = 0; i < wagi.Length; i++)
        {
            wagi[i] = int.MaxValue/2;
            poprzednik[i] = - 1;
        }
        wagi[v] = 0;
        policzony[v] = true;
        for (int i = 0; i < graf[v].Count; i++)
        {
            if (!policzony[graf[v][i].wierzcholek])
            {
                wagi[graf[v][i].wierzcholek] = graf[v][i].waga;
                poprzednik[graf[v][i].wierzcholek] = v;
            }
        }


        for (int i = 1; i < graf.Length; i++)
        {
            int min = int.MaxValue;
            int minInd = -1;
            for (int j = 0; j < wagi.Length; j++)
            {
                if (wagi[j]<min && !policzony[j])
                {
                    min = wagi[j];
                    minInd = j;
                }
            }
            policzony[minInd] = true;
            for (int j = 0; j < graf[minInd].Count; j++)
            {
                if (wagi[minInd]+graf[minInd][j].waga<wagi[graf[minInd][j].wierzcholek])
                {
                    if (!policzony[graf[minInd][j].wierzcholek])
                    {
                        wagi[graf[minInd][j].wierzcholek] = wagi[minInd] + graf[minInd][j].waga;
                        poprzednik[graf[minInd][j].wierzcholek] = minInd;
                    }
                }
            }

        }
        for (int i = 0; i<wagi.Length;i++)
        {
            Console.WriteLine(wagi[i] + "  " + poprzednik[i]);
        }
    }

    static void Main(string[] args)
        {
        int[,] G = {
        {  1, 0, 0, 3, 0, 0, 7  },
        {  0, 0, 2, 0, 4, 0, 1  },
        {  0, 2, 0, 4, 1, 2, 3  },
        {  3, 0, 4, 0, 5, 3, 3  },
        {  0, 4, 1, 5, 0, 1, 2  },
        {  0, 0, 2, 3, 1, 0, 2  },
        {  7, 1, 3, 3, 2, 2, 0  }
        };

        List<Krawedz>[] graf = KonwersjaNaListy(G);
        Dijkstra(graf, 0);
        Console.ReadKey();
    }
    }

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

// WERSJA NA MACIERZY SASIEDZTWA
// Ale zbory L i R jako listy a to poglądowo wygląda dobrze
// ale złożoność niepotrzebnie rośnie

//Zadanie 4
//    Zaimplementuj algorytm Dijkstry zgodnie z pseudokodem podanym na wykładzie.
//    Dla grafów z zadania 2 wypisz krok po kroku realizację algorytmu Dijkstry,
//    wybierając jako startowy wierzchołek pierwszy(w przypadku B ten z krawędzią cykliczną).

class Program
{
    static void Dijkstra(int[,] G, int s)
    {
        List<int> L = new List<int>();// to niezbyt dobry pomysł bo złożoność rośnie
        List<int> R = new List<int>();// j.w.

        int[] w = new int[G.GetLength(0)];
        w[s] = 0;
        L.Add(s);
        for (int i = 0; i < w.Length; i++)
        {
            if (i != s)
            {
                R.Add(i);
                if (G[s, i] == 0)
                {
                    w[i] = int.MaxValue / 2;
                }
                else
                {
                    w[i] = G[s, i];
                }
            }
        }

        for (int i = 1; i < w.Length; i++)
        {
            int min = int.MaxValue;
            int minInd = -1;
            for (int k = 0; k < w.Length; k++)
            {
                if (R.Contains(k)) // to niezbyt dobry pomysł bo złożoność rośnie
                {
                    if (w[k] < min)
                    {
                        min = w[k];
                        minInd = k;
                    }
                }
            }
            L.Add(minInd);
            R.Remove(minInd); // to niezbyt dobry pomysł bo złożoność rośnie

            for (int j = 0; j < G.GetLength(0); j++)
            {
                if (G[minInd, j] != 0 && R.Contains(j))
                {
                    if (w[minInd] + G[minInd, j] < w[j])
                    {
                        w[j] = w[minInd] + G[minInd, j];
                    }
                }
            }
        }
        for (int i = 0; i < w.Length; i++)
        {
            Console.WriteLine(w[i]);
        }
    }

    static void Main(string[] args)
    {
        int[,] G = {
        { 1, 0, 0, 3, 0, 0, 7 },
        { 0, 0, 2, 0, 4, 0, 1 },
        { 0, 2, 0, 4, 1, 2, 3 },
        { 3, 0, 4, 0, 5, 3, 3 },
        { 0, 4, 1, 5, 0, 1, 2 },
        { 0, 0, 2, 3, 1, 0, 2 },
        { 7, 1, 3, 3, 2, 2, 0 }
        };


        Dijkstra(G, 0);

        Console.ReadKey();
    }
}

//Przykładowy kolos

using System;
using System.CodeDom;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace AISD_Kolos2_Moodle
{
    class Program
    {
        static void Main(string[] args)
        {
            //Zadanie1(); Chcemy reprezentować wielomiany w postaci listy jednokierunkowej par
            //(współczynnik; wykładnik). Uwaga: przechowujemy tylko współczynniki niezerowe.
            //Napisz zestaw metod do tworzenia takich wielomianów na podstawie tablicy, a także
            //dodawania i odejmowania takich wielomianów oraz różniczkowania

            //Zadanie2();Opracuj strukturę danych Zbiór opartą na liście dowiązaniowej. Napisz metodę Suma
            //(mnogościowa)tworzącą listę z elementów dwóch list Napisz także metodę Iloczyn
            //(mnogościowy) tworzącą listę z elementów wspólnych(o takiej samej wartości
            //klucza) z dwóch list.Dodaj metodę Różnica(mnogościowa).Rozważ dwa przypadki
            //listy nieuporządkowane i uporządkowane. Jaka jest złożoność opracowanych
            //algorytmów(metod) ?

            //Zadanie3();Napisz metodę (iteracyjną), która za pomocą kolejki wypisuje zawartość drzewa
            //kolejnymi poziomami.

            //Zadanie4();Drzewo BST odczytano w porządku pre-order i otrzymano 6, 3, 1, 2, 4, 5, 7. Czy
            //możemy odtworzyć to drzewo? Napisz metodę odtwarzającą drzewo na podstawie
            //odczytu pre-order, jeżeli drzewa nie można odtworzyć(dane są sprzeczne np. 6, 3,
            //1, 2, 4, 7, 5) metoda ma zwracać drzewo puste.

            //Zadanie5();Napisz metodę, która dla spójnego grafu nieskierowanego, dla którego dane są
            //liczbowe wagi krawędzi, znajduje drzewo rozpinające o maksymalnej wartości.

            Console.ReadKey();
        }

        static void Zadanie5()
        {
            int n = 7;
            List<List<int>> graph = new List<List<int>>
            {
                new List<int>(){0, 0, 0, 0, 0, 0, 0},
                new List<int>(){0, 0, 5, 0, 0, 10, 0},
                new List<int>(){0, 5, 0, 7, 0, 4, 0},
                new List<int>(){0, 0, 7, 0, 4, 0, 0},
                new List<int>(){0, 0, 0, 3, 0, 2, 1},
                new List<int>(){0, 10, 4, 0, 2, 0, 0},
                new List<int>(){0, 0, 0, 0, 1, 0, 0}
            };
            bool[] visited = new bool[n];

            var drzewo = Prim(graph, 1, visited);
        }

        static List<List<int>> Prim(List<List<int>> graph, int s, bool[] visited)
        {
            List<List<int>> drzewo = new List<List<int>>();
            int root = s;
            visited[0] = true;
            visited[s] = true;

            List<Tuple<int, int>> l = new List<Tuple<int, int>>();

            bool allVisited = false;

            while (!allVisited)
            {
                allVisited = true;

                for (int i = 0; i < visited.Length; i++)
                {
                    if (visited[i] == false)
                    {
                        allVisited = false;
                        break;
                    }
                }

                if (allVisited)
                    break;

                for (int i = 0; i < graph[root].Count; i++)
                {
                    if (graph[root][i] != 0 && !visited[i])
                        l.Add(new Tuple<int, int>(graph[root][i], i));
                }

                // sort list
                l.Sort();
                if (l.Count != 0)
                {
                    drzewo.Add(new List<int>(){ root, l[0].Item2 });
                    root = l[0].Item2;
                    visited[l[0].Item2] = true;
                    l.Clear();
                }
                else
                {
                    for (int i = drzewo.Count - 1; i >= 0; i--)
                    {
                        if (drzewo[i][1] == root)
                        {
                            root = drzewo[i][0];
                            break;
                        }
                    }
                }
            }

            return drzewo;
        }

        static List<List<int>> Solve(int s, int n, List<List<bool>> graph, bool[] visited)
        {
            List<List<int>> drzewo = new List<List<int>>();

            Queue<int> q = new Queue<int>();
            q.Enqueue(s);
            visited[s] = true;

            while (q.Count != 0)
            {
                int node = q.Dequeue();
                var neighbours = graph[node];
                for (int i = 0; i < neighbours.Count; i++)
                {
                    if (neighbours[i] && !visited[i])
                    {
                        drzewo.Add(new List<int>() { node, i });
                        q.Enqueue(i);
                        visited[i] = true;
                    }
                }
            }

            return drzewo;
        }

        static void Zadanie4()
        {
            int[] t = new int[]{ 6, 3, 1, 2, 4, 7, 5 };
            Tree root = null;

            int i = 0;
            bool badTree = false;

            root = constructTree(t, ref i, Int32.MaxValue);

           // WypiszDrzewo(root);
        }

        static bool IsValid(int[] pre)
        {
            Stack<int> s = new Stack<int>();
            int? lowerBound = null;

            for (int i = 0; i < pre.Length; i++)
            {
                if (lowerBound != null && pre[i] < lowerBound) return false;
                while (s.Count != 0 && s.Peek() < pre[i]) lowerBound = s.Pop();
                s.Push(pre[i]);
            }

            return true;
        }

        static Tree constructTree(int[] pre, ref int i, int high)
        {
            if (!IsValid(pre)) return null;
            else
            {
                if (i >= pre.Length || pre[i] > high) return null;

                Tree root = new Tree(pre[i++]);
                root.left = constructTree(pre, ref i, root.val);
                root.right = constructTree(pre, ref i, high);
                return root;
            }
        }

        static void Zadanie3()
        {
            Tree t = new Tree(5);
            t.left = new Tree(3);
            t.right = new Tree(10);

            t.left.left = new Tree(1);
            t.left.right = new Tree(4);
            t.right.left = new Tree(8);
            t.right.right = new Tree(12);

            WypiszDrzewo(t);

        }

        static void WypiszDrzewo(Tree root)
        {
            if (root == null)
                return;

            Queue<Tree> q = new Queue<Tree>();
            q.Enqueue(root);

            while (true)
            {
                int nodeCount = q.Count;
                if (nodeCount == 0)
                    break;

                while (nodeCount > 0)
                {
                    Tree node = q.Dequeue();
                    Console.Write(node.val + " ");

                    if (node.left != null)
                        q.Enqueue(node.left);
                    if (node.right != null)
                        q.Enqueue(node.right);
                    nodeCount--;
                }
                Console.WriteLine();
            }
        }

        class Tree
        {
            public int val;
            public Tree left;
            public Tree right;

            public Tree(int val)
            {
                this.val = val;
            }
        }


        static void Zadanie2()
        {
            int[] t2 = new int[] { 0 };
            int[] t1 = new int[] { 2, 3 ,5};

            Zbior z1 = new Zbior(t1);
            Zbior z2 = new Zbior(t2);

            Zbior z3 = Zbior.Suma(z1, z2);

            Zbior z4 = Zbior.Iloczyn(z1, z2);

            Debugger.Break();
        }

        class Zbior
        {
            public int val;
            public Zbior next;

            public Zbior(int[] tab)
            {
                Zbior current = this;

                for (int i = 0; i < tab.Length; i++)
                {
                    if (i == 0)
                        val = tab[i];

                    else
                    {
                        current.next = new Zbior(tab[i]);
                        current = current.next;
                    }
                }
            }

            public static Zbior Iloczyn(Zbior z1, Zbior z2)
            {
                Zbior zOut = new Zbior(0);
                Zbior zn = zOut;

                Zbior z2Start = z2;
                bool first = true;

                while (z1 != null && z2 != null)
                {
                    while (z2 != null)
                    {
                        if (z1.val == z2.val)
                        {
                            if (first)
                            {
                                zn.val = z2.val;
                                first = false;
                            }
                            else
                            {
                                zn.next = new Zbior(0);
                                zn = zn.next;
                                zn.val = z2.val;
                            }

                            break;
                        }
                        z2 = z2.next;
                    }
                    z2 = z2Start;

                    z1 = z1.next;
                }

                zn = null;

                return zOut;
            }

            public static Zbior Suma(Zbior z1, Zbior z2)
            {
                Zbior zOut = z1;
                Zbior zn = zOut;

                bool repeated = false;

                while (z2 != null)
                {
                    zn = zOut;
                    repeated = false;

                    while (zn != null)
                    {
                        if (zn.val == z2.val)
                        {
                            repeated = true;
                            break;
                        }
                        zn = zn.next;
                    }

                    zn = zOut;

                    if (!repeated && zn != null)
                    {
                        while (zn.next != null)
                        {
                            zn = zn.next;
                        }

                        zn.next = new Zbior(z2.val);
                    }

                    z2 = z2.next;
                }

                return zOut;
            }

            public Zbior(int val, Zbior next = null)
            {
                this.val = val;
                this.next = next;
            }
        }


        static void Zadanie1()
        {
            int[] t1 = new int[] { 1, 2,3, 4};
            int[] t2 = new int[] { 2, 3};

            Wielomian w1 = new Wielomian(t1);
            Wielomian w2 = new Wielomian(t2);

            Wielomian.Calka(ref w1);
            Debugger.Break();

            Wielomian wOut = w2 - w1;
        }

        class Wielomian
        {
            public int coef;
            public int exp;
            public Wielomian next;

            public bool first = false;
            public bool last = false;
            public int count = -1;

            public static void Calka(ref Wielomian root)
            {
                if (root.next == null)
                {
                    if (root.exp == 0)
                        root.coef = 0;
                    else
                    {
                        root.next = new Wielomian(root.coef * root.exp, root.exp - 1);
                    }
                }
                else
                {
                    Calka(ref root.next);
                    root.next = new Wielomian(root.coef * root.exp, root.exp - 1, root.next.next);
                    root.coef = 0;
                }
            }

            public static Wielomian operator -(Wielomian w1, Wielomian w2)
            {
                Wielomian wOut = w1.exp >= w2.exp ? w1 : w2;
                Wielomian wSmall = w1.exp >= w2.exp ? w2 : w1;
                bool switched = w1.exp < w2.exp;

                Wielomian wReturn = wOut;

                while (wOut != null && wSmall != null)
                {
                    if (wOut.exp == wSmall.exp)
                    {
                        wOut.coef -= wSmall.coef;
                        if (switched)
                            wOut.coef = -wOut.coef;
                        wOut = wOut.next;
                        wSmall = wSmall.next;
                    }
                    else if (wOut.exp > wSmall.exp)
                    {
                        if (switched)
                            wOut.coef = -wOut.coef;
                        wOut = wOut.next;
                    }
                }

                while (wSmall != null)
                {
                    wOut.next = wSmall;
                    wOut = wOut.next;
                    if (switched)
                        wOut.coef = wOut.coef;
                    else
                        wOut.coef = -wOut.coef;
                    wSmall = wSmall.next;
                }

                return wReturn;
            }

            public static Wielomian operator +(Wielomian w1, Wielomian w2)
            {
                Wielomian wOut = w1.exp >= w2.exp ? w1 : w2;
                Wielomian wSmall = w1.exp >= w2.exp ? w2 : w1;

                Wielomian wReturn = wOut;

                while (wOut != null && wSmall != null)
                {
                    if (wOut.exp == wSmall.exp)
                    {
                        wOut.coef += wSmall.coef;
                        wOut = wOut.next;
                        wSmall = wSmall.next;
                    }
                    else if (wOut.exp > wSmall.exp)
                        wOut = wOut.next;
                }

                while (wSmall != null)
                {
                    wOut.next = wSmall;
                    wOut = wOut.next;
                    wSmall = wSmall.next;
                }

                return wReturn;
            }

            public Wielomian(int coef, int exp, Wielomian next = null)
            {
                this.coef = coef;
                this.exp = exp;
                this.next = next;
            }

            public Wielomian(int[] tab)
            {
                Wielomian current = this;
                first = true;
                count = tab.Length;

                for (int i = tab.Length - 1; i >= 0; i--)
                {
                    if (tab[i] != 0)
                    {
                        if (i == tab.Length - 1)
                        {
                            coef = tab[i];
                            exp = i;
                        }
                        else
                        {
                            current.next = new Wielomian(tab[i], i);
                            current = current.next;
                            if (i == 0)
                                current.last = true;
                        }
                    }

                }
            }

        }


        //static void Pociag()
        //{
        //    string pociag = "             .---._\r\n           .--(. '  .).--.      . .-.\r\n        . ( ' _) .)` (   .)-. ( ) '-'\r\n       ( ,  ).        `(' . _)\r\n     (')  _________      '-'\r\n     ____[_________]                                         ________\r\n     \\__/ | _ \\  ||    ,;,;,,                               [________]\r\n     _][__|(\")/__||  ,;;;;;;;;,   __________   __________   _| LILI |_\r\n    /             | |____      | |          | |  ___     | |      ____|\r\n   (| .--.    .--.| |     ___  | |   |  |   | |      ____| |____      |\r\n   /|/ .. \\~~/ .. \\_|_.-.__.-._|_|_.-:__:-._|_|_.-.__.-._|_|_.-.__.-._|\r\n+=/_|\\ '' /~~\\ '' /=+( o )( o )+==( o )( o )=+=( o )( o )+==( o )( o )=+=";
        //    List<char> znaki = new List<char>(pociag.Length);

        //    bool nl = true;
        //    for (int i = 0; i < pociag.Length; i++)
        //    {
        //        if (nl)
        //        {
        //            for (int j = 0; j < 15; j++)
        //            {
        //                znaki.Add('\t');
        //            }

        //            nl = false;
        //        }

        //        if (pociag[i] == '\n')
        //        {
        //            nl = true;
        //        }

        //        znaki.Add(pociag[i]);
        //    }

        //    int tabs = 15;
        //    int index = -15;
        //    nl = true;

        //    while (true)
        //    {
        //        nl = true;
        //        index = -tabs;
        //        StringBuilder s = new StringBuilder();
        //        foreach (var znak in znaki)
        //        {
        //            s.Append(znak);
        //        }

        //        Console.Clear();
        //        Console.Write(s);

        //        if (index >= -1)
        //        {
        //            for (int i = 0; i < znaki.Count; i++)
        //            {
        //                if (nl)
        //                {
        //                    znaki.RemoveRange(i + 1, 4);
        //                    nl = false;
        //                }

        //                if (znaki[i] == '\n')
        //                {
        //                    nl = true;
        //                }
        //            }
        //        }

        //        while (index != -1)
        //        {
        //            index = znaki.IndexOf('\t', index + tabs);
        //            if (index != -1)
        //                znaki.RemoveAt(index);
        //        }

        //        tabs--;

        //        Thread.Sleep(30);
        //    }




        //    //Debugger.Break();
        //}
    }
}


//DRZEWA BST

using System;
//narysuj drzewo bst wstawiające kolejno
class Drzewo
{
    public Węzeł korzeń;
}
class Węzeł
{
    public int wartość; // tutaj klucz
    public Węzeł lewy;
    public Węzeł prawy;
}

class Program
{
    static void Wstaw(Drzewo d, int k)
    {
        Węzeł nowy = new Węzeł();
        nowy.wartość = k;
        if (d.korzeń == null)
        {
            d.korzeń = nowy;
        }
        else
            WstawRekurencyjnie(d.korzeń, nowy);
    }
    static void WstawRekurencyjnie(Węzeł w, Węzeł nowy)
    {
        if (w.wartość > nowy.wartość)
        {
            if (w.lewy == null) w.lewy = nowy;
            else
                WstawRekurencyjnie(w.lewy, nowy);
        }
        else
        {
            if (w.prawy == null) w.prawy = nowy;
            else WstawRekurencyjnie(w.prawy, nowy);
        }
    }
    static void PreOrder(Węzeł w)
    {
        if (w != null)
        {
            Console.Write(w.wartość + " ");
            PreOrder(w.lewy);
            PreOrder(w.prawy);
        }
    }

    static void WyswietlDrzewo(Węzeł w, string wciecie)
    {
        if (w != null)
        {
            if (w.prawy == null && w.lewy != null) Console.WriteLine(wciecie + "   *");
            else WyswietlDrzewo(w.prawy, wciecie + "   ");
            Console.WriteLine(wciecie + w.wartość);
            if (w.lewy == null && w.prawy != null) Console.WriteLine(wciecie + "   *");
            else WyswietlDrzewo(w.lewy, wciecie + "   ");
        }
    }

//    Zadanie 2
//      Mamy zadany zbiór kluczy: {10, 16, 12, 7, 9, 2, 21, 6, 17, 1, 15}.
//      Należy skonstruować drzewo BST biorąc klucze w kolejności:
//      a) podanej
//      b) odwrotnej
//      c) na przemian od początku do końca
//      d) na przemian od końca do początku
    static void Main(string[] args)
    {
        int[] t = { 10, 16, 12, 7, 9, 2, 21, 6, 17, 1, 15 };
        Drzewo d = new Drzewo();
        for (int i = 0; i < t.Length; i++)
        {
            Wstaw(d, t[i]);
        }
        PreOrder(d.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d.korzeń, "");
        Console.WriteLine();
        Drzewo d1 = new Drzewo();
        for (int i = 0; i < t.Length; i++)
        {
            Wstaw(d1, t[t.Length-i-1]);
        }
        PreOrder(d1.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d1.korzeń, "");
        Console.WriteLine();
        Drzewo d2 = new Drzewo();
        for (int i = 0; i < t.Length/2; i++)
        {
            Wstaw(d2, t[i]);
            Wstaw(d2, t[t.Length - 1 - i]);
        }
        if (t.Length % 2 != 0) Wstaw(d2, t.Length / 2);
        PreOrder(d2.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d2.korzeń, "");
        Console.WriteLine();
        Drzewo d3 = new Drzewo();
        for (int i = 0; i < t.Length / 2; i++)
        {
            Wstaw(d3, t[t.Length - 1 - i]);
            Wstaw(d3, t[i]);
        }
        if (t.Length % 2 != 0) Wstaw(d3, t.Length / 2);
        PreOrder(d3.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d3.korzeń, "");
        Console.WriteLine();


        Console.ReadKey();
    }
}

//    Zadanie 3
    //Proszę narysować drzewa BST o wysokości 2, 3, 4, 5 oraz 6 (zygzakiem)
    //zawierające następujący zbiór kluczy: {2, 4, 7, 12, 15, 20, 25}.

    // Następnie proszę przejść te drzewa w porządku in-order wypisując kolejne węzły.
    static void InOrder(Węzeł w)
    {
        if (w != null)
        {
            InOrder(w.lewy);
            Console.Write(w.wartość + " ");
            InOrder(w.prawy);
        }
    }

    static void Main(string[] args)
    {
        int[] t = { 2, 4, 7, 12, 15, 20, 25 };
        Drzewo d = new Drzewo();
        for (int i = 0; i < t.Length; i++)
        {
            Wstaw(d, t[i]);
        }
        PreOrder(d.korzeń);
        Console.WriteLine();
        InOrder(d.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d.korzeń, ""); // wysokosc 6
        Console.WriteLine("------------------------------------------------");

        int[] t1 = { 12, 4, 2, 7, 20, 15, 25 };
        Drzewo d1 = new Drzewo();
        for (int i = 0; i < t1.Length; i++)
        {
            Wstaw(d1, t1[i]);
        }
        PreOrder(d1.korzeń);
        Console.WriteLine();
        InOrder(d1.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d1.korzeń, ""); // wysokosc 2
        Console.WriteLine("------------------------------------------------");

        int[] t2 = { 12, 2, 4, 7, 20, 15, 25 };
        Drzewo d2 = new Drzewo();
        for (int i = 0; i < t2.Length; i++)
        {
            Wstaw(d2, t2[i]);
        }
        PreOrder(d2.korzeń);
        Console.WriteLine();
        InOrder(d2.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d2.korzeń, ""); // wysokosc 3
        Console.WriteLine("------------------------------------------------");

        int[] t3 = { 15, 12, 2, 4, 7, 20, 25 };
        Drzewo d3 = new Drzewo();
        for (int i = 0; i < t3.Length; i++)
        {
            Wstaw(d3, t3[i]);
        }
        PreOrder(d3.korzeń);
        Console.WriteLine();
        InOrder(d3.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d3.korzeń, ""); // wysokosc 4
        Console.WriteLine("------------------------------------------------");

        int[] t4 = { 2, 25, 4, 20, 7, 15, 12 };
        Drzewo d4 = new Drzewo();
        for (int i = 0; i < t4.Length; i++)
        {
            Wstaw(d4, t4[i]);
        }
        PreOrder(d4.korzeń);
        Console.WriteLine();
        InOrder(d4.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d4.korzeń, ""); // wysokosc 6 zygzak

        Console.ReadKey();
    }

// Zadanie 5
    // Napisz w C# metody znajdujące w drzewie BST węzeł z maksymalnym kluczem,
    // oraz węzeł z minimalnym kluczem.


    // iteracja, można rekurencyjnie jak dla Min
    static Węzeł Max(Węzeł w)
    {
        Węzeł temp = w;
        while (temp.prawy != null)
        {
            temp = temp.prawy;
        }
        return temp;
    }
    // rekurencja, można iteracyjnie jak dla Min
    static Węzeł Min(Węzeł w)
    {
        if (w.lewy == null)
        {
            return w;
        }
        else
            return Min(w.lewy);
    }

    //  Napisz w C# metodę iteracyjną wyszukującą węzeł o podanej wartości klucza.
    // iteracja
    static Węzeł ZnajdzPoKluczu(Węzeł w,int k)
    {
        Węzeł temp = w;
        while (temp != null)
        {
            if (temp.wartość == k) return temp;
            if(temp.wartość<k)
                    temp = temp.prawy;
            else
                temp = temp.lewy;
        }
        return temp;
    }



    static void Main(string[] args)
    {
        int[] t = { 10, 16, 12, 7, 9, 2, 21, 6, 17, 1, 15 };
        Drzewo d = new Drzewo();
        for (int i = 0; i < t.Length; i++)
        {
            Wstaw(d, t[i]);
        }
        PreOrder(d.korzeń);
        Console.WriteLine();
        Console.WriteLine();
        WyswietlDrzewo(d.korzeń, "");
        Console.WriteLine();

        Węzeł W = Max(d.korzeń);
        Console.WriteLine(W.wartość);
        W = Min(d.korzeń);
        Console.WriteLine(W.wartość);

        W = ZnajdzPoKluczu(d.korzeń, 17);
        if (W != null)
            Console.WriteLine("znaleziono "+W.wartość);
        else Console.WriteLine("nie znaleziono");
        W = ZnajdzPoKluczu(d.korzeń, 77);
        if (W != null)
            Console.WriteLine("znaleziono " + W.wartość);
        else Console.WriteLine("nie znaleziono");

        Console.ReadKey();
    }
}