En ikke-lineær datastruktur består af en samling af de elementer, der er fordelt på et plan, hvilket betyder, at der ikke er nogen sådan sekvens mellem elementerne som den eksisterer i en lineær datastruktur.
Sammenligningstabel
| Grundlag for sammenligning | Træ | Kurve |
|---|---|---|
| Sti | Kun en mellem to hjørner. | Mere end en sti er tilladt. |
| Rodknude | Den har nøjagtigt en rodknude. | Grafen har ikke en rodknude. |
| loops | Ingen sløjfer er tilladt. | Grafen kan have sløjfer. |
| kompleksitet | Mindre kompleks | Mere kompleks forholdsvis |
| Traversal teknikker | Forbestilling, I-bestilling og Post-order. | Bredde-første søgning og dybde-første søgning. |
| Antal kanter | n-1 (hvor n er antallet af noder) | Ikke defineret |
| Model type | Hierarkisk | Netværk |
Definition af træ
Et træ er en endelige samling af dataposter, der normalt betegnes som knuder. Som det er nævnt ovenfor, er et træ en ikke-lineær datastruktur, som arrangerer dataposter i rækkefølge. Det bruges til at vise en hierarkisk struktur mellem de forskellige dataelementer og organiserer dataene i grene, der relaterer oplysningerne. Tilføjelsen af en ny kant i et træ resulterer i en dannelse af sløjfen eller kredsløbet.
Der er flere typer træer, såsom et binært træ, binært søgetræ, AVL-træ, trådt binærtræ, B-træ osv. Datakomprimering, arkivering, manipulation af det aritmetiske udtryk og spiltræer er noget af anvendelsen af træ datastruktur.
Træets egenskaber:
- Der er udpeget knude øverst på træet kendt som en rod af træet.
- De resterende dataelementer er opdelt i disjoint undergrupper henvises til som subtree.
- Træet er udvidet i højden mod bunden.
- Et træ skal forbindes, hvilket betyder, at der skal være en sti fra en rod til alle andre knuder.
- Det indeholder ingen løkker.
- Et træ har n-1 kanter.
Der er forskellige termer i forbindelse med træer som terminal node, kant, niveau, grad, dybde, skov osv. Blandt disse termer er nogle af dem beskrevet nedenfor.
- Kant - En linje, som forbinder to noder.
- Niveau - Et træ er opdelt i niveauer på en sådan måde, at rodknuden er på niveau 0. Derefter er dens umiddelbare børn på niveau 1, og dens umiddelbare børn er på niveau 2 og så videre op til terminalen eller bladknuden.
- Grad - Det er antallet af subtre af en node i et givet træ.
- Dybde - Det er det maksimale niveau for en node i et givet træ og også kendt som højde .
- Terminal node - Det højeste niveau knudepunkt er terminal node, mens andre noder undtagen terminal og root node er kendt som ikke-terminale noder.
Definition af graf
En graf er også en matematisk ikke-lineær datastruktur, som kan repræsentere forskellige former for fysisk struktur. Den består af en gruppe af hjørner (eller knuder) og sæt af kanter, som forbinder de to hjørner. Grafer på grafen er repræsenteret som punkt eller cirkler, og kanter vises som buer eller linjesegmenter. En kant er repræsenteret ved E (v, w), hvor v og w er parrene af hjørner. Fjernelse af en kant fra et kredsløb eller tilsluttet graf skaber en subgraph, der er et træ.
Graferne er klassificeret i forskellige kategorier som direkte, ikke-rettet, tilsluttet, ikke-tilsluttet, enkel og multi-graf. Computer netværk, transport system, sociale netværk graf, elektriske kredsløb og projektplanlægning er nogle af de applikationer af graf data struktur. Det er også ansat i ledelsesteknik, der er opkaldt som PERT (programevaluering og gennemgangsteknik) og CPM (kritisk vejmetode), hvor grafstrukturen analyseres.
Egenskaber for en graf:
- Et hjørne i en graf kan forbindes til et hvilket som helst antal andre hjørner ved hjælp af kanter.
- En kant kan være vejledende eller rettet.
- En kant kan vægtes.
I graf bruger vi også forskellige udtryk som tilstødende hjørner, sti, cyklus, grad, tilsluttet graf, komplet graf, vægtet graf osv. Lad os forstå nogle af disse udtryk.
- Tilgrænsende hjørner - En vinkel a ligger ved siden af vertex b, hvis der er en kant (a, b) eller (b, a).
- Sti - En sti fra et tilfældigt vertex w er en tilstødende sekvens af hjørner.
- Cyklus - Det er en sti, hvor de første og sidste hjørner er de samme.
- Grad - Det er en række kanter, der forekommer på et vertex.
- Tilknyttet graf - Hvis der findes en sti fra et tilfældigt vertex til et hvilket som helst andet toppunkt, så er den graf kendt som en tilsluttet graf.
Nøgleforskelle mellem træ og graf
- I et træ eksisterer der kun en vej mellem de to to hjørner, medens en graf kan have ensretnings- og tovejsstier mellem knudepunkterne.
- I træet er der nøjagtigt en rodknude, og hvert barn kan kun have en forælder. I modsætning til, i en graf er der intet koncept af rodknuden.
- Et træ kan ikke have sløjfer og selvløkker, mens graf kan have sløjfer og selvløkker.
- Grafer er mere komplicerede, da det kan have sløjfer og selvløkker. I modsætning hertil er træer enkle sammenlignet med grafen.
- Træet krydses ved hjælp af forudbestillings-, i-ordnings- og postorderteknikker. På den anden side bruger vi BFS (Breadth First Search) og DFS (Dyb First Search) til graf-traversal.
- Et træ kan have n-1 kanter. Tværtimod er der i grafen ikke noget foruddefineret antal kanter, og det afhænger af grafen.
- Et træ har en hierarkisk struktur, mens grafen har en netværksmodel.
Konklusion
Graf og træ er den ikke-lineære datastruktur, som bruges til at løse forskellige komplekse problemer. En graf er en gruppe af hjørner og kanter, hvor en kant forbinder et par hjørner, medens et træ betragtes som en minimalt forbundet graf, der skal forbindes og fri for sløjfer.
