Binärträd

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-03) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Ett binärträd är en datastruktur av trädtyp i vilken varje nod har högst två barn. En vanlig användning är i form av ett binärt sökträd. Varje träd har en rot, det är den nod i trädet som inte har någon förälder. Om man följer en väg från rot och går längst ner kommer man till ett löv. Löv är noder som saknar barn.

Definitioner

• En riktad kant är länken mellan en nod och ett barn (pilarna i bilden).
• Rotnoden är noden utan någon förälder (noden längst upp i bilden). Det kan bara finnas en rotnod.
• Förälder är noden ovanför som har en riktad kant ner till den aktuella noden.
• Ett barn är en nod under den aktuella noden som vi har en riktad kant till.
• Ett löv är en nod utan några barn.
• Djupet för en nod är antalet steg från rotnoden till noden. Rotnoden är på djup 0, dess barn är på djup 1, osv.
• Höjden för trädet är det största djupet i trädet. Ett träd med bara en rotnod har höjd 0.
• Syskon är noder med samma förälder.
• Delträd eller subträd är en del av trädet.

Källor

Se även

• B-träd