Binary megrendelt fa
A fa egy nemlineáris dinamikus adattárolási struktúrája. A fa áll csomópontok vagy csúcsok, amelyek adatmezők és a mutatók más csomópontokhoz vagy csúcsot.
Node vagy csúcspont egy bináris fa tartalmaz egy adatmezőt és a két területen mutató. Hagyott mezők mutató pointereket nevezik (balra) és jobb nyilak (jobbra), mivel ezek pont a bal és a jobb részfa, ill. NULL pointer értéke azt jelzi, egy üres részfa.
A gyökér csomópont a fa határozza meg a belépési pont és a mutató mező - a következő szint a szerelvény. A levél csomópont (levél) mező NULL a bal és a jobb mutatók.
Osztályú TreeNode tárgyak csomópontok egy bináris fa (8.1 ábra).
// mutató balra és jobbra gyermek csomópontok
TreeNode (const int elemet, TreeNode * lptr = NULL,
// függvény elemei hozzáférés területén a mutatók
TreeNode * Bal () const;
TreeNode * Jobb () const;
Constructor inicializálja a mezőket az adatok és mutatók. Egy null pointer NULL csomópont megindítjuk a levelek. A mutató P TreeNode objektumot paraméterként, a tervező hozzáteszi P a bal vagy a jobb gyermeke az új csomópont. Funkció elemek Bal () és Jobb () függvény értékeit mezők a bal és a jobb mutatók. Ezzel osztály az ügyfél hozzáfér a bal és a jobb csomópont gyermekei.
// pointerek integer csomópontja
TreeNode * root * lp * rp;
// Létrehozunk levelek, amelyek 20 és 30, mint egy adat
lp = új TreeNode (20);
rp = új TreeNode (30);
// létrehoz egy gyökér, amely a 10-es számú, valamint két leszármazottai
root = új TreeNode (10, lp, rp);
8.1 ábra - egy bináris fa
root-> adatok = 50; // rendelni a gyökér 50
// konstruktor inicializálja az adatmezőket és indexek
// NULL érték megfelel egy üres részfa
TreeNode. TreeNode (const int elemet, TreeNode * lp,
TreeNode * rp): adat (db), bal (lp), jobbra (rp)
Binary megrendelt fát (keresési fa)
Bináris keresési fa - egy szerkezet (8.2 ábra), amely rendezi az elemek révén a kapcsolat "<”. Чтобы сравнить узлы дерева, подразумевают, что часть или все поле данных определено в качестве ключа и операция “<” сравнивает ключи при размещении элемента на дереве.
Binary keresési fa épül a következő szabály szerint:
Minden egyes csomópont, az adatok értéke a bal részfa ennél kevesebb csomópontot, majd a jobb oldali részfa - több.
A fa az úgynevezett kereső, mert a keresést egy bizonyos eleme (a kulcs) csak megy egy meglehetősen sajátos módon. Kezdve a gyökér, szkennelt bal részfa, ha a kulcs-érték kevesebb, mint a jelenlegi csomópontot. Egyébként szkennelés a jobb részfa. A módszer megteremti a fa lehetővé teszi a keresést a legrövidebb út a gyökér. Binary keresési fákat célja a gyors hozzáférést az adatokhoz. Ideális esetben a fa kiegyensúlyozott és magassága és hatékonyságának keresési sorrend
8.2 ábra - egy bináris fa rendelhető
Mert tárolt adatok feldolgozása a fa, az alábbi módszerek átviteli fa használjuk:
bal részfa jobb részfa csomópontot. eljárást vagy a szimmetrikus;
bal részfa jobb részfa csomópontot. vagy fordított módszer;
jobb al-nyirokcsomó a bal részfa. vagy jobbról balra;
node a bal részfa jobb részfa. vagy felülről lefelé.
Megvalósítása rekurzív algoritmusok módszereket alkalmaz.
A cél ennek osztály egy bináris rendezett fa (például - a 8.2 ábra).
// osztály - egy bináris fa
// távolítsa el az összes fa csomópontjait
void DeleteTree (TreeNode * t);
// kap egy mutatót - a csomópontot a tételt, és a szülő
TreeNode * FindNode (const int elemet,
Algoritmus eltávolítására facsomópontok végrehajtott elemek funkciója DeleteTree és használt-elem funkciója ClearTree. hívják, mint a destructor és túlterhelt hozzárendelés működését.
Funkció elemek Keressen és Insert indul a gyökér, és használja a meghatározása bináris kereső fába. Az algoritmus a jobb részfa, kulcs, vagy amikor egy új elem nagyobb, mint az aktuális csomópont. Ellenkező esetben, a folyosón húzódik a bal részfa. Funkció Element Keresse használ zárt FindNode funkciójú elem. részesülő, mint a paraméter a kulcsot és végrehajtja a folyosón le a fáról. A függvény egy mutatót a párosított csomópont és az eredeti mutatója. Találat esetén a bajt, a szülő mutató értéke NULL.
Funkció-Delete törli az elem a fa egy adott kulcs csomópontot. Először egy függvény-elem úgy van beállítva FindNode helyett a fában, és a meghatározott mutatót a szülő. Ha a cél csomópont offline, a törlési művelet befejeződik.
Törlése csomópontot a fa van szükség egy tesztsorozatot meghatározni, ahol csatlakozni a törlendő csomópontra fia. Részfák kell újra rögzíteni oly módon, hogy megőrizzék a szerkezet a bináris megrendelt fát.
FindNode DNodePtr függvény visszaad egy pointert a csomópont D. kell hagyni. A második mutató, PNodePtr. P azonosítja a csomópont - a szülő csomópont törölni kell. Törlés funkció „próbál” találni csere csomópont R., amely kapcsolódik az eredeti, ezért helyét veszi át a távoli csomópont. A helyettesítő csomópont R azonosított pointer RNodePtr.
Funkció törlése keresési algoritmus valósítja meg a cserekészüléket a négy esetben, attól függően, hogy a számát és helyét a fia a törölt csomópont. Vegye figyelembe, hogy ha a szülő mutató értéke NULL. törlésre kerül, és naprakészen gyökér. Ezt a helyzetet figyelembe véve az algoritmus.
A cél ebben a laborban, hogy tanulmányozza algoritmusok és funkciók dolgozni bináris megrendelt fa a példa a fa egész számok.
Választás, elhelyezés és beállítás komponens tulajdonságait.
Kódok osztályok, függvények és eseménykezelőkkel
Mentsd meg a fő formája modul neve LR_8, és a projekt - elemzi PR_LR_8.
Elhelyezésére az osztályok a projektben használt modulok, amelyek nem kapcsolódnak a formában. Osztály egy csomópont a fa bejelentett és megadott f_8_1 fájlt, és osztály egy bináris fa - a f_8_2 modult. A következő a header fájlokra végrehajtási ezek a modulok.
Fejlécfájlba f_8_1.h modul f_8_1 (forma nélkül)
#include
// BinSTree függ TreeNode
// változó newnode jelzi az új csomópont jön létre
// keresztül Hívás GetTreeNode csatlakoztatható, és ezt követően
// Az új csomópont és paraméterként adja át GetTreeNode
TreeNode * newlptr * newrptr * newnode;
// állítsa le a rekurzív átjárót, amikor az üres fa
// ha igen, akkor létrehoz egy példányt belőle. egyébként vissza
// és leteszi őt fiai
érvényteleníti __fastcall RadioButton2Click (TObject * feladó);
érvényteleníti __fastcall RadioButton1Click (TObject * feladó);
érvényteleníti __fastcall ExitExecute (TObject * feladó);
érvényteleníti __fastcall OutMemoExecute (TObject * feladó);
érvényteleníti __fastcall InsertExecute (TObject * feladó);
érvényteleníti __fastcall BitBtn1Click (TObject * feladó);
érvényteleníti __fastcall ClearMemoExecute (TObject * feladó);
érvényteleníti __fastcall ClearTreeExecute (TObject * feladó);
érvényteleníti __fastcall CountLeafExecute (TObject * feladó);
érvényteleníti __fastcall DepthExecute (TObject * feladó);
érvényteleníti __fastcall FindExecute (TObject * feladó);
érvényteleníti __fastcall DeleteExecute (TObject * feladó);
private: // felhasználó nyilatkozatok
Nyilvános: // felhasználó nyilatkozatok
__fastcall TForm1 (TComponent * Képviselő);
extern CSOMAG TForm1 * Form1;
Mi át az alak a komponensek és meghatározza azok ingatlanok értéke. Ezen túlmenően, az oldalon - LabeledEdit1 (EditLabel-> Caption - Kulcs, Text - 10), ActionManager1 Action menedzsere és szalag ActionMainMenuBar1 főmenübe. Alapértelmezett zenekar ActionMainMenuBar1 főmenü tetején található, teljes szélességében formájában. Kérdezd meg, ingatlan align = alNone, hogy ez a kívánt méretet, és helyezzük a megfelelő helyre.
Aztán, a Win32 oldal betét formájában ImageList1, az oldalról Standard - Label1 (Caption - FA), Memo1, GroupBox1 (Caption - Formation egy fa). Panel GroupBox1 átutalás: az oldalról Standard - két rádió gombjai - RadioButton1 (Caption - manuálisan Checked - igaz Enabled - igaz ..) És RadioButton2 (Caption - automatikusan ellenőrzésre - hamis Enabled - igaz ..), Label2 (Caption - a csomópontok száma) button1 (Caption - Add node), Button2 (Caption - Vegye node) az oldalról példák - CSpinEdit1 (MAXVALUE - 100, MINVALUE - 1, érték - 10) a oldal Advanced - BitBtn1 (Caption - START), LabeledEdit2 (EditLabel- > Caption - egész szám, szöveg - 10).
Load alkatrész ImageList1 fldropen ikonok fájlokat. filesave. floppy. találni. helyezze. világos. törölni. arrow2d. törli. dooropen. directry. A ActionManager1 komponensek beállítása Képek tulajdon egyenlő ImageList1, ezáltal összekötve a vezérlő intézkedéseket a képek listáját.
Hozzáadás űrlapot szabályozó intézkedések eszköztár ActionManager1 ActionTollBar1, meg érte align = alNone, Constraints-> MaxHeight = 230, Constraints-> MinHeight = 230, és helyezze a megfelelő formában ris.8.3.
Az ingatlan Action Button1 gomb (Caption - Add ezt a webhelyet) és Button2 (Caption - Csomópont törlése), illetve tárolja az értékeket Beszúrás és Törlés.
Műveletek aktiválása és inicializálása alkatrészek és eseménykezelők fájlban felsorolt végrehajtási LR_8.cpp LR_8 modult.
A végrehajtás fájl LR_8.cpp modul LR_8