1. Liniowym opisem drzewa binarnego nazwiemy ciąg etykiet tego drzewa odczytanych w porządku preorder i uzupełniony symbolem *, wszędzie tam, gdzie brakuje lewego lub prawego syna. Na przykład a*bc*** jest  opisem drzewa o trzech wierzchołkach, którego korzeniem jest a, prawym i jedynym synem korzenia jest b, a lewym synem b jest c. Zaproponuj algorytm, który na podstawie liniowego opisu drzewa, konstruuje to drzewo.
    

2. Zaproponuj rekurencyjny algorytm wyliczania liczby liści w drzewie binarnym. Uzasadnij poprawność tego algorytmu. Oszacuj koszt.
    

3. Dany jest diagram Hassego pewnego zbioru częściowo uporządkowanego X. Każdy węzeł tego grafu ma atrybut et, będący elementem zbioru X, oraz tablicę następników next. Zaproponuj strukturę danych do zapamiętania diagramu Hassego i napisz algorytm, który wyszukuje w tym grafie elementy maksymalne.
    

4. Powiemy, że dwa drzewa D1 i D2 są izomorficzne wttw (1) każde z nich składa się z jednego wierzchołka lub (2) (a) Korzenie obu drzew mają tę samą liczbę synów oraz (b) dla dowolnego i, poddrzewo, którego korzeniem jest i-ty syn korzenia drzewa D1 jest izomorficzny z poddrzewem, którego korzeniem jest i-ty syn drzewa D2.
   Zaproponuj rekurencyjny, a następnie  iteracyjny, algorytm badania, czy dwa dane drzewa są izomorficzne.
    

5. Definicja. Bezpośrednim następnikiem wierzchołka v w drzewie binarnych poszukiwań D nazywamy taki wierzchołek w, którego etykieta ma najmniejszą wartość w zbiorze wszystkich  etykiet tego drzewa, większych od etykiety wierzchołka v.
   Napisz algorytm, który dla danego wierzchołka drzewa BST wyznacza jego bezpośredni następnik, o ile taki istnieje. Oszacuj koszt zaproponowanego algorytmu.
    

6. Definicja. Bezpośrednim poprzednikiem wierzchołka v w drzewie binarnych poszukiwań D nazywamy taki wierzchołek w, którego etykieta ma największą wartość w zbiorze wszystkich  etykiet tego drzewa, mniejszych od etykiety wierzchołka v.
   Napisz algorytm, który dla danego wierzchołka drzewa BST wyznacza jego bezpośredni poprzednik, o ile taki istnieje. Oszacuj koszt zaproponowanego algorytmu.
    

7. Niech f będzie funkcją  zdefiniowaną dla drzew binarnych za pomocą algorytmu:

   int  f( drzewo d){
   int x,y;
       if (d=null) then return 0 else { x:= f(d.left); y := f(d.right);  return(x+y+1);}
   }

   Zakładamy, że  każdy wierzchołek drzewa ma dwa atrybuty left i right wskazujące odpowiednio lewego i prawego syna tego wierzchołka. Jaki jest wynik wykonania  funkcji f(d), jeśli d jest korzeniem pewnego drzewa binarnego. Oszacuj złożoność tego algorytmu.

    

    

   
   
    

    

    

    

 

« poprzedni punkt

następny punkt »