Badanie drzewa binarnego


Tematy pokrewne
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew
Podstawowe operacje na tablicach
Zliczanie wg kryterium
Wyszukiwanie max lub min

Problem

Dla danego drzewa binarnego określić:

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



Na pierwszy rzut oka zadanie wydaje się być skomplikowane. Jednakże rozwiążemy je za pomocą opisanego wcześniej 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ł.

 

Lazarus Code::Blocks Free Basic
type
  PBTNode = ^BTNode;
  BTNode  = record
    left  : PBTNode;
    right : PBTNode;
    level : Integer;
    data  : typ_danych;
  end;
struct BTNode
{
  BTNode * left;
  BTNode * right;
  int level;
  typ_danych data;
};
Type BTNode
  left As BTNode Ptr
  right As BTNode Ptr
  level As Integer
  data As typ_danych
End Type

 

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:

  1. Odczytujemy n.
  2. Tworzymy dynamicznie tablicę n wskaźników do węzłów drzewa.
  3. Dynamicznie tworzymy n węzłów i ich adresy zapamiętujemy we wskaźnikach.
  4. 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.
  5. Po odczycie danych zapamiętujemy w osobnej zmiennej wskazanie korzenia, czyli pierwszy wskaźnik w tablicy wskaźników.
  6. 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ł:
  1. 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.
  2. 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.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje ze standardowego wejścia definicję drzewa, tworzy drzewo binarne, przechodzi je algorytmem rekurencyjnym DFS:preorder, przetwarza węzły i wypisuje wyniki.

Przykładowe dane wejściowe:

 

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

 

Lazarus
// Badanie drzewa binarnego
// Data: 24.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program explore_BT;

// Typ węzłów drzewa

type
  PBTNode = ^BTNode;   // wskazanie węzła

  BTNode  = record        // rekord węzła
    left  : PBTNode;      // lewy syn
    right : PBTNode;      // prawy syn
    level : integer;         // numer poziomu
    data  : integer;         // dane węzła
  end;

// Zmienne globalne

var
  maxpath       : integer;    // długość najdłuższej ścieżki / wysokość drzewa
  minpath       : integer;    // długość najkrótszej ścieżki
  levelcount    : array of Integer; // tablica liczników
  leafcount     : integer;    // liczba liści
  onechildcount : integer;    // liczba węzłów z jedynakiem
  nodesum       : integer;    // suma danych węzłów

  n             : integer;    // liczba węzłów
  root          : PBTNode; // wskazanie korzenia drzewa

// Procedura inicjuje dane, odczytuje definicję drzewa
// ze standardowego wejścia i tworzy jego strukturę w
// pamięci. Na wyjściu w zmiennej root zostaje umieszczony
// adres korzenia drzewa
//--------------------------------------------------------
procedure readBT;
var
  vp : array of PBTNode;  // tablica wskaźników
  i,d,l,r : integer;
begin
  read(n);             // odczytujemy liczbę węzłów drzewa binarnego

  SetLength(vp,n);     // tworzymy tablicę dynamiczną wskaźników

  for i := 0 to n - 1 do
    new(vp[i]);        // tworzymy dynamicznie węzeł

  for i := 0 to n - 1 do
  begin
    read(d,l,r);       // odczytujemy trójkę liczb

    vp[i]^.level := 0; // zerujemy poziom węzła

    vp[i]^.data  := d; // wprowadzamy do węzła dane

    if l > 0 then vp[i]^.left  := vp[l]  // ustawiamy lewego syna
    else          vp[i]^.left  := nil;   // jeśli istnieje

    if r > 0 then vp[i]^.right := vp[r]  // ustawiamy prawego syna
    else          vp[i]^.right := nil;   // jeśli istnieje
  end;

  root := vp[0];       // zapamiętujemy korzeń drzewa

  SetLength(vp,0);     // usuwamy tablicę wskaźników

  maxpath := 0;        // ustawiamy zmienne globalne
  minpath := MAXINT;
  SetLength(levelcount,n);
  for i := 0 to n - 1 do levelcount[i] := 0;
  leafcount := 0;
  onechildcount := 0;
  nodesum := 0;
end;

// Procedura przechodzi drzewo algorytmem DFS:preorder
// i odpowiednio przetwarza węzły zapisując wyniki
// w zmiennych globalnych
//----------------------------------------------------
procedure DFS(v : PBTNode);
var
  children : integer;
begin
  if v <> nil then
  begin

    // przetwarzamy bieżący węzeł

    children := 0; // liczba dzieci, 0, 1 lub 2

    if v^.left <> nil then
    begin
      inc(children);
      v^.left^.level := v^.level + 1;
    end;

    if v^.right <> nil then
    begin
      inc(children);
      v^.right^.level := v^.level + 1;
    end;

    // test na najdłuższą ścieżkę

    if v^.level > maxpath then maxpath := v^.level;

    // test na najkrótszą ścieżkę do liścia i zliczanie liści

    if children = 0 then
    begin
      if v^.level < minpath then minpath := v^.level;
      inc(leafcount);
    end;

    // zliczanie węzłów na bieżącym poziomie poziomie

    inc(levelcount[v^.level]);

    // zliczanie węzłów z jednym synem

    if children = 1 then inc(onechildcount);

    // sumowanie zawartości węzłów

    inc(nodesum,v^.data);

    DFS(v^.left);  // przechodzimy lewe poddrzewo
    DFS(v^.right); // przechodzimy prawe poddrzewo
  end;
end;

// Procedura wyświetla wyniki końcowe
//-----------------------------------
procedure writeBT;
var
  i : integer;
begin
  writeln;
  writeln('maxpath       = ',maxpath);
  writeln('minpath       = ',minpath);
  writeln;
  for i := 0 to maxpath do
    writeln('level ',i,' : number of nodes = ',levelcount[i]);
  writeln;
  writeln('leafcount     = ',leafcount);
  writeln('onechildcount = ',onechildcount);
  writeln('nodesum       = ',nodesum);
  writeln;
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease(v : PBTNode);
begin
  if v <> nil then
  begin
    DFSRelease(v^.left);   // usuwamy lewe poddrzewo
    DFSRelease(v^.right);  // usuwamy prawe poddrzewo
    dispose(v);            // usuwamy sam węzeł
  end;
end;

// Procedura sprząta pamięć
//-------------------------
procedure deleteBT;
begin
  SetLength(levelcount,0);
  DFSRelease(root);   // wykorzystujemy DFS:postorder do usunięcia drzewa
end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

begin
  readBT;      // odczytaj i utwórz drzewo
  DFS(root);   // przetwórz drzewo
  writeBT;     // wypisz wyniki
  deleteBT;    // posprzątaj pamięć
end.
Code::Blocks
// Badanie drzewa binarnego
// Data: 24.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Typ węzłów drzewa

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

// Zmienne globalne

int maxpath = 0;              // długość najdłuższej ścieżki / wysokość drzewa
int minpath = 2147483647;     // długość najkrótszej ścieżki
int * levelcount;             // tablica liczników
int leafcount = 0;            // liczba liści
int onechildcount = 0;        // liczba węzłów z jedynakiem
int nodesum = 0;              // suma danych węzłów

int n;                        // liczba węzłów
BTNode * root;             // wskazanie korzenia drzewa

// Procedura inicjuje dane, odczytuje definicję drzewa
// ze standardowego wejścia i tworzy jego strukturę w
// pamięci. Na wyjściu w zmiennej root zostaje umieszczony
// adres korzenia drzewa
//--------------------------------------------------------
void readBT()
{
  BTNode ** vp;     // tablica wskaźników
  int i,d,l,r;

  cin >> n;            // odczytujemy liczbę węzłów drzewa binarnego

  vp = new BTNode * [n]; // tworzymy tablicę dynamiczną wskaźników

  for(i = 0; i < n; i++)
    vp[i] = new BTNode; // tworzymy dynamicznie węzeł

  for(i = 0; i < n; i++)
  {
    cin >> d >> l >> r;    // odczytujemy trójkę liczb

    vp[i]->level = 0;      // zerujemy poziom węzła

    vp[i]->data = d;       // wprowadzamy do węzła dane

    vp[i]->left  = l ? vp[l]: NULL;  // ustawiamy lewego syna, jeśli istnieje

    vp[i]->right = r ? vp[r]: NULL;  // ustawiamy prawego syna, jeśli istnieje
  }

  root = vp[0];           // zapamiętujemy korzeń drzewa

  delete [] vp;           // usuwamy tablicę wskaźników

  // tworzymy tablicę liczników elementów na poziomach

  levelcount = new int[n];
  for(i = 0; i < n; i++) levelcount[i] = 0;
}

// Procedura przechodzi drzewo algorytmem DFS:preorder
// i odpowiednio przetwarza węzły zapisując wyniki
// w zmiennych globalnych
//----------------------------------------------------
void DFS(BTNode * v)
{
  if(v)
  {
     // przetwarzamy bieżący węzeł

    int children = 0; // liczba dzieci, 0, 1 lub 2

    if(v->left)
    {
      children++;
      v->left->level = v->level + 1;
    }

    if(v->right)
    {
      children++;
      v->right->level = v->level + 1;
    }

    // test na najdłuższą ścieżkę

    if(v->level > maxpath) maxpath = v->level;

    // test na najkrótszą ścieżkę do liścia i zliczanie liści

    if(!children)
    {
      if(v->level < minpath) minpath = v->level;
      leafcount++;
    }

    // zliczanie węzłów na bieżącym poziomie poziomie

    levelcount[v->level]++;

    // zliczanie węzłów z jednym synem

    if(children == 1) onechildcount++;

    // sumowanie zawartości węzłów

    nodesum += v->data;

    DFS(v->left);  // przechodzimy lewe poddrzewo
    DFS(v->right); // przechodzimy prawe poddrzewo
  }
}

// Procedura wyświetla wyniki końcowe
//-----------------------------------
void writeBT()
{
  cout << endl
       << "maxpath       = " << maxpath << endl
       << "minpath       = " << minpath << endl
       << endl;
  for(int i = 0; i <= maxpath; i++)
    cout << "level " << i << " : number of nodes = " << levelcount[i] << endl;
  cout << endl
       << "leafcount     = " << leafcount << endl
       << "onechildcount = " << onechildcount << endl
       << "nodesum       = " << nodesum << endl
       << endl;
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease(BTNode * v)
{
  if(v)
  {
    DFSRelease(v->left);   // usuwamy lewe poddrzewo
    DFSRelease(v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam węzeł
  }
}

// Procedura sprząta pamięć
//-------------------------
void deleteBT()
{
  delete [] levelcount;
  DFSRelease(root);   // wykorzystujemy DFS:postorder do usunięcia drzewa
}

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

int main()
{
  readBT();    // odczytaj i utwórz drzewo
  DFS(root);   // przetwórz drzewo
  writeBT();   // wypisz wyniki
  deleteBT();  // posprzątaj pamięć

  return 0;
}
Free Basic
' Badanie drzewa binarnego
' Data: 24.01.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Typ węzłów drzewa

Type BTNode
  left As BTNode Ptr
  right As BTNode Ptr
  level As Integer
  data As Integer
End Type

' Zmienne globalne

Dim Shared As Integer maxpath = 0          ' długość najdłuższej ścieżki / wysokość drzewa
Dim Shared As Integer minpath = 2147483647 ' długość najkrótszej ścieżki
Dim Shared As Integer Ptr levelcount       ' tablica liczników
Dim Shared As Integer leafcount = 0        ' liczba liści
Dim Shared As Integer onechildcount = 0    ' liczba węzłów z jedynakiem
Dim Shared As Integer nodesum = 0          ' suma danych węzłów

Dim Shared As Integer n                    ' liczba węzłów
Dim Shared As BTNode Ptr root           ' wskazanie korzenia drzewa

' Procedura inicjuje dane, odczytuje definicję drzewa
' ze standardowego wejścia i tworzy jego strukturę w
' pamięci. Na wyjściu w zmiennej root zostaje umieszczony
' adres korzenia drzewa
'--------------------------------------------------------
Sub readBT()
  Dim As BTNode Ptr Ptr vp     ' tablica wskaźników
  Dim As Integer i,d,l,r

  Open Cons For Input As #1
  
  Input #1,n                 ' odczytujemy liczbę węzłów drzewa binarnego

  vp = new BTNode Ptr [n] ' tworzymy tablicę dynamiczną wskaźników

  For i = 0 To n-1
    vp[i] = new BTNode    ' tworzymy dynamicznie węzeł
  Next

  For i = 0 To n-1
    Input #1,d,l,r           ' odczytujemy trójkę liczb

    vp[i]->level = 0         ' zerujemy poziom węzła

    vp[i]->data = d          ' wprowadzamy do węzła dane

    ' ustawiamy lewego syna, jeśli istnieje
    
    If l > 0 Then
    	vp[i]->left = vp[l]
    Else
    	vp[i]->Left = 0
    End If

    ' ustawiamy prawego syna, jeśli istnieje
    
    If r > 0 Then
    	vp[i]->right = vp[r]
    Else
    	vp[i]->Right = 0
    End If
  Next
  
  Close #1

  root = vp[0]           ' zapamiętujemy korzeń drzewa

  delete [] vp           ' usuwamy tablicę wskaźników

  ' tworzymy tablicę liczników elementów na poziomach

  levelcount = new Integer [n]
  For i = 0 To n-1
  	levelcount[i] = 0
  Next
End Sub

' Procedura przechodzi drzewo algorytmem DFS:preorder
' i odpowiednio przetwarza węzły zapisując wyniki
' w zmiennych globalnych
'----------------------------------------------------
Sub DFS(v As BTNode Ptr)

  Dim As Integer children = 0
   
  If v Then
    ' przetwarzamy bieżący węzeł

    If v->Left Then
      children += 1
      v->left->level = v->level + 1
    End If

    If v->Right Then
      children += 1
      v->right->level = v->level + 1
    End If

    ' test na najdłuższą ścieżkę

    If v->level > maxpath Then maxpath = v->level

    ' test na najkrótszą ścieżkę do liścia i zliczanie liści

    If children = 0 Then
      If v->level < minpath Then minpath = v->level
      leafcount += 1
    End If

    ' zliczanie węzłów na bieżącym poziomie poziomie

    levelcount[v->level] += 1

    ' zliczanie węzłów z jednym synem

    If children = 1 then onechildcount += 1

    ' sumowanie zawartości węzłów

    nodesum += v->Data

    DFS(v->left)  ' przechodzimy lewe poddrzewo
    DFS(v->right) ' przechodzimy prawe poddrzewo
  End If
End Sub

' Procedura wyświetla wyniki końcowe
'-----------------------------------
Sub writeBT()
  Dim As Integer i
  Print
  Print "maxpath       = ";maxpath
  Print "minpath       = ";minpath
  Print
  For i = 0 To maxpath
    Print "level ";i;" : number of nodes = ";levelcount[i]
  Next
  Print
  Print "leafcount     = ";leafcount
  Print "onechildcount = ";onechildcount
  Print "nodesum       = ";nodesum
  Print
End Sub

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
sub DFSRelease(v As BTNode Ptr)
  If v Then
    DFSRelease(v->left)   ' usuwamy lewe poddrzewo
    DFSRelease(v->right)  ' usuwamy prawe poddrzewo
    delete v              ' usuwamy sam węzeł
  End If
End Sub

' Procedura sprząta pamięć
'-------------------------
Sub deleteBT()
  delete [] levelcount
  DFSRelease(root)        ' wykorzystujemy DFS:postorder do usunięcia drzewa
End Sub

'**********************
'*** PROGRAM GŁÓWNY ***
'**********************

readBT()    ' odczytaj i utwórz drzewo
DFS(root)   ' przetwórz drzewo
writeBT()   ' wypisz wyniki
deleteBT()  ' posprzątaj pamięć

End
Wynik
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

maxpath       = 3
minpath       = 2

level 0 : number of nodes = 1
level 1 : number of nodes = 2
level 2 : number of nodes = 4
level 3 : number of nodes = 5

leafcount     = 6
onechildcount = 1
nodesum       = 78

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe