Liść (informatyka)

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Liśćmi w tym drzewie są wierzchołki 9, 14, 19, 67 oraz 76

Liść – węzeł (element) drzewa, który nie posiada potomków. Często liśćmi są węzły najbardziej oddalone od korzenia. Rozpatrując drzewiastą strukturę danych jako graf drzewiasty można powiedzieć, że liście to wierzchołki o stopniu 1, które nie są korzeniem (wyjątkiem jest tu drzewo złożone tylko z korzenia, wówczas jest on także liściem). Węzeł niebędący liściem nazywany jest węzłem wewnętrznym.

Niektóre drzewa przechowują dane tylko w węzłach wewnętrznych, co ułatwia dostęp do danych. Dla przykładu, jeżeli przyjmiemy, że liście drzewa są puste, to drzewo złożone z tylko jednego elementu jest drzewem pustym. Gdy liście zawierają dane, puste drzewo musiałoby być oznaczone dodatkowym znacznikiem.

Przyjmuje się także wariant, w którym dane przechowywane są w liściach. Wówczas węzły wewnętrzne przechowują jedynie metadane, jak zakres danych w umieszczonych potomnych liściach. Takie drzewa ułatwiają wyszukiwanie danych.

Programowanie genetyczne[edytuj | edytuj kod]

W programowaniu genetycznym liść to najbardziej zewnętrzna cześć programu, często nazywana także terminalem. Węzły wewnętrzne są wówczas funkcjami.