En icke-linjär datastruktur består av en samling av elementen som distribueras på ett plan vilket innebär att det inte finns någon sådan sekvens mellan elementen som den existerar i en linjär datastruktur.
Jämförelsediagram
| Grunder för jämförelse | Träd | Graf |
|---|---|---|
| Väg | Bara en mellan två hörn. | Mer än en väg är tillåten. |
| Rotknutpunkt | Den har exakt en rotknutpunkt. | Grafen har ingen rotknutpunkt. |
| Loops | Inga slingor är tillåtna. | Grafen kan ha loopar. |
| Komplexitet | Mindre komplex | Mer komplicerat relativt |
| Traversal tekniker | Förbeställning, beställning och postorder. | Bredd - första sök och djup-första sökning. |
| Antal kanter | n-1 (där n är antalet noder) | Inte definierad |
| Modell typ | Hierarkisk | Nätverk |
Definition av träd
Ett träd är en ändlig samling av dataposter som vanligen kallas som noder. Som nämnts ovan är ett träd en icke-linjär datastruktur som ordnar dataposter i sorterad ordning. Den används för att visa en hierarkisk struktur mellan de olika dataelementen och organiserar data i grenar som relaterar informationen. Tillsatsen av en ny kant i ett träd resulterar i en formning av slingan eller kretsen.
Det finns flera typer av träd som binärt träd, binärt sökt träd, AVL-träd, trådat binärt träd, B-träd, etc. Datakomprimering, fillagring, manipulation av det aritmetiska uttrycket och spelträdorna är en del av trädets tillämpning datastruktur.
Träets egenskaper:
- Det är utvalt nod på toppen av trädet som kallas trädets rot.
- De återstående dataposterna är uppdelade i ojämna subgrupper som subtree.
- Träet är expanderat i höjd mot botten.
- Ett träd måste vara anslutet vilket innebär att det måste finnas en väg från en rot till alla andra noder.
- Det innehåller inga loopar.
- Ett träd har n-1 kanter.
Det finns olika termer som hör samman med träd som terminalnod, kant, nivå, grad, djup, skog, etc. Bland dessa villkor beskrivs några av dem nedan.
- Kant - En linje som förbinder två noder.
- Nivå - Ett träd är uppdelat i nivåer på ett sådant sätt att rotnodet ligger på nivå 0. Därefter är dess omedelbara barn på nivå 1 och dess närmaste barn ligger på nivå 2 och så vidare upp till terminalen eller lövnoden.
- Grad - Det är antalet subtre av en nod i ett givet träd.
- Djup - Det är den maximala nivån på någon nod i ett givet träd och även känd som höjd .
- Terminalnod - Högsta nivån är terminalnod medan andra noder utom terminal och rootnod är kända som icke-terminala noder.
Definition av graf
Ett diagram är också en matematisk icke-linjär datastruktur som kan representera olika typer av fysisk struktur. Den består av en grupp hörn (eller noder) och uppsättning kanter som förbinder de två vertikalerna. Vertikaler på grafen representeras som punkt eller cirklar och kanter visas som bågar eller linjesegment. En kant representeras av E (v, w) där v och w är paren av punkter. Avlägsnande av en kant från en krets eller kopplad graf skapar en subgraph som är ett träd.
Graferna klassificeras i olika kategorier, såsom direkt, icke-riktad, ansluten, icke-ansluten, enkel och multi-graf. Datornät, transportsystem, sociala nätverk, elektriska kretsar och projektplanering är några av applikationerna för grafdatastrukturen. Det är också anställd i ledningsteknik som kallas PERT (programutvärdering och granskningsteknik) och CPM (kritisk sökvägsmetod) där grafstrukturen analyseras.
Egenskaper för ett diagram:
- Ett toppunkt i ett diagram kan kopplas till ett antal andra vertikaler med kanter.
- En kant kan riktas direkt eller riktas.
- En kant kan vägas.
I diagram använder vi också olika termer som intilliggande vinklar, väg, cykel, grad, kopplad graf, komplett graf, vägd graf etc. Låt oss förstå några av dessa termer.
- Angränsande hörn - En toppunkt a ligger intill vertex b om det finns en kant (a, b) eller (b, a).
- Sti - En väg från ett slumpmässigt vertex w är en intilliggande sekvens av punkter.
- Cykel - Det är en väg där de första och sista kryssarna är desamma.
- Grad - Det är ett antal kanter som händer på ett vertex.
- Kopplad graf - Om det finns en väg från ett slumpmässigt vertex till något annat vertex, så är det grafen känt som ett anslutet diagram.
Viktiga skillnader mellan träd och graf
- I ett träd finns det bara en väg mellan några två hörn, medan ett diagram kan ha enriktad och dubbelriktad väg mellan knutpunkterna.
- I trädet finns det exakt en rotnod, och varje barn kan bara ha en förälder. I motsats till, i ett diagram finns det inget begrepp i rotnodet.
- Ett träd kan inte ha slingor och slingor medan grafen kan ha slingor och slingor.
- Grafer är mer komplicerade eftersom det kan ha loopar och självhäftningar. Däremot är träden enkla jämfört med grafen.
- Träet är korsat med hjälp av förbeställning, beställning och postorderteknik. Å andra sidan använder vi BFS (Breadth First Search) och DFS (Deepth First Search) för grafgräns.
- Ett träd kan ha n-1 kanter. Tvärtom, i diagrammet finns det inget fördefinierat antal kanter, och det beror på grafen.
- Ett träd har en hierarkisk struktur medan grafen har en nätverksmodell.
Slutsats
Grafik och träd är den icke-linjära datastrukturen som används för att lösa olika komplexa problem. Ett diagram är en grupp av kryssningar och kanter där en kant förbinder ett par kryssningar medan ett träd betraktas som ett minimalt anslutet diagram som måste vara anslutet och fri från slingor.
