Wprowadzenie

Drzewa to hierarchiczne struktury danych. Znajdują zastosowanie przy tworzeniu baz danych, przetwarzaniu tekstu czy w telekomunikacji. Typowe drzewo składa się z połączonych ze sobą wierzchołków nazywanych węzłami (ang. node).

Pierwszy to korzeń (ang. root node) lub węzeł główny (ang. main node). Każdy z węzłów może mieć wiele połączonych z nim węzłów znajdujących się na niższym poziomie. Występuje wtedy relacja rodzic-dziecko. Mamy wtedy do czynienia z węzłem rodzicem (ang. parent node) , który możemy nazwać węzłem nadrzędnym, i jego dziećmi (ang. child node) , nazywanymi węzłami potomnymi lub podwęzłami (ang. subnode). Wyjątkiem jest korzeń, który nie ma węzła rodzica. Węzły, które nie mają dzieci, nazywane są liśćmi (ang. leaf).

Cechą charakterystyczną drzew jest to, że pomiędzy dowolnym węzłem a korzeniem istnieje jedna i tylko jedna droga połączeń.