Metody programowania / Ćwiczenia 3: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Pch (dyskusja | edycje)
411 edycji
Daria (dyskusja | edycje)
154 edycje
Linia 154: Linia 154:
  '''begin'''
  '''begin'''
   '''if''' d <> nil '''then'''
   '''if''' d <> nil '''then'''
     '''if''' (d^.lsyn <> nil) '''or''' (d^.psyn = nil) '''then''' '''begin'''  //jeśli d to lisć
     '''if''' l = nil '''then''' '''begin'''     
      '''if''' l = nil '''then''' '''begin'''     
      new(l);
        new(l);
      l^.w:=0;
        l^.w:=0;
      l^.nast:=nil;
        l^.nast:=nil;
      '''end''';
      l^.w:=l^.w+1;                                    //zwiększamy licznik liści na tym poziomie
    '''end'''
    '''else'''  '''begin'''                                        //jesli d nie jest liściem
      Obejdź(d^.lsyn, l^.nast);                        //obchodzimy lewe i prawe poddrzewa
      Obejdź(d^.psyn, l^.nast);
     '''end''';
     '''end''';
    l^.w:=l^.w+1;                                    //zwiększamy licznik liści na tym poziomie
    Obejdź(d^.lsyn, l^.nast);                        //obchodzimy lewe i prawe poddrzewa
    Obejdź(d^.psyn, l^.nast);
  '''end''';
  '''end''';
  '''begin''' //Szerokość
  '''begin''' //Szerokość

Wersja z 13:40, 1 wrz 2009

To są zadania na drzewa.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Przyjmujemy następujące definicje: 

type el_drzewa = record
                   w: integer;
                   lsyn, psyn: ^el_drzewa;
                 end;
        drzewo = ^el_drzewa;


Zadanie 1 (Liczba liści w drzewie)

Napisz funkcję która oblicza liczbę liści w drzewie.

Rozwiązanie 1

{{{3}}}

Zadanie 2 (Odbicie lustrzane)

Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.

Rozwiązanie 1

{{{3}}}

Zadanie 3 (Izomorfizm drzew)

Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).

Rozwiązanie 1

{{{3}}}

Zadanie 4 (Lista liści)

Napisz funkcję wiążącą liście drzewa w listę (od lewej do prawej). Wynikiem funkcji ma być wskaźnik do utworzonej listy. Zakładamy, że każdy węzeł ma dodatkowe pole będące wskaźnikiem do węzła, czyli używamy typów 

type węzeł = record
               w: integer;
               lsyn, psyn, nast: ^węzeł;
             end;
   drzewoL = ^węzeł;

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 5 (Szerokość drzewa)

Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 6 (Średnica drzewa)

Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 7 (Sprawdzanie czy drzewo jest BST)

Napisz funkcję sprawdzającą czy drzewo jest drzewem BST.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}


Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Metody_programowania_/_Ćwiczenia_3&oldid=75864”