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[redigera | redigera wikitext]
- 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.