I denne vejledning lærer du om træets datastruktur. Du vil også lære om forskellige typer træer og de terminologier, der bruges i træet.
Et træ er en ikke-lineær hierarkisk datastruktur, der består af noder forbundet med kanter.
Et træ
Hvorfor trædatastruktur?
Andre datastrukturer såsom arrays, sammenkædet liste, stak og kø er lineære datastrukturer, der lagrer data sekventielt. For at udføre enhver operation i en lineær datastruktur øges tidskompleksiteten med stigningen i datastørrelsen. Men det er ikke acceptabelt i nutidens beregningsverden.
Forskellige trædatastrukturer giver hurtigere og lettere adgang til dataene, da det er en ikke-lineær datastruktur.
Træterminologier
Node
En node er en enhed, der indeholder en nøgle eller værdi og peger på dens underordnede noder.
De sidste noder på hver sti kaldes bladnoder eller eksterne noder , der ikke indeholder et link / markør til underordnede noder.
Den node, der mindst har en undernode, kaldes en intern node .
Edge
Det er forbindelsen mellem to knudepunkter.
Noder og kanter på et træ
Rod
Det er den øverste knude på et træ.
Højde på en knude
Højden på en node er antallet af kanter fra noden til det dybeste blad (dvs. den længste sti fra noden til en bladnode).
Dybde af en node
Dybden af en node er antallet af kanter fra roden til noden.
Træets højde
Højden på et træ er højden på rodnoden eller dybden af den dybeste node.
Højde og dybde af hver knude i et træ
Grad af en node
Graden af en node er det samlede antal grene af den node.
Skov
En samling af usammenhængende træer kaldes en skov.
Oprettelse af skov fra et træ
Du kan oprette en skov ved at skære roden af et træ.
Typer af træ
- Binært træ
- Binært søgetræ
- AVL-træ
- B-træ
Træ gennemgange
For at udføre enhver operation på et træ skal du nå til den specifikke knude. Træ traversal algoritmen hjælper med at besøge en krævet node i træet.
Hvis du vil vide mere, skal du besøge tree traversal.
Træapplikationer
- Binære søgetræer (BST'er) bruges til hurtigt at kontrollere, om et element er til stede i et sæt eller ej.
- Heap er en slags træ, der bruges til bunksortering.
- En modificeret version af et træ kaldet Tries bruges i moderne routere til at gemme routinginformation.
- Mest populære databaser bruger B-Trees og T-Trees, som er varianter af den træstruktur, vi har lært ovenfor for at gemme deres data
- Kompilatorer bruger et syntaks-træ til at validere syntaksen for hvert program, du skriver.
