Klasa III - Badanie drzew binarnych

Dla danego drzewa binarnego określić:

Długość najdłuższej ścieżki od korzenia do liścia (czyli wysokość drzewa).
Długość najkrótszej ścieżki od korzenia do liścia.
Liczbę węzłów na każdym poziomie.
Liczbę liści.
Liczbę węzłów zawierających tylko jednego syna
Sumę danych zawartych w węzłach.

Na pierwszy rzut oka zadanie wydaje się być skomplikowane. Jednakże rozwiążemy je za pomocą opisanego na poprzedniej lekcji przejścia DFS:preorder. Algorytm DFS gwarantuje nam odwiedzenie każdego węzła drzewa, jeśli węzłem startowym będzie jego korzeń. Do wykonania naszego zadania w strukturze węzła będziemy potrzebowali dodatkowe pole level, w którym zostanie umieszczony numer poziomu zawierającego dany węzeł.

struct BTNode
{
  BTNode * left;
  BTNode * right;
  int level;
  typ_danych data;
};

Kolejnym problemem jest sposób wprowadzania drzewa. Można go rozwiązać na kilka sposobów. Tutaj postąpimy w sposób następujący:

Pierwsza liczba n będzie określała ilość wszystkich węzłów w drzewie. Umówmy się, że węzły ponumerujemy kolejnymi liczbami od 0 do n-1 idąc od strony lewej do prawej na kolejnych poziomach.

Kolejne dane występują jako n trójek liczb. Każdy węzeł jest opisany jedną trójką liczb. Pierwsza trójka odnosi się do węzła nr 0, druga do węzła nr 1, itd.

Trójka liczb dla danego węzła określa kolejno: daną dla węzła, numer węzła będącego lewym synem, numer węzła będącego prawym synem. Jeśli węzeł nie posiada syna, to jego numer wynosi 0 (nie spowoduje to dwuznaczności, ponieważ numer 0 jest zarezerwowany dla korzenia, a korzeń nie jest synem żadnego węzła).

Przykład:

Na rysunku poniżej przedstawione jest drzewo binarne. Wewnątrz węzłów znajdują się przechowywane w tych węzłach liczby. Numery węzłów są podane w kolorze czerwonym pod każdym węzłem. Na przykład węzeł nr 3 przechowuje liczbę 32 i posiada dwóch synów: lewego – węzeł 7 i prawego – węzeł 8.

12
5 1 2
11 3 4
7 5 6
32 7 8
-16 0 9
21 10 11
-2 0 0
3 0 0
17 0 0
-5 0 0
4 0 0
1 0 0

Liczba węzłów
węzeł   0: synowie 1 i 2
węzeł   1: synowie 3 i 4
węzeł   2: synowie 5 i 6
węzeł   3: synowie 7 i 8
węzeł   4: prawy syn 9
węzeł   5: synowie 10 i 11
węzeł   6: brak synów
węzeł   7: brak synów
węzeł   8: brak synów
węzeł   9: brak synów
węzeł 10: brak synów
węzeł 11: brak synów

Zasada odczytu danych będzie następująca:

Odczytujemy n.
Tworzymy dynamicznie tablicę n wskaźników do węzłów drzewa.
Dynamicznie tworzymy n węzłów i ich adresy zapamiętujemy we wskaźnikach.
Odczytujemy n trójek liczb. Numer trójki określa numer węzła. Pierwszą liczbę wstawiamy w pole data, następne dwie liczby, jeśli są różne od zera, darzą numery wskaźników w tablicy, które należy przepisać odpowiednio w pole left i right węzła.
Po odczycie danych zapamiętujemy w osobnej zmiennej wskazanie korzenia, czyli pierwszy wskaźnik w tablicy wskaźników.
Tablicę dynamiczną wskaźników usuwamy z pamięci.

Długość najdłuższej ścieżki

Tworząc węzły, zerujemy w nich pola level. Przed rozpoczęciem przeglądania drzewa tworzymy zmienną maxpath, w której umieszczamy wartość 0. W trakcie przechodzenia drzewa przetwarzamy węzeł:

Jeśli posiada syna, to w polu level syna umieszczamy zawartość pola level węzła powiększoną o 1. W ten sposób dzieci będą miały zawsze numer poziomu o 1 większy od swoich rodziców.
Porównujemy pole level przetwarzanego węzła ze zmienną maxpath. Jeśli level ma wartość większą, to zapisujemy ją w maxpath. Po przejściu całego drzewa maxlevel będzie zawierał największą wartość poziomu, czyli wysokość drzewa.

Długość najkrótszej ścieżki do liścia

Przed rozpoczęciem przeglądania drzewa tworzymy zmienną minpath, w której umieszczamy największą wartość całkowitą (dla liczb 32 bitowych jest to 2147483647). W trakcie przechodzenia drzewa sprawdzamy, czy węzeł jest liściem (tak będzie, jeśli pola left i right zawierają wskazanie puste). Jeśli tak, to porównujemy wartość pola level ze zmienną minpath. Jeśli jest mniejsze, zapamiętujemy je w minpath. Po przejściu całego drzewa minpath będzie zawierało długość najkrótszej ścieżki.

Liczba węzłów na każdym poziomie

Przed rozpoczęciem przeglądania drzewa tworzymy dynamicznie tablicę levelcount liczników i zerujemy je. Kolejne liczniki będą zliczały węzły na kolejnych poziomach. Tworząc tablicę musimy określić liczbę poziomów. W najbardziej niekorzystnym przypadku będzie ich n (drzewo binarne posiadające wszystkie węzły oprócz ostatniego z jednym synem). Dlatego tworzymy tablicę n elementową. Faktyczną wysokość drzewa poznamy dopiero po wykonaniu przejścia DFS.

W trakcie wykonywania DFS zwiększamy o 1 licznik o indeksie równym zawartości pola level – zliczymy węzeł na danym poziomie. Po przejściu drzewa wyświetlamy zawartości liczników od 0 do maxpath.

Liczba liści

Przed rozpoczęciem przeglądania drzewa tworzymy zmienną leafcount i nadajemy jej wartość 0. W trakcie przeglądania drzewa sprawdzamy, czy bieżący węzeł jest liściem (pola left i right zawierają wskazanie puste) i jeśli tak, to zwiększamy o 1 zmienną leafcount. Po przejściu drzewa zmienna zawiera liczbę liści.

Liczba węzłów z jednym synem

Przed rozpoczęciem przeglądania drzewa tworzymy zmienną onechildcount i nadajemy jej wartość 0. W trakcie przeglądania drzewa sprawdzamy, czy bieżący węzeł posiada tylko jednego syna (tylko jedno z pól left i right zawiera wskazanie puste) i jeśli tak, to zwiększamy o 1 zmienną onechildcount. Po przejściu drzewa zmienna zawiera liczbę węzłów z jednym synem.

Suma zawartości węzłów

Przed rozpoczęciem przeglądania drzewa tworzymy zmienną nodesum i nadajemy jej wartość 0. W trakcie przeglądania do zmiennej nodesum dodajemy zawartość pola data bieżącego węzła. Po przejściu drzewa w nodesum będzie suma zawartości wszystkich węzłów drzewa.

Przykładowe dane wejściowe (jest to drzewo z przykładu podanego powyżej):

Wynik