Drzewo

obrazek

Drzewo (ang. tree) jest strukturą dynamiczną zbudowaną z elementów zwanych węzłami (ang. node), z których każdy może posiadać jednego rodzica (ang. parent node) oraz kilku potomków (ang. child node). Węzeł nie posiadający rodzica nazywamy korzeniem drzewa lub węzłem głównym (ang. root node). Węzeł nie posiadający potomków nazywamy liściem lub węzłem terminalnym (ang. leaf). Drzewo może posiadać wiele liści lecz tylko jeden korzeń.

obrazek

Drzewo binarne (ang. binary tree) posiada tą własność, iż każdy węzeł może posiadać co najwyżej dwóch potomków. Dzięki temu, iż liczba możliwych węzłów potomnych jest ograniczona, węzeł drzewa binarnego jest łatwo realizowalny za pomocą poniższej struktury języka C++:

deklaracja typu węzła
drzewa binarnego		 
struct TBTNode
{
  TBTNode * top, * left, * right; 
  int key;
  char ch;
  ...
};

Pola struktury TBTNode posiadają następujące znaczenia:

top - wskaźnik do węzła nadrzędnego. Jeśli zawiera adres NULL, to dany węzeł jest korzeniem drzewa.
left - wskaźnik lewego (umownie) potomka danego węzła
right - wskaźnik prawego potomka danego węzła. Jeśli oba pola left i right zawierają adres pusty NULL, to węzeł jest liściem
key - pole klucza - wykorzystywane w algorytmie Huffmana
ch - pole znaku - wykorzystywane w algorytmie Huffmana

Drzewo zbudowane z takich węzłów można łatwo przebywać w obu kierunkach - z góry w dół (od korzenia do liścia) i z dołu do góry (od liścia do korzenia).

Podamy teraz kilka algorytmów związanych z drzewami binarnymi, z których korzysta algorytm Huffmana.

Tworzenie drzewa binarnego z dwóch węzłów

Dane wejściowe

n1,n2  - dwa wskaźniki węzłów drzewa binarnego typu TBTNode

Dane wyjściowe

n  - wskaźnik węzła typu TBTNode będący korzeniem drzewa zbudowanego z węzłów n1 i n2.

Lista kroków

K01: Utwórz nowy węzeł i wpisz jego adres do n Przydzielamy pamięć dla nowego węzła
K02: n1→parent ← n;  n2→parent ← n Węzeł n ustawiamy jako rodzica dla n1 i n2
K03: n→left ← n1;  n→right ← n2 Jako potomki węzła n ustawiamy n1 i n2
K04: n→parent ← NULL Węzeł n nie posiada rodzica, ponieważ jest korzeniem nowego drzewa
K05: Zakończ  

Zwróć uwagę, iż powyższy algorytm może również bez dodatkowych założeń łączyć dwa drzewa binarne w jedno drzewo, jeśli jeden z węzłów n1 lub n2 (a nawet oba) jest korzeniem drzewa binarnego.

Przechodzenie przez drzewo binarne

Poniższy algorytm rekurencyjny przechodzi przez wszystkie ścieżki prowadzące od korzenia do poszczególnych liści. W trakcie przechodzenia drzewa zapamiętywana jest trasa w pewien szczególny sposób. Mianowicie przejście przez gałąź lewą powoduje zapamiętanie zera, a przejście przez gałąź prawą zapamiętuje 1. Po dotarciu do liścia algorytm wyświetla znak ch zawarty w danych węzła oraz odpowiadającą mu ścieżkę zbudowaną z zer i jedynek. Poniższy rysunek wyjaśnia ideę algorytmu:

obrazek

Zwróć uwagę na pewną ciekawą właściwość tak otrzymanych kodów binarnych:

A : 00
B : 010
C : 10
D : 011
E : 110
F : 111

Żadne słówko kodowe nie jest prefiksem innego słówka kodowego (ang. prefix-free code). Dzięki tej własności słówka kodowe można przesyłać jako strumień bitów bez wstawiania pomiędzy nie znaków przystankowych. Pomimo różnej długości słówek zawsze da się je jednoznacznie zdekodować w strumieniu - po prostu przechodzimy przez drzewo binarne skręcając w lewo dla bitu 0 lub w prawo dla bitu 1 aż dojdziemy do liścia, w którym mamy zdefiniowany symbol odpowiadający danemu słówku kodowemu.

Dane wejściowe

n  - adres korzenia drzewa binarnego

Dane wyjściowe

Zbiór kodów odpowiadających ścieżkom prowadzącym od korzenia do kolejnych liści, utworzonych wg opisanej powyżej metody:

c[ ]  - tablica znakowa zawierająca kolejny kod
lenc - zawiera długość kodu

Lista kroków

K01: inorder(n,c[ ], 0) Wyszukujemy rekurencyjnie wszystkie liście, wyprowadzając dla nich kody zawarte w c[ ]
K02: Zakończ  

Lista kroków rekurencyjnej funkcji przejścia inorder(n, c[ ], lenc)

K01: Jeśli n→lleft = NULL, wypisz n→ch oraz kod w c[ ] o długości lenc i zakończ Jeśli bieżący węzeł nie posiada potomka, to jest liściem. Wypisujemy kody
K02: c[lenc] ← '0'; inorder(n→lleft, c[ ], lenc + 1) W przeciwnym razie przeglądamy lewą gałąź poddrzewa binarnego
K03: c[lenc] ← '1'; inorder(n→right, c[ ], lenc + 1) A następnie prawą gałąź.
K04: Zakończ  

Algorytm inorder polega na rekurencyjnym odwiedzeniu lewego poddrzewa (drzewa związanego z lewym potomkiem węzła), a następnie na rekurencyjnym odwiedzeniu prawego poddrzewa. Algorytm inorder jest szczególnie użyteczny dla drzew binarnych.

       Program

Poniższy program tworzy drzewo binarne łącząc węzły losowo raz z prawej, a raz z lewej strony. Następnie przegląda wynikowe drzewo binarne wypisując kody wszystkich elementów wg powyższego algorytmu.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P015

#include <iostream>

using namespace std;

// deklaracja typu węzła drzewa binarnego

struct TBTNode
{
  struct TBTNode * parent, * left, * right;
  char ch;
};

// Funkcja rekurencyjne przechodzenia drzewa binarnego

void inorder(TBTNode * n, char c[], int lenc)
{
  if(!(n->left))
  {
    cout << n->ch << " : ";
    for(int i = 0; i < lenc; i++) cout << c[i];
    cout << endl;
  }
  else
  {
    c[lenc] = '0'; inorder(n->left,c,lenc + 1);
    c[lenc] = '1'; inorder(n->right,c,lenc + 1);    
  }
}

main()
{
  TBTNode * n, * x, * r;
  char c[16];  // tablica przechowująca kody ścieżek
  
  srand((unsigned)time(NULL));
  
// tworzymy pierwszy węzeł

  n = new TBTNode;
  n->parent = n->left = n->right = NULL;
  n->ch = 'A';
  
// Tworzymy 10 następnych węzłów łącząc je w drzewo binarne

  for(int i = 1; i < 10; i++)
  {
    x = new TBTNode;
    x->left = x->right = NULL;
    x->ch = 'A' + i;

// tworzymy nowy korzeń

    r = new TBTNode;
    r->parent = NULL;
    
// do korzenia dołączamy węzły n i x

    n->parent = x->parent = r;
    
    if(rand() % 2)
    {
      r->left = x; r->right = n;            
    }
    else
    {
      r->left = n; r->right = x;
    }

// n staje się nowym korzeniem drzewa

    n = r;    
  }

// przeglądamy utworzone drzewo wypisując kody elementów

  inorder(n,c,0);

  cout << endl << endl;
  system("pause");
}

I : 00
G : 0100
D : 0101000
B : 010100100
A : 010100101
C : 01010011
E : 010101
F : 01011
H : 011
J : 1

Dla otrzymanych wyników pracy programu drzewo binarne posiada poniższą strukturę:

obrazek

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie
©2024 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