Implementacja drzewa binarnego w Javie

1. Wstęp

W tym artykule zajmiemy się implementacją drzewa binarnego w Javie.

Na potrzeby tego artykułu użyjemy posortowanego drzewa binarnego, które będzie zawierało wartości int .

2. Drzewo binarne

Drzewo binarne to rekurencyjna struktura danych, w której każdy węzeł może mieć maksymalnie 2 dzieci.

Powszechnym typem drzewa binarnego jest drzewo wyszukiwania binarnego, w którym każdy węzeł ma wartość większą lub równą wartościom węzłów w lewym poddrzewie oraz mniejszą lub równą wartościom węzłów w prawym pod-drzewie. drzewo.

Oto szybkie wizualne przedstawienie tego typu drzewa binarnego:

Do implementacji użyjemy pomocniczej klasy Node, która będzie przechowywać wartości int i zachowywać referencje do każdego dziecka:

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

Następnie dodajmy początkowy węzeł naszego drzewa, zwykle nazywany korzeniem:

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

3. Wspólne operacje

Zobaczmy teraz, jakie operacje są najczęściej wykonywane na drzewie binarnym.

3.1. Wstawianie elementów

Pierwszą operacją, którą zajmiemy się, jest wstawianie nowych węzłów.

Najpierw musimy znaleźć miejsce, w którym chcemy dodać nowy węzeł, aby drzewo było posortowane . Będziemy przestrzegać tych zasad, zaczynając od węzła głównego:

  • jeśli wartość nowego węzła jest niższa niż wartość obecnego węzła, przechodzimy do lewego dziecka
  • jeśli wartość nowego węzła jest większa niż wartość bieżącego węzła, przechodzimy do właściwego dziecka
  • gdy bieżący węzeł jest pusty, dotarliśmy do węzła liścia i możemy wstawić nowy węzeł w tym miejscu

Najpierw utworzymy rekurencyjną metodę wstawiania:

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; }

Następnie utworzymy metodę publiczną, która rozpocznie rekurencję z węzła głównego :

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

Zobaczmy teraz, jak możemy użyć tej metody do stworzenia drzewa z naszego przykładu:

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. Znalezienie elementu

Dodajmy teraz metodę sprawdzania, czy drzewo zawiera określoną wartość.

Tak jak poprzednio, najpierw utworzymy metodę rekurencyjną, która przechodzi przez drzewo:

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); }

Tutaj szukamy wartości, porównując ją z wartością w bieżącym węźle, a następnie kontynuujemy w lewym lub prawym dziecku, w zależności od tego.

Następnie stwórzmy metodę publiczną, która zaczyna się od katalogu głównego :

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

Teraz stwórzmy prosty test, aby sprawdzić, czy drzewo naprawdę zawiera wstawione elementy:

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

Wszystkie dodane węzły powinny znajdować się w drzewie.

3.3. Usuwanie elementu

Inną powszechną operacją jest usunięcie węzła z drzewa.

Najpierw musimy znaleźć węzeł do usunięcia w podobny sposób, jak robiliśmy to wcześniej:

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; }

Po znalezieniu węzła do usunięcia istnieją 3 główne różne przypadki:

  • węzeł nie ma dzieci - to najprostszy przypadek; musimy tylko zastąpić ten węzeł null w jego węźle nadrzędnym
  • węzeł ma dokładnie jedno dziecko - w węźle nadrzędnym zastępujemy ten węzeł jedynym dzieckiem.
  • węzeł ma dwoje dzieci - jest to najbardziej złożony przypadek, ponieważ wymaga reorganizacji drzewa

Zobaczmy, jak możemy zaimplementować pierwszy przypadek, gdy węzeł jest węzłem liścia:

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

Teraz przejdźmy do przypadku, gdy węzeł ma jedno dziecko:

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

Tutaj zwracamy niezerowe dziecko, aby można je było przypisać do węzła nadrzędnego.

Na koniec musimy zająć się przypadkiem, w którym węzeł ma dwoje dzieci.

Najpierw musimy znaleźć węzeł, który zastąpi usunięty węzeł. Użyjemy najmniejszego węzła z prawego poddrzewa usuwanego węzła:

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

Następnie przypisujemy najmniejszą wartość do węzła do usunięcia, a następnie usuniemy ją z prawego poddrzewa:

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

Na koniec stwórzmy metodę publiczną, która rozpocznie usuwanie z katalogu głównego :

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

Teraz sprawdźmy, czy usuwanie działa zgodnie z oczekiwaniami:

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

4. Przechodzenie po drzewie

W tej sekcji zobaczymy różne sposoby przechodzenia po drzewie, szczegółowo omawiając przeszukiwanie najpierw w głąb i wszerz.

Użyjemy tego samego drzewa, którego używaliśmy wcześniej, i pokażemy kolejność przemierzania każdego przypadku.

4.1. Przeszukiwanie w głąb

Przeszukiwanie w głąb jest rodzajem przemierzania, które w każdym dziecku sięga tak głęboko, jak to tylko możliwe, przed zbadaniem następnego rodzeństwa.

Istnieje kilka sposobów przeprowadzania wyszukiwania w głąb: na zamówienie, w przedsprzedaży i na koniec.

Przechodzenie w kolejności składa się z odwiedzenia najpierw lewego poddrzewa, następnie węzła głównego, a na końcu prawego poddrzewa:

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

Jeśli wywołasz tę metodę, dane wyjściowe konsoli pokażą przechodzenie w kolejności:

3 4 5 6 7 8 9

Trawersal zamówienia w przedsprzedaży odwiedza najpierw węzeł główny, następnie lewe poddrzewo, a na końcu prawe poddrzewo:

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

I sprawdźmy przechodzenie przed zamówieniem w danych wyjściowych konsoli:

6 4 3 5 8 7 9

Przechodzenie po zamówieniu odwiedza lewe poddrzewo, prawe poddrzewo i węzeł główny na końcu:

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

Oto węzły w zamówieniu końcowym:

3 5 4 7 9 8 6

4.2. Przeszukiwanie wszerz

Jest to kolejny popularny typ przechodzenia, który odwiedza wszystkie węzły poziomu przed przejściem do następnego poziomu .

Ten rodzaj przechodzenia jest również nazywany porządkiem poziomów i odwiedza wszystkie poziomy drzewa, zaczynając od korzenia i od lewej do prawej.

Do implementacji użyjemy kolejki do przechowywania węzłów z każdego poziomu w porządku. Wyodrębnimy każdy węzeł z listy, wydrukujemy jego wartości, a następnie dodamy jego dzieci do kolejki:

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); } } }

W takim przypadku kolejność węzłów będzie następująca:

6 4 8 3 5 7 9

5. Wniosek

W tym artykule widzieliśmy, jak zaimplementować posortowane drzewo binarne w Javie i jego najpopularniejsze operacje.

Pełny kod źródłowy przykładów jest dostępny na GitHub.