Sisältö

• Vertailutaulukko
• Määritelmä puu
• Puun ominaisuudet:
• Määritelmä Kaavio
• Kaavion ominaisuudet:
• johtopäätös

Puu ja kuvaaja kuuluvat epälineaarisen tietorakenteen luokkaan, jossa puu tarjoaa erittäin hyödyllisen tavan edustaa solmujen välistä suhdetta hierarkkisessa rakenteessa ja kuvaaja seuraa verkkomallia. Puu ja kuvaaja erotetaan toisistaan ​​sillä, että puurakenteen on oltava kytkettynä eikä siinä saa koskaan olla silmukoita, kun kuvaajassa ei ole tällaisia ​​rajoituksia.

Epälineaarinen tietorakenne koostuu elementtien kokoelmasta, jotka ovat jakautuneet tasolle, mikä tarkoittaa, että elementtien välillä ei ole sellaista sekvenssiä kuin se esiintyy lineaarisessa tietorakenteessa.

1. 1. Vertailutaulukko
   2. Määritelmä
   3. Keskeiset erot
   4. johtopäätös

Vertailutaulukko

Vertailun perusteet	Puu	kaavio
polku	Vain yksi kahden kärkipisteen välillä.	Enemmän kuin yksi polku on sallittu.
Juurisolmu	Sillä on tarkalleen yksi juurisolmu.	Kaaviossa ei ole juurisolmua.
silmukat	Silmukoita ei sallita.	Kaaviossa voi olla silmukoita.
Monimutkaisuus	Vähemmän monimutkainen	Monimutkaisempi verrattuna
Poikittaistekniikat	Ennakkotilaus, tilaus ja postitilaus.	Leveys-ensimmäinen haku ja syvyys-ensimmäinen haku.
Reunojen lukumäärä	n-1 (missä n on solmujen lukumäärä)	Ei määritelty
Malli tyyppi	Hierarkkinen	verkko

Määritelmä puu

puu on rajallinen kokoelma tietoyksiköitä, joita yleensä kutsutaan solmuiksi. Kuten edellä on mainittu, puu on epälineaarinen tietorakenne, joka järjestää dataelementit lajiteltuun järjestykseen. Sitä käytetään osoittamaan hierarkkinen rakenne eri tietoelementtien välillä ja järjestämään tiedot haaroihin, jotka liittyvät informaatioon. Uuden reunan lisääminen puuhun johtaa silmukan tai piirin muodostumiseen.

Puita on useita tyyppejä, kuten binaaripuu, binaarinen hakupuu, AVL-puu, kierteitetty binaaripuu, B-puu jne. Tietojen pakkaaminen, tiedostojen tallennus, aritmeettisen lausekkeen manipulointi ja pelipuut ovat joitain puun sovelluksista. tietorakenne.

Puun ominaisuudet:

• Puun yläosassa on nimetty solmu, joka tunnetaan puun juurena.
• Jäljelle jäävät dataelementit on jaettu erillisiin osajoukkoihin, joihin viitataan osapuuna.
• Puun korkeus laajenee pohjaa kohti.
• Puun on oltava kytkettynä, mikä tarkoittaa, että tiellä on oltava polku yhdestä juurista muihin solmuihin.
• Se ei sisällä silmukoita.
• Puussa on n-1 reunaa.

Puihin liittyy useita termejä, kuten terminaalisolmu, reuna, taso, aste, syvyys, metsä jne. Näiden termien joukossa joitain niistä kuvataan alla.

• Reuna - Linja, joka yhdistää kaksi solmua.
• Taso - Puu on jaettu tasoille siten, että juurisolmu on tasolla 0. Sitten sen välittömät lapset ovat tasolla 1 ja sen välittömät lapset ovat tasolla 2 ja niin edelleen pääte- tai lehtisolmuun asti.
• aste - Se on solmun alapuiden lukumäärä tietyssä puussa.
• Syvyys - Se on tietyn puun minkä tahansa solmun enimmäistaso ja tunnetaan myös nimellä korkeus.
• Terminaalisolmu - Korkeimman tason solmu on päätesolmu, kun taas muita solmuja paitsi pääte- ja juurisolmuja kutsutaan ei-päätelaitteiksi.

Määritelmä Kaavio

kaavio on myös matemaattinen epälineaarinen tietorakenne, joka voi edustaa erilaisia ​​fyysisiä rakenteita. Se koostuu ryhmästä huipuja (tai solmuja) ja sarjasta reunoja, jotka yhdistävät nämä kaksi kärkeä. Kaaviossa olevat huiput esitetään pisteinä tai ympyröinä ja reunat esitetään kaareina tai viivaosina. Reunaa edustaa E (v, w), missä v ja w ovat kärkiparit. Reunan poistaminen piiristä tai kytketystä kuvaajasta luo alakuvion, joka on puu.

Kaaviot luokitellaan eri luokkiin, kuten suunnatut, ei suunnatut, kytketyt, kytkemättömät, yksinkertaiset ja moni kuvaajat. Tietokoneverkko, siirtojärjestelmä, sosiaalisen verkoston kuvaaja, sähköpiirit ja projektisuunnittelu ovat joitain graafin tietorakenteen sovelluksia. Sitä käytetään myös hallintotekniikassa nimeltään PERT (ohjelman arviointi - ja arviointitekniikka) ja CPM (kriittisen polun menetelmä), jossa graafin rakennetta analysoidaan.

Kaavion ominaisuudet:

• Kaaviossa oleva kärki voidaan yhdistää mihin tahansa määrään muita huippuja reunoilla.
• Reuna voidaan suunnata tai suuntaa.
• Reuna voidaan painottaa.

Käytämme myös kuvaajassa erilaisia ​​termejä, kuten vierekkäiset vertikaalit, polku, sykli, aste, kytketty kuvaaja, täydellinen kuvaaja, painotettu kuvaaja jne. Ymmärretään joitain näistä termeistä.

• Vierekkäiset huiput - Kärkipiste a on kärkipisteen b vieressä, jos siinä on reuna (a, b) tai (b, a).
• polku - Reitti satunnaisesta kärkipisteestä w on vierekkäinen kärkipiste.
• sykli - Se on polku, jolla ensimmäinen ja viimeinen kärki ovat samat.
• aste - Se on useita reunoja, jotka esiintyvät kärjessä.
• Yhdistetty kaavio - Jos satunnaisesta kärkipisteestä löytyy polku mihinkään muuhun kärkeen, kyseistä kuvaajaa kutsutaan kytketyksi kuvaajaksi.

1. Puussa on vain yksi polku minkä tahansa kahden kärkipisteen välillä, kun taas kuvaajalla voi olla yksisuuntainen ja kaksisuuntainen polku solmujen välillä.
2. Puussa on tarkalleen yksi juurisolmu, ja jokaisella lapsella voi olla vain yksi vanhemmista. Vastaavasti kuvaajassa ei ole juurisolmun käsitettä.
3. Puussa ei voi olla silmukoita ja itsesilmukoita, kun taas kaaviossa voi olla silmukoita ja itsesilmukoita.
4. Kaaviot ovat monimutkaisempia, koska siinä voi olla silmukoita ja itsesilmukoita. Sen sijaan puut ovat yksinkertaisia ​​kuvaajaan verrattuna.
5. Puuta kuljetetaan ennakkotilauksen, tilauksen ja tilauksen jälkeisillä tekniikoilla. Toisaalta graafin liikkumiseen käytämme BFS (Leveys ensimmäinen haku) ja DFS (syvyys ensimmäinen haku).
6. Puussa voi olla n-1 reunaa. Päinvastoin, kuvaajassa ei ole ennalta määritettyä reunojen lukumäärää, ja se riippuu kuvaajasta.
7. Puulla on hierarkkinen rakenne, kun taas kuvaajalla on verkkomalli.

johtopäätös

Graafi ja puu ovat epälineaarinen tietorakenne, jota käytetään erilaisten monimutkaisten ongelmien ratkaisemiseksi. Kaavio on ryhmä huippuja ja reunoja, joissa reuna yhdistää kärkiparin, kun taas puuta pidetään minimaalisesti kytkettynä kuvaajana, jonka on oltava kytkettynä ja vapaa silmukoista.