Boom (datastructuur)

Een boom of boomstructuur is een datastructuur in de informatica die een bijzonder geval van een graaf is. Een boom bestaat uit een knoop(punt) of vertex die de stam (ook wel wortel) genoemd wordt en die het ingangspunt is voor de in de boom opgeslagen informatie. In deze wortelknoop zitten nul of meer pointers die naar andere knooppunten verwijzen. Ieder knooppunt behalve de wortel heeft precies een ouder en nul of meer kinderen. Verwijzingen gaan dus nooit tussen de kinderen onderling maar alleen van ouder naar kind; in een wat uitgebreidere versie eventueel ook van kind naar ouder (bidirectionele graaf). In een boom bestaan geen cirkelpaden en is er altijd precies 1 pad van de wortel naar een willekeurige knoop. Een knoop die zelf geen kinderen heeft noemt men een blad.