arbore binar ordonat
Lemnul este o structură neliniară de stocare a datelor dinamice. Arborele este format din noduri sau noduri, care conțin câmpuri de date și indicii la alte noduri sau noduri.
Nod sau nod al unui arbore binar cuprinde un câmp de date și două câmpuri cu indicii. Câmpurile lăsate indicii pointer sunt numite (stânga) și săgețile dreapta (dreapta), deoarece acestea indică spre stânga și dreapta subarbore, respectiv. Valoarea pointer NULL este o indicație a unui subramificație gol.
Nodul rădăcină al arborelui determină punctul de intrare și câmpul pointer - la următorul nivel de asamblare. Câmpul nod foaie (frunze) conține NULL în pointerii stânga și dreapta.
Class TreeNode obiectele sunt noduri ale unui arbore binar (figura 8.1).
// pointer la stânga și la dreapta noduri copii
TreeNode (const int articol, TreeNode * lptr = NULL,
// elemente funcționale de acces la domeniile de indicii
TreeNode * Stânga () const;
TreeNode * Dreapta () const;
Inițializează câmpurile Constructor de date și indicii. Folosind un pointer nul noduri NULL sunt inițializate ca frunze. Cu indicatorul P clasa TreeNode obiect ca parametru, proiectantul adaugă P ca un copil la stânga sau la dreapta a noului nod. Elemente funcționale din stânga () și dreapta () returnează valorile câmpurilor din stânga și indicii de dreapta. Cu această clasă clientul are acces la copii nodul stânga și la dreapta lui.
// pointer întreg nod copac
TreeNode * rădăcină, * lp, * rp;
// crea frunze care conțin 20 și 30 ca date
lp = new TreeNode (20);
rp = new TreeNode (30);
// a crea o rădăcină care conține numărul 10 și doi descendenți
root = new TreeNode (10, lp, rp);
Figura 8.1 - un arbore binar
Rădăcină-> date = 50; // atribuie rădăcină 50
// constructor inițializează câmpurile de date și indicii
// valoarea NULL corespunde unui subarborele gol
TreeNode. TreeNode (const int articol, TreeNode * lp,
TreeNode * rp): date (element), la stânga (lp), dreapta (rp)
arbore binar ordonat (arbore de căutare)
arbore binar de căutare - o structură (figura 8.2), care organizează elementele prin intermediul relației "<”. Чтобы сравнить узлы дерева, подразумевают, что часть или все поле данных определено в качестве ключа и операция “<” сравнивает ключи при размещении элемента на дереве.
arbore binar de căutare este construită de următoarea regulă:
Pentru fiecare nod, valorile datelor din subarborele din stânga este mai mică decât acest nod, iar în subarborele din dreapta - mai mult.
Copacul este numit căutare, deoarece căutarea unui anumit element (o cheie), poate merge doar pe un drum destul de specific. Pornind de la rădăcină, scanat subarbore stânga, în cazul în care valoarea cheie este mai mică decât nodul curent. În caz contrar, scanarea subarborelui drept. Metoda de a crea copac vă permite să căutați calea cea mai scurtă de la rădăcină. copaci binar de căutare sunt proiectate pentru acces rapid la date. În mod ideal, arborele este echilibrat și are o înălțime și eficiența ordinii de căutare
Figura 8.2 - un arbore binar ordonat
Pentru prelucrarea datelor stocate în copac, se utilizează următoarele metode de transmitere a arborelui:
subarbore stânga, nodul subarborelui drept. metoda sau simetrice;
subarbore stânga, nodul subarborelui drept. sau metoda inversă;
dreapta sub-ganglioni din stânga subramificație. sau de la dreapta la stânga;
nodul subarborele stânga, subarborelui drept. sau de sus în jos.
Pentru a implementa algoritmi recursivi folosesc metode.
Obiectul acestei clase este un arbore ordonat binar (de exemplu - în Figura 8.2).
// clasa - un arbore binar
// elimina toate nodurile arborelui
void DeleteTree (TreeNode * t);
// obține un pointer - la nodul cu elementul și societatea mamă
TreeNode * FindNode (const int element,
Algoritmul de eliminare a nodurilor de arbori implementate DeleteTree elemente de funcție și funcția de element utilizat ClearTree. numit ca destructor și funcționarea reacoperire.
Elemente funcționale Găsiți și introduceți începe de la rădăcină și de a folosi definiția unui arbore binar de căutare. Algoritmul este pe tasta subramificație din dreapta, sau atunci când un element nou este mai mare decât nodul curent. În caz contrar, pasajul se extinde din subarbore stâng. Funcția Element Găsiți utilizează un element funcție FindNode închis. primind ca parametru cheia și susține trecerea în jos copac. Funcția returnează un pointer la nodul potrivit și indicatorul său părinte. În cazul în care un meci are loc în fașă, indicatorul părinte este NULL.
-Function Șterge elimină elementul de lemn cu un nod cheie dat. În primul rând, cu ajutorul unui element funcție este setat locul FindNode al nodului din copac și indicatorul determinat să mamă. Dacă nodul țintă este deconectat, operația de ștergere se termină.
Ștergerea unui nod din arborele necesită o serie de teste pentru a determina în cazul în care să se conecteze nodul să fie fii șterse. Subarbori trebuie să fie re-atașat în așa fel încât să se păstreze structura de arbore binar ordonat.
Funcția FindNode DNodePtr returnează un pointer la nodul D. se elimină. Al doilea indicator, PNodePtr. P identifică nodul - nodul părinte care urmează să fie șters. Funcție de ștergere este „încearcă“ pentru a găsi un înlocuitor R. nod care este atașat la mamă și, prin urmare, ia locul nodului de la distanță. Nodul de înlocuire R identificat pointer RNodePtr.
Øtergere algoritm de căutare pune în aplicare unitatea de înlocuire a celor patru cazuri, în funcție de numărul și locația fiii nodului șters. Rețineți că, dacă indicatorul părinte este NULL. se elimină și rădăcină actualizate. Această situație este luată în considerare de algoritm.
Scopul acestui laborator este de a studia algoritmi și funcții pentru a lucra cu arbore binar ordonat pe exemplul arborelui de numere întregi.
Alegerea, plasare și setarea proprietăților componente.
Codurile de clase, funcții și manipulare eveniment
Salvați modulul principal formularul numit LR_8, iar proiectul - numit PR_LR_8.
Pentru a se adapta claselor în proiect utilizat modulele care nu sunt legate de forma. Clasa pentru un nod al arborelui este declarat și definit în fișierul f_8_1 și clasă pentru un arbore binar - în modulul f_8_2. Următoarele sunt fișierele antet și fișierele de punere în aplicare aceste module.
Fișierul antet f_8_1 modul f_8_1.h (fără formă)
#include
// BinSTree depinde TreeNode
// newNode variabilă arată noul nod care este creat
// prin apel GetTreeNode atașabil și ulterior
// noul nod și a trecut ca parametri în GetTreeNode
TreeNode * newlptr, * newrptr, * newNode;
// opri trecerea recursiv atunci când arborele gol
// dacă este, se creează o copie a acestuia. altfel returnează un
// și-l închide fii
anula __fastcall RadioButton2Click (TObject * Sender);
anula __fastcall RadioButton1Click (TObject * Sender);
anula __fastcall ExitExecute (TObject * Sender);
anula __fastcall OutMemoExecute (TObject * Sender);
anula __fastcall InsertExecute (TObject * Sender);
anula __fastcall BitBtn1Click (TObject * Sender);
anula __fastcall ClearMemoExecute (TObject * Sender);
anula __fastcall ClearTreeExecute (TObject * Sender);
anula __fastcall CountLeafExecute (TObject * Sender);
anula __fastcall DepthExecute (TObject * Sender);
anula __fastcall FindExecute (TObject * Sender);
anula __fastcall DeleteExecute (TObject * Sender);
privat: // declarații de utilizator
publice: // Declarații de utilizator
__fastcall TForm1 (TComponent * proprietar);
PACHET TForm1 * Form1 extern;
Transferăm forma componentelor și să specifice valorile lor de proprietate. În plus, din pagina - LabeledEdit1 (EditLabel-> Legendă - cheie, Text - 10), ActionManager1 Managerul de acțiune și benzi ActionMainMenuBar1 meniul principal. band implicit, meniul principal ActionMainMenuBar1 situat în partea de sus, întreaga lățime a formei. Cere-i proprietatea align = alNone, pentru a da dimensiunea dorită și locul în locul potrivit.
Apoi, cu pagina insertul Win32 în forma ImageList1, de la pagina Standard - Label1 (Legendă - copac), Memo1, GroupBox1 (Caption - Formarea unui copac). Transfer Panel GroupBox1: de la pagina Standard - două butoane radio - RadioButton1 (Legendă - Verificat manual - true Enabled - true ..) Și RadioButton2 (Legendă - S-au consultat în mod automat - fals Enabled - true ..), Label2 (Legendă - numărul de noduri) Button1 (Caption - Adăugați nod), Button2 (Legendă - Eliminare nod) din exemplele de pagini - CSpinEdit1 (MAXVALUE - 100, MINVALUE - 1, Value - 10) din pagina Advanced - BitBtn1 (Legendă - START), LabeledEdit2 (EditLabel- > Legendă - număr întreg, Text - 10).
Load componentă ImageList1 icoane fldropen de fișiere. filesave. floppy. găsi. inserați. clare. șterge. arrow2d. șterge. dooropen. directry. În ActionManager1 componente Set Imagini proprietatea egal ImageList1, corelând astfel acțiunea controler cu o listă de imagini.
Adăugați la formularul folosind bara de instrumente acțiuni controler ActionManager1 ActionTollBar1, stabilit pentru ea align = alNone, Constraints-> MaxHeight = 230, Constraints-> MinHeight = 230 și puneți-l pe un formular conform ris.8.3.
Proprietatea de acțiune Button1 Butonul (Caption - Adăugați acest site Web) și Button2 (Legendă - Ștergere nod), respectiv, stoca valorile Insert și Delete.
Acțiuni privind activarea și inițializarea componentelor și manipulanții eveniment sunt listate în fișierul de punere în aplicare modulul LR_8.cpp LR_8.
Fișierul de implementare LR_8.cpp modul LR_8