EN Binær trædatastruktur er en hierarkisk datastruktur, hvor hver node højst har to børn, kaldet det venstre barn og det højre barn. Det er almindeligt anvendt i datalogi til effektiv lagring og hentning af data med forskellige operationer såsom indsættelse, sletning og gennemkøring.
Introduktion:
- Egenskaber af binært træ
- Typer af binære træer
- Anvendelser, fordele og ulemper ved binært træ
- Binært træ (Array-implementering)
- Komplet binært træ
- Perfekt binært træ
Grundlæggende handlinger på binært træ:
- Trægennemgange (Inorder, Preorder og Postorder)
- Level Order Tree Traversal
- Find den maksimale dybde eller højde for givet binært træ
- Indsættelse i et binært træ
- Sletning i et binært træ
- Optælling af binære træer
Nogle andre vigtige binære trægennemgange:
- Niveauordregennemgang i spiralform
- Reverse Level Order Traversal
- BFS vs DFS for binært træ
- Inorder trægennemgang uden rekursion
- Morris-traversal for forudbestilling
- Iterativ Preorder Traversal
- Iterativ postordre-gennemkørsel ved hjælp af to stakke
- Diagonal gennemkørsel af binært træ
- Grænsegennemgang af binært træ
Lette problemer på binær trædatastruktur:
- Beregn dybden af et fuldt binært træ fra forudbestilling
- Konstruer et træ ud fra Inorder- og Level-ordregennemgange
- Tjek om et givet binært træ er SumTree
- Tjek om to noder er fætre i et binært træ
- Tjek, om fjernelse af en kant kan dele et binært træ i to halvdele
- Tjek, om et givet binært træ er perfekt eller ej
- Tjek, om et binært træ indeholder duplikerede undertræer af størrelse 2 eller mere
- Tjek om to træer er spejl
- Sammenfoldelige binære træer
- Symmetrisk træ (spejlbillede af sig selv)
- Skriv kode for at bestemme, om to træer er identiske
- Undertræ med given sum i et binært træ
- Kortfattet kodning af binært træ
- Skriv et program til at beregne størrelsen af et træ
- Diameter af et binært træ
- Få niveauet for en node i et binært træ
Mellemstore problemer på binær trædatastruktur:
- Find alle mulige binære træer med givet Inorder Traversal
- Udfyld Inorder Successor for alle noder
- Konstruer komplet binært træ fra dets linkede listerepræsentation
- Minimum swap påkrævet for at konvertere binært træ til binært søgetræ
- Konverter et givet binært træ til dobbeltforbundet liste | Sæt 1
- Konverter et træ til skov med lige knuder
- Vend binært træ
- Udskriv rod til blad-stier uden brug af rekursion
- Tjek, om forudbestilling, Inorder og Postorder gennemgange er af samme træ
- Tjek, om et givet binært træ er komplet eller ej | Sæt 1 (Iterativ løsning)
- Tjek, om et binært træ er undertræ til et andet binært træ | Sæt 2
- Find største deltræsum i et træ
- Maksimal sum af noder i binært træ, således at der ikke er to tilstødende
- Laveste fælles forfader i et binært træ | Sæt 1
- Højde på et generisk træ fra forældrearray
- Find afstanden mellem to givne nøgler i et binært træ
Hårde problemer på binær trædatastruktur:
- Rediger et binært træ for at få forudbestillingsgennemgang kun ved at bruge højre pointere
- Konstruer fuldt binært træ ved at bruge dets Preorder traversal og Preorder traversal af dets spejltræ
- Konstruer et specielt træ ud fra en given forudbestillingsgennemgang
- Konstruer træ fra forfader matrix
- Konstruer det fulde k-ary-træ ud fra dets forudbestillingsgennemgang
- Konstruer binært træ fra streng med parentesrepræsentation
- Konverter et binært træ til dobbeltforbundet liste i spiralform
- Konverter et binært træ til en cirkulær dobbeltlinkliste
- Konverter ternært udtryk til et binært træ
- Tjek, om der er en rod til blad-sti med en given sekvens
- Fjern alle noder, der ikke ligger i nogen sti med sum>= k
- Maksimal spiralsum i binært træ
- Summen af noder på k-te niveau i et træ repræsenteret som streng
- Summen af alle de tal, der er dannet fra rod til bladbaner
- Flet to binære træer ved at lave nodesum (rekursiv og iterativ)
- Find roden af træet, hvor børns id-sum for hver node er givet
Hurtige links :
Anbefalede:
- Lær datastruktur og algoritmer | DSA Tutorial