11
Tags:
c#
Skrevet af
Bruger #4522
@ 20.12.2008
Introduktion
I denne artikel skal vi kigge lidt på træer. I modsætning til mange af de mere almindelige datastrukturer, som er lineære, har træer forgreninger. Dette betyder at måden hvorpå vi opbygger - og gennemgår - træer, præsenterer os med nogle flere muligheder, og også med flere valg der skal træffes.
Lad os starte med at kigge lidt på hvad træer egentlig er...
Træer
Et træ er en datastruktur der består af en samling elementer kaldet knuder. Navnet skyldes at det ligner et rigtig træ, bare vendt på hovedet. Knuderne er forbundet til hindanden via relationer kaldet grene (eller kanter). Træets knuder bruges til at holde data.
En enkelt knude er også i sig selv et træ. Derudover kalder man et tomt træ (dvs. et træ uden nogle knuder og altså derfor også uden noget data) for et trivielt træ.
Alle træer har et udgangspunkt, kaldet dets rod. Typisk er træer illustreret ved at vise roden øverst på tegningen, og alle knuderne følger så under roden i en træstruktur. De nederste knuder, som derfor ikke refererer til nogle knuder længere nede i træet, kaldes for blade, eller bladknuder. Alle andre knuder kaldes for indre knuder. Et træ kan også inddeles i undertræer. Et undertræ er en knude og de knuder som der refereres til herfra.
Et par illustrationer vil nok være på sin plads nu.
Som det kan ses ligner disse strukturer almindelige træer, blot vendt på hovedet.
En knudes forælder er den knude den er forbundet til i niveauet umiddelbart over dens eget niveau. Hermed kan vi også definere et træs rod som den knude der ingen forælder har. En knudes forfædre er alle de knuder der er rødder i træer der indeholder pågældende knude: knudens forælder, og dennes forælder etc. Roden er derfor forfader til alle knuder i træet. En knudes barn er de knuder som har pågældende knude til forælder. Vi kan derfor nu definere en bladknude som en knude uden børn. En knudes afkom er alle de knuder der har pågældende knude som forfader. Det er nok igen på tide at se noget af dette illustreret.
Vi bruger også udtrykket søskende om knuder. To knuder er, ikke overraskende, søskende hvis de deler en forælder. På lignende vis kan man også bruge udtryk som onkel osv. hvis det gør det nemmere at forklare en algoritme eller lignende. Hvis en knude har to børn, kan vi også bruge udtryk som "venstre barn" og "højre barn" til at gøre det klart hvilken knude vi snakker om.
En sti i et træ er en unik sekvens af forgreninger (også kaldet kanter) fra en knude til en forfader. En sådanne stis længde er antallet af kanter som den spænder. En knudes højde er længden af den længste sti fra en bladknude til pågældende knude. Et træs højde er højden af roden. En knudes dybde er derimod længden af den længste sti fra pågældende knude til træets rod. Summen af en knudes højde og dybde er aldrig større en træets højde.
En knudes grad er antallet af børn til knuden. Et træs grad er den højeste grad der kan findes bland dens børn. Et binært træ har en grad mindre end eller lig med to. En knude i et binært træ er fuldt, såfremt den har to børn. Et fuldt binært træ, med en højde på
h, har kun bladknuder på niveau
h, og alle dens interne knude er fulde. Et komplet binært træ er et fuldt træ bortset fra at nogle af bladknuderne på niveau
h mangler.
Lad os se dette illustreret med nogle eksempler.
Hvad synes du om denne artikel? Giv din mening til kende ved at stemme via pilene til venstre og/eller lægge en kommentar herunder.
Del også gerne artiklen med dine Facebook venner:
Kommentarer (4)
Nu har jeg godt nok aldrig kodet i C# før men den kode der virker på som alt for lang til en implementation af binær træer.
Og så bliver jeg lige nød til at spørge hvordan den der insert skulle virke for hvis jeg kaldte insert 2 gange på et tomt træ ville jeg efter min overbevisning få en exception smidt i hovedet, eller forestille du dig at man selv skulle sidde og rykke rundt med move funktionerne til man fandt en node med frie børn?
Hej Nørden.
Insert indsætter en knude i et tomt træ. Man flytter så markøren ud af træet v.h.a. MoveLeft og MoveRight, og kalder da Insert.
Måske ville det være på sin plads med et eller flere kode eksempler på hvordan du forestiller dig man rent faktisk brugte din kode.
Tror ikke at jeg er den eneste der ville få problemer med at bruge det
.
Du kunne f.eks lave eksempler på hvordan man bygger træet, sletter i det og bruger en eller flere af de der iteratorer, men det bare et forslag.
PS så synes jeg det en god artikel, men hvis du kan rette i den burde du evt, lave en eller flere(en per fil) bokse med all koden i tilsidst, ville gøre det lettere at kopier den.
Hej Nørden.
Det har du helt ret i. Det gik op for mig da jeg læste din kommentar at jeg skulle have tilføjet et eksempel på brug af koden. En åbenlys mangel. Jeg vil opdatere artiklen med et eksempel inden længe.
Tak for kommentarene.
Du skal være
logget ind for at skrive en kommentar.