Share
Până acum, am analizat structurile de date care organizează datele într-un mod liniar. Listele legate conțin date dintr-un singur nod de pornire la un singur nod terminator. Arrays dețin date în blocuri concomitente, unidimensionale.
În această secțiune, vom vedea cum adăugarea unei alte dimensiuni ne va permite să introducem o nouă structură de date: arborele. Mai exact, vom analiza un tip de copac cunoscut ca arbore binar de căutare. Arborele de căutare binar are structura generală a copacilor și aplică un set de reguli simple care definesc structura copacului.
Înainte de a afla despre aceste reguli, să învățăm ce este un copac.
Un arbore este o structură de date în care fiecare nod are zero sau mai mulți copii. De exemplu, am putea avea un copac ca acesta:
Structura arborelui organizatoric În acest arbore, putem vedea structura organizatorică a unei afaceri. Blocurile reprezintă persoane sau diviziuni în cadrul companiei, iar liniile reprezintă relații de raportare. Un arbore este un mod foarte eficient și logic de a prezenta și de a stoca aceste informații.
Arborele prezentat în figura precedentă este un arbore general. Acesta reprezintă relațiile părinte / copil, dar nu există reguli pentru structură. CEO-ul are un raport direct, dar ar putea avea la fel de ușor cu două sau două. În figură, Vânzările sunt afișate în partea stângă a site-ului Marketing, dar ordonarea nu are sens. De fapt, singura constrângere observabilă este că fiecare nod are cel mult un părinte (și nodul superior, Consiliul de Administrație, nu are părinte).
Un arbore binar de căutare utilizează aceeași structură de bază ca arborele general prezentat în ultima figură, dar cu adăugarea câtorva reguli. Aceste reguli sunt:
Să ne uităm la un copac construit folosind aceste reguli:
Arborele de căutare binară Observați cum sunt impuse constrângerile specificate în diagramă. Fiecare valoare din stânga nodului rădăcină (opt) are o valoare mai mică de opt și fiecare valoare din dreapta este mai mare sau egală cu nodul rădăcină. Această regulă se aplică recursiv la fiecare nod de-a lungul drumului.
Având în vedere acest copac, să ne gândim la pașii care au urmat să-l construim. Când procesul a început, arborele a fost gol și apoi a fost adăugată o valoare, opt. Deoarece a fost prima valoare adăugată, a fost pusă în poziția rădăcină (ultimul părinte).
Nu știm exact ordinea în care au fost adăugate restul nodurilor, dar voi prezenta o cale posibilă. Valorile vor fi adăugate utilizând o metodă numită Adăuga care acceptă valoarea.
Arbore BinaryTree = nou BinaryTree (); tree.Add (8); tree.Add (4); tree.Add (2); tree.Add (3); tree.Add (10); tree.Add (6); tree.Add (7);
Să trecem prin primele elemente.
Opt a fost adăugat mai întâi și a devenit rădăcina. Apoi, patru au fost adăugate. Din moment ce patru sunt mai puțin de opt, trebuie să meargă la stânga a opt după regulă numărul doi. Din moment ce opt nu are nici un copil în stânga sa, patru devin copilul stâng imediat al opt.
Două sunt adăugate în continuare. două sunt mai puțin de opt, așa că merge la stânga. Există deja un nod în partea stângă a opt, astfel încât logica de comparație este efectuată din nou. două sunt mai puțin de patru, iar patru nu au un copil stâng, așa că doi devin copilul de stânga al patrulea.
Trei se adaugă în continuare și se duce spre stânga a opt și patru. În comparație cu cele două noduri, este mai mare, deci trei sunt adăugate la dreapta a două ca regulă numărul trei.
Acest ciclu de comparare a valorilor la fiecare nod și apoi verificarea fiecărui copil peste și peste până când se găsește slotul corespunzător se repetă pentru fiecare valoare până când este creată structura de copac finală.
BinaryTreeNode reprezintă un singur nod din arbore. Conține referințe la copiii din stânga și dreapta (nulă dacă nu există), valoarea nodului și IComparable.CompareTo care permite compararea valorilor nodurilor pentru a determina dacă valoarea ar trebui să meargă la stânga sau la dreapta nodului curent. Acesta este întregul BinaryTreeNode clasa - după cum puteți vedea, este foarte simplă.
clasa BinaryTreeNode: IComparabile unde TNode: IComparable public BinaryTreeNode (valoare TNode) Value = value; public BinaryTreeNode Stânga get; a stabilit; public BinaryTreeNode Drept get; a stabilit; public TNode Value get; set privat; /// /// Compară nodul curent cu valoarea furnizată. /// /// Valoarea nodului de comparat cu /// 1 dacă valoarea instanței este mai mare decât /// valoarea furnizată, -1 dacă este mai mică sau 0 este egală. public int int CompareTo (alt TNode) return Value.CompareTo (altul);
BinaryTree clasa oferă metodele de bază de care aveți nevoie pentru a manipula arborele: Adăuga, Elimina, A Conține metodă pentru a determina dacă un element există în arbore, mai multe metode de traversare și enumerare (acestea sunt metode care ne permit să enumerăm nodurile din arbore în diferite ordine bine definite) și normală Numara și clar metode.
Pentru a inițializa arborele, există a BinaryTreeNode referință care reprezintă nodul cap (rădăcină) al copacului și există un număr întreg care ține evidența numărului de elemente din arbore.
public class BinaryTree: IEnumerable în cazul în care T: IComparable private BinaryTreeNode _head; private int _count; public void Adăugați (valoarea T) arunca noua NotImplementedException (); bool public Conține (valoarea T) arunca noua NotImplementedException (); bool public Eliminare (valoare T) arunca noua NotImplementedException (); public void PreOrderTraversal (Acțiune de acțiune) arunca noua NotImplementedException (); public void PostOrderTraversal (acțiunea de acțiune) throw new NotImplementedException (); public void InOrderTraversal (Acțiune de acțiune) arunca noua NotImplementedException (); public IEnumerator GetEnumerator () arunca noua NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () arunca noua NotImplementedException (); void public Clear () arunca noua NotImplementedException (); public int Count get;
| Comportament | Adaugă valoarea furnizată la locația corectă din arbore. |
| Performanţă | O (log n) în medie; O (n) în cel mai rău caz. |
Adăugarea unui nod la arbore nu este teribil de complexă și este chiar mai ușoară atunci când problema este simplificată într-un algoritm recursiv. Există două cazuri care trebuie luate în considerare:
În primul caz, pur și simplu alocăm noul nod și îl adăugăm copacului. În cel de-al doilea caz, comparăm valoarea cu valoarea nodului. Dacă valoarea pe care încercăm să o adăugăm este mai mică decât valoarea nodului, algoritmul se repetă pentru copilul stâng al nodului. În caz contrar, se repetă pentru copilul potrivit al nodului.
public void Adăugați (valoarea T) // Cazul 1: Arborele este gol. Alocați capul. dacă (_head == null) _head = BinaryTreeNode (valoare); // Cazul 2: Arborele nu este gol, deci recursiv // găsiți locul potrivit pentru a introduce nodul. altceva AddTo (_head, value); _count ++; // Algoritmul adăugării recursive. private void AddTo (nod BinaryTreeNode, valoare T) // Cazul 1: Valoarea este mai mică decât valoarea curentă a nodului dacă (value.CompareTo (node.Value) < 0) // If there is no left child, make this the new left, if (node.Left == null) node.Left = new BinaryTreeNode(value); else // else add it to the left node. AddTo(node.Left, value); // Case 2: Value is equal to or greater than the current value. else // If there is no right, add it to the right, if (node.Right == null) node.Right = new BinaryTreeNode(value); else // else add it to the right node. AddTo(node.Right, value);
| Comportament | Îndepărtează prima nore găsită cu valoarea indicată. |
| Performanţă | O (log n) în medie; O (n) în cel mai rău caz. |
Eliminarea unei valori din arbore este o operație simplă conceptuală care devine surprinzător de complexă în practică.
La un nivel înalt, operațiunea este simplă:
Primul pas este simplu și, după cum vom vedea, se realizează utilizând același mecanism pe care îl folosește metoda Contains. Odată identificat nodul care urmează să fie eliminat, operația poate lua una din cele trei căi dictate de starea copacului în jurul nodului care urmează să fie eliminat. Cele trei stări sunt descrise în următoarele trei cazuri.
Cazul unu: Nodul care trebuie eliminat nu are un copil potrivit.
Cazul 1 Nodul care trebuie eliminat nu are un copil potrivit În acest caz, operația de mutare poate pur și simplu să mute copilul din stânga, dacă există unul, în locul nodului îndepărtat. Arborele rezultat ar arăta astfel:
Cazul 1 - Starea arborelui după îndepărtare Cazul doi: Nodul care urmează a fi eliminat are un copil care, la rândul său, nu are un copil la stânga.
Cazul doi Nodul care urmează a fi eliminat are un copil care nu are copil de stânga În acest caz, vrem să mutăm copilul drept (șase) în locul nodului eliminat. Arborele rezultat va arata astfel:
Starea copacului după îndepărtare Cazul trei: Nodul care urmează să fie eliminat are un copil care, la rândul său, are un copil stâng.
Cazul 3 - Nodul care urmează a fi eliminat are un copil care are un copil stâng În acest caz, copilul cel mai stâng al copilului drept al nodului eliminat trebuie plasat în slotul nodului eliminat.
Să facem un minut să ne gândim de ce este adevărat. Există două fapte pe care le cunoaștem despre sub-copaci, începând cu nodul care este eliminat (de exemplu, sub-arborele a cărui rădăcină este nodul cu valoarea cinci).
Trebuie să plasăm o valoare în slotul nodului îndepărtat, care este mai mic sau egal cu fiecare nod din partea dreaptă. Pentru a face acest lucru, trebuie să obținem cea mai mică valoare pe partea dreaptă. Prin urmare, avem nevoie de nodul cel mai stâng al copilului drept.
După eliminarea nodului, arborele va arăta astfel:
Cazul 3 - Arborele după îndepărtarea nodului Acum, că înțelegem cele trei scenarii de eliminare, să examinăm codul pentru a face acest lucru.
Un lucru de remarcat: The FindWithParent (vezi secțiunea Conține) returnează nodul de eliminat, precum și părintele nodului care este eliminat. Acest lucru se întâmplă deoarece atunci când nodul este eliminat, trebuie să actualizăm parintele Stânga sau Dreapta proprietate pentru a indica noul nod.
Am putea evita acest lucru dacă toate nodurile au ținut o referință la părintele lor, dar acest lucru ar introduce costuri de memorie per-nod și cheltuieli de contabilitate necesare numai în acest caz.
bool public Eliminare (valoare T) BinaryTreeNode curent, părinte; // Găsiți nodul pe care doriți să-l eliminați. curent = FindWithParent (valoare, parent); dacă (curent == null) return false; _numara--; // Cazul 1: Dacă curentul nu are un copil corect, stânga curentului înlocuiește curentul. dacă (curent.Right == null) if (parent == null) _head = current.Left; altceva int result = parent.CompareTo (current.Value); dacă (rezultat> 0) // Dacă valoarea parentală este mai mare decât valoarea curentă, // face copilul stâng actual să fie un copil stâng al părintelui. parent.Left = current.Left; altfel dacă (rezultat < 0) // If parent value is less than current value, // make the current left child a right child of parent. parent.Right = current.Left; // Case 2: If current's right child has no left child, current's right child // replaces current. else if (current.Right.Left == null) current.Right.Left = current.Left; if (parent == null) _head = current.Right; else int result = parent.CompareTo(current.Value); if (result > 0) // Dacă valoarea parentală este mai mare decât valoarea curentă, // face copilul drept drept un copil stâng al părintelui. parent.Left = curent. altfel dacă (rezultat < 0) // If parent value is less than current value, // make the current right child a right child of parent. parent.Right = current.Right; // Case 3: If current's right child has a left child, replace current with current's // right child's left-most child. else // Find the right's left-most child. BinaryTreeNode leftmost = current.Right.Left; BinaryTreeNode leftmostParent = current.Right; while (leftmost.Left != null) leftmostParent = leftmost; leftmost = leftmost.Left; // The parent's left subtree becomes the leftmost's right subtree. leftmostParent.Left = leftmost.Right; // Assign leftmost's left and right to current's left and right children. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) _head = leftmost; else int result = parent.CompareTo(current.Value); if (result > 0) // Dacă valoarea părintească este mai mare decât valoarea curentă, // face din stânga copilul părintelui din stânga. parent.Left = stânga; altfel dacă (rezultat < 0) // If parent value is less than current value, // make leftmost the parent's right child. parent.Right = leftmost; return true;
| Comportament | Returnează adevărat dacă arborele conține valoarea furnizată. În caz contrar, se întoarce false. |
| Performanţă | O (log n) în medie; O (n) în cel mai rău caz. |
Conține se îndepărtează FindWithParent, care efectuează un algoritm simplu de copaci care efectuează următorii pași, începând de la nodul principal:
De cand Conține returnează a boolean, valoarea returnată este determinată de dacă FindWithParent returnează un non-null BinaryTreeNode (adevărat) sau una nulă (falsă).
FindWithParent metoda este folosită și de metoda Remove. Parametrul out, părinte, nu este utilizat de către Conține.
bool public Contains (valoarea T) // Să se deplaseze la funcția helper search node. BinaryTreeNode părinte; returnează FindWithParent (valoare, părinte parentală)! = null; /// /// Găsește și returnează primul nod care conține valoarea specificată. Dacă valoarea /// nu este găsită, ea se întoarce nulă. De asemenea, returnează părintele nodului găsit (sau null) /// care este utilizat în Eliminare. /// privat BinaryTreeNode FindWithParent (valoare T, ieșire BinaryTreeNode părinte) // Acum încercați să găsiți date în arbore. BinaryTreeNode curent = _head; părinte = null; // În timp ce nu avem o potrivire ... în timp ce (curent! = Null) int result = current.CompareTo (value); dacă (rezultat> 0) // Dacă valoarea este mai mică decât cea curentă, mergeți la stânga. părinte = curent; curent = curent. altfel dacă (rezultat < 0) // If the value is more than current, go right. parent = current; current = current.Right; else // We have a match! break; return current;
| Comportament | Returnează numărul de valori din arbore (0 dacă este gol). |
| Performanţă | O (1) |
Câmpul de numărare este incrementat de Adăuga metodă și decrementată de către Elimina metodă.
public int Număr get return _count;
| Comportament | Îndepărtează toate nodurile din arbore. |
| Performanţă | O (1) |
public void Clear () _head = null; _count = 0;
Transversalele arborilor sunt algoritmi care permit prelucrarea fiecărei valori în arbore într-o ordine bine definită. Pentru fiecare algoritm discutat, următorul arbore va fi folosit ca intrare de eșantion.
Exemplele care urmează o acceptă pe toate Acțiune parametru. Acest parametru definește acțiunea care va fi aplicată fiecărui nod așa cum este procesată de traversal.
Secțiunea de comandă pentru fiecare traversal va indica ordinea în care următorul arbore va traversa.
Arborele de eșantionare pentru rezultatele comenzii traversale | Comportament | Efectuează acțiunea furnizată pentru fiecare valoare în preordonare (vezi descrierea care urmează). |
| Performanţă | Pe) |
| Ordin | 4, 2, 1, 3, 5, 7, 6, 8 |
Traversalul de preordonare procesează nodul curent înainte de a se deplasa spre stânga și apoi spre dreapta pentru copii. Începând de la nodul rădăcină, patru, acțiunea este executată cu valoarea patru. Apoi, nodul stâng și toți copiii săi sunt procesați, urmat de nodul drept și de toți copiii acestuia.
O utilizare obișnuită a traversalului preorder ar fi să creeze o copie a copacului care conținea nu doar aceleași valori ale nodului, ci și aceeași ierarhie.
public void PreOrderTraversal (acțiunea de acțiune) PreOrderTraversal (action, _head); void privat PreOrderTraversal (acțiune acțiune, nod BinaryTreeNode) if (node! = null) acțiune (node.Value); PreOrderTraversal (acțiune, nod. PreOrderTraversal (acțiune, nod. Dreapta);
| Comportament | Efectuează acțiunea furnizată pentru fiecare valoare în postură (vezi descrierea care urmează). |
| Performanţă | Pe) |
| Ordin | 1, 3, 2, 6, 8, 7, 5, 4 |
Traversalul postorder vizitează copilul stâng și drept al nodului recursiv și apoi efectuează acțiunea pe nodul curent după terminarea copiilor.
Traversalele postorder sunt adesea folosite pentru a șterge un arbore întreg, cum ar fi în limbajele de programare în care fiecare nod trebuie eliberat sau pentru a șterge subrețele. Acesta este cazul deoarece nodul rădăcină este procesat (șters) ultima și copiii acestuia sunt procesați într-un mod care va reduce la minimum cantitatea de muncă Elimina algoritmul trebuie să efectueze.
public void PostOrderTraversal (acțiunea de acțiune) PostOrderTraversal (action, _head); privid void PostOrderTraversal (Acțiune de acțiune, BinaryTreeNode nod) if (node! = null) PostOrderTraversal (acțiune, node.Left); PostOrderTraversal (acțiune, nod.Right); acțiune (node.Value);
| Comportament | Efectuează acțiunea furnizată pentru fiecare valoare din pentru a (vezi descrierea care urmează). |
| Performanţă | Pe) |
| Ordin | 1, 2, 3, 4, 5, 6, 7, 8 |
Inorder traversal procesează nodurile în ordinea de sortare - în exemplul anterior, nodurile vor fi sortate în ordine numerică de la cea mai mică la cea mai mare. Ea face acest lucru prin găsirea celui mai mic (cel mai stâng) nod și apoi procesându-l înainte de a procesa nodurile mai mari (dreapta).
Traversele inorder sunt folosite ori de câte ori nodurile trebuie procesate în ordine de sortare.
Exemplul care urmează indică două metode diferite de a efectua un traversal inorder. Primul implementează o abordare recursivă care efectuează un apel invers pentru fiecare nod traversat. Al doilea elimină recursiunea prin utilizarea structurii de date Stack și returnează o IEnumerator pentru a permite enumerarea directă.
Void public InOrderTraversal (Acțiune de acțiune) InOrderTraversal (acțiune, _head); void privat InOrderTraversal (Acțiune de acțiune, BinaryTreeNode nod) if (node! = null) InOrderTraversal (acțiune, node.Left); acțiune (node.Value); InOrderTraversal (acțiune, nod.Right); public IEnumerator InOrderTraversal () // Acesta este un algoritm non-recursiv care utilizează o stivă pentru a demonstra eliminarea // recursivă. dacă (_head! = null) // Stocați nodurile pe care le-am ignorat în această stivă (evită recursiunea). Stack> stack = Stack nou> (); BinaryTreeNode curent = _head; // Când eliminăm recursiunea, trebuie să vedem dacă // ar trebui să mergem la nodul stâng sau la nodurile din dreapta următoare. bool goLeftNext = adevărat; // Începeți prin împingerea capului pe stivă. stack.Push (curent); în timp ce (stack.Count> 0) // Dacă mergem la stânga ... if (goLeftNext) // Împingeți totul, dar cel mai stâng nod în teanc. // Vom renunța la stânga după acest bloc. în timp ce (current.Left! = null) stack.Push (curent); curent = curent. // Inorder este stânga-> randament-> dreapta. randamentul randament curent.Value; Dacă putem merge bine, fă așa. dacă (curent.Right! = null) curent = actual.Right; // Odată ce ne-am dus o dată, trebuie să începem // să mergem din nou la stânga. goLeftNext = adevărat; altceva // Dacă nu putem merge bine, atunci trebuie să oprim nodul părinte //, astfel încât să îl putem procesa și apoi să mergem la nodul său drept. curent = stack.Pop (); goLeftNext = false;
| Comportament | Returnează un enumerator care enumeră utilizând algoritmul de traversare InOrder. |
| Performanţă | O (1) pentru a reveni la enumerator. Enumerând toate elementele este O (n). |
public IEnumerator GetEnumerator () retur InOrderTraversal (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () returnează GetEnumerator ();
Accentsconagua