drzewo

drzewo,

inform. struktura danych mająca postać drzewa (mat.), w którym jest wyróżniony jeden wierzchołek, zwany korzeniem;

każdy wierzchołek z wyjątkiem korzenia ma dokładnie jeden poprzednik (tj. sąsiedni wierzchołek na ścieżce łączącej dany wierzchołek z korzeniem); każdy wierzchołek może mieć następniki (wierzchołki, dla których jest poprzednikiem); wierzchołek nie mający następników jest nazywany liściem. Dla każdego wierzchołka w drzewie jest zdefiniowany jego poziom, tj. długość drogi (ścieżki) między wierzchołkiem a korzeniem (mierzona liczbą krawędzi). Największy poziom wierzchołka nazywa się wysokością drzewa. Szczególnym przypadkiem drzewa jest drzewo binarne, w którym każdy wierzchołek ma co najwyżej 2 następniki (lewy i prawy). Przykładowo drzewo wyrażenia to zapis wyrażenia arytmetycznego lub logicznego w postaci drzewa binarnego, w którym wierzchołkami są operatory, a liśćmi — stałe lub zmienne; drzewo wyrażenia pozwala jednoznacznie określić kolejność wykonywania operacji. Drzewo decyzyjne opisuje kolejność podejmowanych decyzji i ich konsekwencji, np. w przypadku gry w szachy każdy węzeł odpowiada jednemu ruchowi (i sytuacji powstałej w jego wyniku); następniki wierzchołka opisują wszystkie możliwe ruchy przeciwnika w tej sytuacji; liście opisują stany, w których nie ma już żadnych decyzji do podjęcia (np. mat w szachach); dla szachów takie drzewo może być nieskończone, gdyż istnieją nieskończone ciągi ruchów.