Implementarea unui arbore binar în Java

1. Introducere

În acest articol, vom acoperi implementarea unui arbore binar în Java.

De dragul acestui articol, vom folosi un arbore binar sortat care va conține valori int .

2. Arborele binar

Un arbore binar este o structură de date recursivă în care fiecare nod poate avea cel mult 2 copii.

Un tip obișnuit de arbore binar este un arbore de căutare binar, în care fiecare nod are o valoare mai mare sau egală cu valorile nodurilor din subarborele din stânga și mai mici sau egale cu valorile nodurilor din sub-dreapta copac.

Iată o reprezentare vizuală rapidă a acestui tip de arbore binar:

Pentru implementare, vom folosi o clasă de nod auxiliar care va stoca valorile int și va păstra o referință la fiecare copil:

class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null; } }

Apoi, să adăugăm nodul de pornire al arborelui nostru, numit de obicei rădăcină:

public class BinaryTree { Node root; // ... }

3. Operațiuni comune

Acum, să vedem cele mai comune operații pe care le putem efectua pe un arbore binar.

3.1. Introducerea elementelor

Prima operațiune pe care o vom acoperi este inserarea de noi noduri.

În primul rând, trebuie să găsim locul în care dorim să adăugăm un nou nod pentru a păstra arborele sortat . Vom urma aceste reguli începând de la nodul rădăcină:

  • dacă valoarea noului nod este mai mică decât cea a nodului curent, mergem la copilul din stânga
  • dacă valoarea noului nod este mai mare decât cea a nodului curent, mergem la copilul potrivit
  • când nodul curent este nul, am ajuns la un nod frunză și putem introduce noul nod în acea poziție

În primul rând, vom crea o metodă recursivă pentru a face inserarea:

private Node addRecursive(Node current, int value) { if (current == null) { return new Node(value); } if (value  current.value) { current.right = addRecursive(current.right, value); } else { // value already exists return current; } return current; }

Apoi, vom crea metoda publică care începe recursiunea de la nodul rădăcină :

public void add(int value) { root = addRecursive(root, value); }

Acum să vedem cum putem folosi această metodă pentru a crea arborele din exemplul nostru:

private BinaryTree createBinaryTree() { BinaryTree bt = new BinaryTree(); bt.add(6); bt.add(4); bt.add(8); bt.add(3); bt.add(5); bt.add(7); bt.add(9); return bt; }

3.2. Găsirea unui element

Să adăugăm acum o metodă pentru a verifica dacă arborele conține o anumită valoare.

La fel ca înainte, vom crea mai întâi o metodă recursivă care traversează arborele:

private boolean containsNodeRecursive(Node current, int value) { if (current == null) { return false; } if (value == current.value) { return true; } return value < current.value ? containsNodeRecursive(current.left, value) : containsNodeRecursive(current.right, value); }

Aici, căutăm valoarea comparând-o cu valoarea din nodul curent, apoi continuăm în copilul din stânga sau din dreapta, în funcție de asta.

Apoi, să creăm metoda publică care începe de la rădăcină :

public boolean containsNode(int value) { return containsNodeRecursive(root, value); }

Acum, să creăm un test simplu pentru a verifica dacă arborele conține într-adevăr elementele inserate:

@Test public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(6)); assertTrue(bt.containsNode(4)); assertFalse(bt.containsNode(1)); }

Toate nodurile adăugate ar trebui să fie conținute în copac.

3.3. Ștergerea unui element

O altă operație obișnuită este ștergerea unui nod din copac.

Mai întâi, trebuie să găsim nodul de șters într-un mod similar, așa cum am făcut înainte:

private Node deleteRecursive(Node current, int value) { if (current == null) { return null; } if (value == current.value) { // Node to delete found // ... code to delete the node will go here } if (value < current.value) { current.left = deleteRecursive(current.left, value); return current; } current.right = deleteRecursive(current.right, value); return current; }

Odată ce am găsit nodul de șters, există 3 cazuri diferite:

  • un nod nu are copii - acesta este cel mai simplu caz; trebuie doar să înlocuim acest nod cu nul în nodul său părinte
  • un nod are exact un copil - în nodul părinte, înlocuim acest nod cu singurul său copil.
  • un nod are doi copii - acesta este cel mai complex caz deoarece necesită o reorganizare a copacilor

Să vedem cum putem implementa primul caz când nodul este un nod frunză:

if (current.left == null && current.right == null) { return null; }

Acum, să continuăm cu cazul când nodul are un copil:

if (current.right == null) { return current.left; } if (current.left == null) { return current.right; }

Aici, returnăm copilul care nu este nul, astfel încât să poată fi atribuit nodului părinte.

În cele din urmă, trebuie să ne ocupăm de cazul în care nodul are doi copii.

Mai întâi, trebuie să găsim nodul care va înlocui nodul șters. Vom folosi cel mai mic nod al nodului pentru a fi șters sub-arborele din dreapta:

private int findSmallestValue(Node root) { return root.left == null ? root.value : findSmallestValue(root.left); }

Apoi, atribuim cea mai mică valoare nodului de șters și după aceea, o vom șterge din subarborele din dreapta:

int smallestValue = findSmallestValue(current.right); current.value = smallestValue; current.right = deleteRecursive(current.right, smallestValue); return current;

În cele din urmă, să creăm metoda publică care începe ștergerea din rădăcină :

public void delete(int value) { root = deleteRecursive(root, value); }

Acum, să verificăm dacă ștergerea funcționează conform așteptărilor:

@Test public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(9)); bt.delete(9); assertFalse(bt.containsNode(9)); }

4. Traversarea Arborelui

În această secțiune, vom vedea diferite moduri de a traversa un copac, acoperind în detaliu căutările la adâncimea întâi și la lățimea întâi.

Vom folosi același arbore pe care l-am folosit înainte și vom arăta ordinea de traversare pentru fiecare caz.

4.1. Căutare în profunzime

Căutarea în adâncime este un tip de traversare care merge cât mai mult la fiecare copil înainte de a explora următorul frate.

Există mai multe modalități de a efectua o căutare în profunzime: în ordine, precomandă și post-comandă.

Trecerea în ordine constă în vizitarea mai întâi a subarborelui stâng, apoi a nodului rădăcină și, în final, a subarborelui drept:

public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.value); traverseInOrder(node.right); } }

Dacă apelăm această metodă, ieșirea consolei va afișa traversarea în ordine:

3 4 5 6 7 8 9

Traversarea precomandă vizitează mai întâi nodul rădăcină, apoi subarborele din stânga și, în final, subarborele din dreapta:

public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

Și să verificăm traversarea precomandă în ieșirea consolei:

6 4 3 5 8 7 9

Traversarea post-comandă vizitează subarborele din stânga, subarborele din dreapta și nodul rădăcină la sfârșit:

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.value); } }

Iată nodurile în post-comandă:

3 5 4 7 9 8 6

4.2. Lățime-Prima căutare

Acesta este un alt tip obișnuit de traversare care vizitează toate nodurile unui nivel înainte de a trece la nivelul următor .

Acest tip de traversare se mai numește nivel de ordine și vizitează toate nivelurile arborelui începând de la rădăcină și de la stânga la dreapta.

Pentru implementare, vom folosi o coadă pentru a menține nodurile de la fiecare nivel în ordine. Vom extrage fiecare nod din listă, îi vom printa valorile, apoi îi vom adăuga copiii la coadă:

public void traverseLevelOrder() { if (root == null) { return; } Queue nodes = new LinkedList(); nodes.add(root); while (!nodes.isEmpty()) { Node node = nodes.remove(); System.out.print(" " + node.value); if (node.left != null) { nodes.add(node.left); } if (node.right != null) { nodes.add(node.right); } } }

În acest caz, ordinea nodurilor va fi:

6 4 8 3 5 7 9

5. Concluzie

În acest articol, am văzut cum să implementăm un arbore binar sortat în Java și cele mai frecvente operațiuni ale acestuia.

Codul sursă complet pentru exemple este disponibil pe GitHub.