Drukowanie zawartości drzew

W tym artykule zamierzam objaśnić sposób, w jaki można przy pomocy rekurencji drukować na konsolę zawartość struktury danych jaką jest drzewo.

Czym są drzewa?

Drzewa są strukturami linkowanymi podobnymi do list, tyle że lista jest jednociągowa, a w drzewie z każdego elementu (węzła) może wychodzić różna liczba "gałęzi" (wskaźników) do innych elementów i tak dalej. Tutaj zajmiemy się wyłącznie drzewami, w których z węzła wychodzą maksymalnie dwie gałęzie - lewa i prawa.

Implementacja struktury drzewa

Implementacja struktury drzewa zgodnie z powyższym opisem, gdzie każdy węzeł przechowuje liczbę, może w języku C wyglądać następująco:

struct node
{
  int value;
  struct node *left;
  struct node *right;
}

Drukowanie drzewa

Przechodzimy do tematu, czyli jak wydrukować całą zawartość drzewa.

Algorytm

Użyjemy następującego algorytmu rekurencyjnego:

1. Wydrukuj zawartość bieżącego węzła
2. Jeśli odchodzi lewa gałąź, drukuj węzeł na który wskazuje
3. Później zrób to samo na ewentualnej prawej gałęzi

Implementacja

Przykładowa implemetacja w postaci funkcji `printtree` może wyglądać następująco:

void printtree (struct node nd)
{
  printf ("%d\n", nd.value);
  if (nd.left)
    printtree (* (nd.left));
  if (nd.right)
    printtree (* (nd.right));
}

Rozszerzenie

Wyjście wytwarzane przez aktualną funkcję ma jedną wadę: nie widać tak naprawdę struktury drzewa. Na przykład jeśli dostaniemy:

123
456
789

To nie wiemy, czy drzewo ma postać taką:

123
 456
  789

Czy może taką?

123
 456
 789

Aby uwidocznić tę różnicę, musimy dodać wcięcia. Konieczne będzie więc przekazywanie poziomu pokrewieństwa jako dodatkowego argumentu do funkcji, aby wydrukować właściwe wcięcie, jak w nowej wersji niżej:

void printtree (struct node nd, unsigned level)
{
  unsigned i;
  for (i = 0; i < level; i++)
    putchar (' ');
  printf ("%d\n", nd.value);
  if (nd.left)
    printtree (* (nd.left), level + 1);
  if (nd.right)
    printtree (* (nd.right), level + 1);
}

Oczywiście będzie trzeba dodatkowo podawać zero jako pozim zagnieżdżenia na starcie, czyli zamiast printtree (drzewo) będzie trzeba pisać printtree (drzewo, 0) ale i na to jest rozwiązanie:

void _printtree (struct node nd, unsigned level)
{
  unsigned i;
  for (i = 0; i < level; i++)
    putchar (' ');
  printf ("%d\n", nd.value);
  if (nd.left)
    _printtree (* (nd.left), level + 1);
  if (nd.right)
    _printtree (* (nd.right), level + 1);
}

void printtree (struct node nd)
  { _printtree (nd, 0); }

Przykładowe pomysły na dalsze rozszerzanie

• Drukowanie drzew o dowolnej liczbie gałęzi
• Drukowanie w formacie hipertekstowym (HTML, RTF)
• Drukowanie do podanego strumienia (nie tylko standardowe wyjście)