Binärträd

Från Wikipedia
Hoppa till: navigering, sök
Konceptuell bild av ett binärt träd

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. En nod består alltid av minst tre värden nämligen värdet som noden själv har, en adress till sitt "vänsterbarn" samt en adress till sitt "högerbarn".[1] Det är också möjligt att noden hänvisar till sin förälder.

Definitioner[redigera | redigera wikitext]

  • En riktad kant är länken mellan en nod och ett barn (pilarna i bilden)
  • Rotnoden är noden utan några föräldrar (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[redigera | redigera wikitext]

  1. ^ Brookshear J. Glenn, "Computer Science an Overview", sidan 344, Addison-Wesley, 2011

Se även[redigera | redigera wikitext]