Laboratóriumi munka №8
bináris fák
Célkitűzés: Annak vizsgálata módszerek hatékony tárolása és feldolgozása az információk a példa bináris fák.
áttekintés
Bináris fa - a dinamikus adatok hierarchikus szerkezet, amely a csomópontok és az azokat összekötő ívek. Minden csomópont, egy kivételével, pontosan egy ív. Ez az egyetlen egység az úgynevezett gyökér a fa. Minden fa csomóponthoz véges számú egyes fák nevű részfákat. Az ábra azt mutatja, egy fa, amelynek csomópontok a szimbólumok: Y csúcsok alatt közvetlenül elhelyezkedő felső X, úgynevezett közvetlen gyermek X, X és a vertex nevezzük őse Y. Ha a csomópont nem rendelkezik leszármazottai, ez az úgynevezett egy levél, ha van, akkor a nevezett belső Apex . Például, vertex D, E közvetlen leszármazottai a B csúcs; vertex H, I, J a levelek. Nyilvánvaló, hogy a kapcsolatra van szükség, hogy leírja a fa. Leírjuk egy bináris fa, mint a Record típusú szerkezet, amely legalább két területen - mutató balra és jobbra részfa, és egy adat területen, mint például Integer típus: alapműveletek a fán, hogy alapvető műveleteket a fák felett: • belépési pont a fa; • bejárás a fa; • eltávolítását egy elemet a fa.
Beírása eleme a fa. fa, amelynek elemei bemeneti létrehozni és kijelző és a billentyűzet is szerves típusát. És minden csúcsa a fák tetején a bal legyen a számos kisebb, de jobb mint a szám, amely tárolja a tetején. Egy ilyen fa nevezzük fa keresést. Nézzük leírására irányuló eljárás egy fa egy új csúcsot. Behelyezésekor a hegyét behelyezzük a fa, vagy részfáját mivel a meglévő felső vagy egyetlen csomópont a fa. Ezért mind a bal és jobb kapcsolatot egy új csúcs egyenlőnek kell lennie nulla. Mikor a fa üres, a továbbított érték formájában referenciaparaméternek egyenlő nulla. Ebben az esetben meg kell változtatni úgy, hogy rámutat arra, hogy az új csomópont, amely beépült, mint a gyökér. Amikor behelyezi a második elem továbbítani a főprogram anód lehetőség már nem lesz egyenlő a nulla, és szükség van annak eldöntését, hogy egy részfa kell beszúrni új csúcs. Nyomtató fa elemekkel. Leírják a folyamatot kimeneti értékek az elemek egy bináris fa a képernyőn. Ehhez el kell végezni egy teljes bejárást a fa. Mozgás a fa egyedi csúcsokat látogatott egy bizonyos sorrendben. Nyomtató bináris fa lehet végezni rekurzív végző minden csúcsa háromból: • A kimenet számát tárolja a csomópont; • bypass bal részfa; • megkerülve a jobb részfa. Az, hogy a végrehajtás ezen intézkedések meghatározzák, hogyan bejárás. megkerülésének módszerek: • bypass vonal (fentről lefelé); • egyensúlyban bypass (balról jobbra); • megkerülve fordított (alulról felfelé). szimmetrikus kimenő fa eljárás a következő: eltávolítjuk a fa. Az azonnali eltávolítását egy elemet rendezett fa végre egyszerűen, ha ez a csomópont a végső: vagy jön csak az egyik él: Meg kell változtatni a kapcsolatot az előző csúcsok. Ha eltávolítjuk a felső levelek két ág, meg kell találni a megfelelő fa tetejére, amelyet fel lehetne beilleszteni a helyére egy levehető tetején. Ebben az esetben a bejegyzést el kell távolítani kell cserélni akár a jobb szélső eleme bal részfa, vagy a bal oldali legszélső eleme a jobb részfa. Ilyen elemek lehetnek egynél több leszármazottja. Hagyja, hogy a következő szerkezetű meghatározása: Kiegészítő rutin Del hivatkozva csak a harmadik esetben. Ez „lefelé” mentén jobb szélső ága a bal részfa az eltávolított csomópont Q ^ majd lecseréli az adatokat (adatmező) a megfelelő értékek a Q ^ jobb szélső csomópont R ^ a bal részfa, majd R ^ tud megszökni. Az ábra adott kezdeti fa (a), amely egymás után eltávolítja csomópontok értékek 13, 15, 5, 10. Az így kapott fák ábrán mutatjuk be. b - e.
tesztkérdések
1. Mi az a rekurzív algoritmus? 2. Milyen részei épített meghatározása egy rekurzív algoritmust? 3. Mi szükséges bármilyen rekurzív algoritmus? 4. Van-e lehetőség, hogy cserélje ki a rekurzió iteráció? Lehetséges, hogy cserélje iteráció rekurzió? 5. Mi az az elv, a dinamikus struktúra a „fa”? 6. Sorolja fel a hasonlóságokat és különbségeket dinamikus struktúrák, mint a „lineáris lista”, „stack”, „fa”. 7. Sorolja fel a struktúrákat is képviselteti magát egy fa, amely előfordul a mindennapi életben. 8. Fejezd be a mondatot: "List - egy fa ...".
Az összes probléma hallgatólagos bináris fák poiska.1. Írj egy rekurzív függvény numerikus számít az összeget a fa elemekkel. 2. Írj egy függvényt, amely megállapítja a legnagyobb eleme a fa. 3. Írj egy függvényt, amely megállapítja a legkisebb eleme a fa. 4. Írj egy eljárás, amely eltávolítja a fát a páros elemeket. 5. Írj egy rekurzív eljárás, amely meghatározza az előfordulások számát egy adott elem a fán. 6. Írj egy rekurzív eljárás, amely kiírja az elemeket a levelek a fa. 7. Írjon egy eljárást, amely megjeleníti a fa mutatja a mélység a behúzás csomópontok a bal szélén a képernyőn. Például egy fa jelenik meg az alábbiak szerint: 1. csoport 2. Az 1. Természetesen PMI-csoport 2 3 4 csoportban természetesen 8. Írjon rekurzív függvény, amely meghatározza a mélység a megadott elemet a fa, és a visszatérési értéke -1, ha nincs ilyen elem. 9. Írjon rutin, hogy a nyomatok (egyszer) a fa tetején. 10. Írja olyan eljárás, amely, adott n megszámlálja az összes csomópont az n mélységű a megadott fa. 11. Írj egy rutin, hogy megtalálja a fa mélységét. 12. Szűrés tömb belefoglalva egy fa elemek és a másolat rendezve adatokat vissza A. 13. Adott szavak sorozatát. Annak megállapításához, a előfordulási gyakorisága minden szót a sorban. Megjegyzés. A probléma megoldása érdekében minden szót felnézett a fa, amely a kezdetben üres. Ha a szó megtalálható, a gróf a saját események eggyel megnöveljük, ha nem, a szó benne van a fa egy számláló értékét. back Home