logo

Binær tredatastruktur

EN Binær tredatastruktur er en hierarkisk datastruktur der hver node har maksimalt to barn, referert til som venstre barn og høyre barn. Det brukes ofte i informatikk for effektiv lagring og gjenfinning av data, med ulike operasjoner som innsetting, sletting og kryssing.

Binær tredatastruktur



Introduksjon:

  • Egenskaper til binært tre
  • Typer av binære tre
  • Bruksområder, fordeler og ulemper med binært tre
  • Binært tre (matriseimplementering)
  • Komplett binært tre
  • Perfekt binært tre

Grunnleggende operasjoner på binært tre:

Noen andre viktige binære treoverganger:

  • Nivåordregjennomgang i spiralform
  • Omvendt nivå ordregjennomgang
  • BFS vs DFS for binært tre
  • Inorder Tree Traversal uten rekursjon
  • Morris-traversal for forhåndsbestilling
  • Iterativ forhåndsbestillingsgjennomgang
  • Iterativ postordregjennomgang ved bruk av to stabler
  • Diagonal traversering av binært tre
  • Grensegjennomgang av binært tre

Enkle problemer på binær tredatastruktur:

  • Beregn dybden til et fullt binært tre fra forhåndsbestilling
  • Konstruer et tre fra Inorder- og Level-ordregjennomganger
  • Sjekk om et gitt binært tre er SumTree
  • Sjekk om to noder er søskenbarn i et binært tre
  • Sjekk om fjerning av en kant kan dele et binært tre i to halvdeler
  • Sjekk om et gitt binært tre er perfekt eller ikke
  • Sjekk om et binært tre inneholder dupliserte undertrær av størrelse 2 eller mer
  • Sjekk om to trær er Mirror
  • Sammenleggbare binære trær
  • Symmetrisk tre (speilbilde av seg selv)
  • Skriv kode for å finne ut om to trær er identiske
  • Undertre med gitt sum i et binært tre
  • Kortfattet koding av binært tre
  • Skriv et program for å beregne størrelsen på et tre
  • Diameteren til et binært tre
  • Få nivået til en node i et binært tre

Middels problemer på binær tredatastruktur:

  • Finn alle mulige binære trær med gitt Inorder Traversal
  • Fyll inn rekkefølger for alle noder
  • Konstruer komplett binært tre fra dens lenkede listerepresentasjon
  • Minimum swap kreves for å konvertere binært tre til binært søketre
  • Konverter et gitt binært tre til dobbeltlenket liste | Sett 1
  • Konverter et tre til skog med jevne noder
  • Vend binært tre
  • Skriv ut rot-til-blad-baner uten å bruke rekursjon
  • Sjekk om gitte Preorder, Inorder og Postorder traverseringer er av samme tre
  • Sjekk om et gitt binært tre er komplett eller ikke | Sett 1 (Iterativ løsning)
  • Sjekk om et binært tre er undertre til et annet binært tre | Sett 2
  • Finn største deltresum i et tre
  • Maksimal sum av noder i binært tre slik at ikke to er tilstøtende
  • Laveste felles stamfar i et binært tre | Sett 1
  • Høyden på et generisk tre fra overordnet array
  • Finn avstanden mellom to gitte nøkler til et binært tre

Harde problemer på binær tredatastruktur:

  • Endre et binært tre for å få forhåndsbestillingsgjennomgang kun ved å bruke høyrepekere
  • Konstruer fullt binært tre ved å bruke forhåndsbestillings-traverseringen og forhåndsbestill-traverseringen av speiltreet
  • Konstruer et spesielt tre fra gitt forhåndsbestilling
  • Konstruer treet fra stamfarmatrise
  • Konstruer hele k-ary-treet fra dets forhåndsbestillingsgjennomgang
  • Konstruer binært tre fra streng med parentesrepresentasjon
  • Konverter et binært tre til dobbeltlenket liste i spiralform
  • Konverter et binært tre til en sirkulær dobbeltkoblingsliste
  • Konverter ternært uttrykk til et binært tre
  • Sjekk om det er en rot-til-blad-bane med gitt rekkefølge
  • Fjern alle noder som ikke ligger i noen bane med sum>= k
  • Maksimal spiralsum i binært tre
  • Summen av noder på k-te nivå i et tre representert som streng
  • Summen av alle tallene som dannes fra rot- til bladstier
  • Slå sammen to binære trær ved å gjøre nodesum (rekursiv og iterativ)
  • Finn roten til treet der barnas id-sum for hver node er gitt

Hurtigkoblinger :

Anbefalt:

  • Lær datastruktur og algoritmer | DSA veiledning