Boom (datastructuur): verschil tussen versies

Een '''treeboom''' of '''[[boomstructuur]]''' is een [[datastructuur]] in de [[informatica]] die een bijzonder geval van een [[Grafentheorie|graaf]] is. Hij bestaat uit een ''knoop(punt)'' of ''vertex'' (Engels: ''node'') die de ''stam'' (ook wel ''wortel'', Eng.: ''root'') genoemd wordt, en die het ingangspunt is voor de in de boom opgeslagen informatie. In deze ''wortelknoop'' zitten nul of meer [[pointer (programmeerconcept)|pointers]] die naar andere knooppunten verwijzen. Ieder knooppunt behalve de wortel heeft precies een ''ouder'' (Eng.: ''parent node'') en nul of meer ''kinderen'' (Eng.: ''child nodes''). De verwijzingenVerwijzingen 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 treeboom 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'' (Eng.: ''leaf'').

Een ''[[binair]]e'' of ''[[Dichotomie|dichotome]] boom'' is een boomstructuur waarbij iedere knoop maximaal twee kinderen heeft. Een ''complete binaire boom'' is een boomstructuur waarin ieder blad zich op gelijke afstand bevindt van de wortelknoop. Iedere boom kan op vrij eenvoudige wijze in een binaire boom worden getransformeerd. Ook voor iedere graaf die geen niet-verbonden vertices heeft kan een boom worden gemaakt. Een ''geordende boom'' is een boomstructuur waarbij de kinderen een gedefinieerde volgorde hebben.