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.
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:
- Treoverganger (Inorder, Preorder og Postorder)
- Nivåordre-tregjennomgang
- Finn maksimal dybde eller høyde for gitt binært tre
- Innsetting i et binært tre
- Sletting i et binært tre
- Oppregning av binære trær
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