Spłaszczanie drzewa

Czasami przychodzi nam operować na strukturach drzewiastych. Drzewko, jak sama nazwa wskazuje, składa się z elementów połączonych relacjami nadrzędny-podrzędny . (OK, może nazwa tego nie wskazuje, ale wiadomo to skądinąd ;]). W językach programowania połączenia te realizujemy poprzez wskaźniki albo podobne mechanizmy, jak na przykład referencje.

Drzewa mogą być oczywiście ustalonego rzędu (jak choćby drzewa binarne) i wtedy ich przechowywanie nie nastręcza większych trudności. Nieco gorzej jest wtedy, gdy każdy węzeł może mieć dowolną liczbę węzłów podrzędnych. Wtedy często wygodnie jest przechowywać je w formie dynamicznej struktury danych: tablicy albo listy. Przynajmniej dopóty, dopóki nasze drzewo rezyduje wyłącznie w pamięci…
Może bowiem przyjść konieczność zapisania go w trwalszym miejscu. Pół biedy, jeśli docelowy format sam w sobie ma strukturę drzewiastą i umożliwia uporządkowanie danych w sposób hierarchiczny – tak jak chociażby XML. Ale nie zawsze mamy taki luksus. Weźmy na przykład wirtualny system plików (VFS), w którego archiwum chcemy zapisać (drzewiastą, rzecz jasna) strukturę katalogów – w formie binarnej. Podobnych sytuacji jest całkiem sporo, zwłaszcza gdy mamy do czynienia z relacyjnymi bazami danych.

Prawdopodobnie właśnie stamtąd wywodzi się najprostsze i chyba najczęściej stosowane rozwiązanie problemu. Polega ono na oznaczeniu każdego węzła drzewa unikalnym identyfikatorem (np. liczbą) i zapisaniu razem z węzłem (oprócz związanych z nim danych) także identyfikatora węzła nadrzędnego. W ten sposób zachowujemy wszystkie informacje o hierarchii. Metoda ta ma tę zaletę, że jest prosty i wymaga niewielkiej liczby dodatkowych danych.
Wadą mogłoby być to, iż w tej postaci nijak nie da się takiego drzewa przejść ani wyszukiwać w nim. Lecz to nie jest tak naprawdę ważne, gdyż dla potrzeb programu możemy na podstawie tej reprezentacji skonstruować normalne, “wskaźnikowe” drzewo. W tym celu wystarczy najpierw stworzyć wszystkie węzły (zapisując oba związane z nimi identyfikatory), a następnie odbudować powiązania między nimi, posługując się odwzorowaniem identyfikator -> węzeł, utworzonym podczas wczytywania. Bardzo przydaje się do tego struktura danych w rodzaju mapy (słownika).