Drzewa binarne

Drzewo wolne to graf nieskierowany, spójny i acykliczny.

• nieskierowany oznacza, że krawędzie są zbiorem par nieuporządkowanych,

• spójny oznacza, że każda para węzłów jest połączona,

• acykliczny oznacza, że graf nie zawiera cykli.

Drzewo ukorzenione drzewo wolne z wyróżnionym jednym węzłem - korzeniem.
Przodek węzła każdy węzeł na drodze od danego węzła do korzenia.
Potomek węzła operacja odwrotna do powyższej.
Poprzednik, rodzic węzła bezpośredni przodek węzła.
Następnik, dziecko węzła bezpośredni potomek węzła.
Liść węzeł drzewa, który nie ma potomków.
Stopień, rząd węzła liczba jego następników.
Stopień, rząd drzewa maksymalny stopień spośród wszystkich stopni tego drzewa.
Ścieżka ciąg węzłów, takich że poprzedni jest rodzicem następnego.
Długość ścieżki ścieżka (n

1

, . . . , n

k

) ma długość k − 1, długość ścieżki dla pojedynczego węzła

to 0.
Wysokość drzewa to długość najdłuższej ścieżki od korzenia do liścia.
Głębokość węzła długość ścieżki od korzenia do danego węzła.

1