Внедряване на двоично дърво в Java

1. Въведение

В тази статия ще разгледаме изпълнението на двоично дърво в Java.

За целите на тази статия ще използваме сортирано двоично дърво, което ще съдържа int стойности .

2. Двоично дърво

Двоичното дърво е рекурсивна структура от данни, където всеки възел може да има най-много 2 деца.

Често срещан тип двоично дърво е двоично дърво за търсене, при което всеки възел има стойност, която е по-голяма или равна на стойностите на възлите в лявото поддърво и по-малка или равна на стойностите на възела в дясната под- дърво.

Ето кратко визуално представяне на този тип двоично дърво:

За реализацията ще използваме спомагателен клас Node, който ще съхранява int стойности и ще запази препратка към всяко дете:

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

След това нека добавим началния възел на нашето дърво, обикновено наричан root:

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

3. Общи операции

Сега нека видим най-често срещаните операции, които можем да извършим върху двоично дърво.

3.1. Вмъкване на елементи

Първата операция, която ще покрием, е вмъкването на нови възли.

Първо, трябва да намерим мястото, където искаме да добавим нов възел, за да държим дървото сортирано . Ще следваме тези правила, започвайки от основния възел:

  • ако стойността на новия възел е по-ниска от стойността на текущия възел, отиваме в лявото дете
  • ако стойността на новия възел е по-голяма от стойността на текущия възел, отиваме към правилното дете
  • когато текущият възел е нулев, стигнахме до листов възел и можем да вмъкнем новия възел в това положение

Първо ще създадем рекурсивен метод за извършване на вмъкването:

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

След това ще създадем публичния метод, който стартира рекурсията от основния възел:

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

Сега нека видим как можем да използваме този метод за създаване на дървото от нашия пример:

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. Намиране на елемент

Нека сега добавим метод за проверка дали дървото съдържа конкретна стойност.

Както и преди, първо ще създадем рекурсивен метод, който пресича дървото:

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

Тук търсим стойността, като я сравняваме със стойността в текущия възел, след което продължаваме в лявото или дясното дете в зависимост от това.

След това нека създадем публичния метод, който започва от корена :

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

Сега, нека създадем прост тест, за да проверим дали дървото наистина съдържа вмъкнатите елементи:

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

Всички добавени възли трябва да се съдържат в дървото.

3.3. Изтриване на елемент

Друга често срещана операция е изтриването на възел от дървото.

Първо, трябва да намерим възела за изтриване по подобен начин, както направихме преди:

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

След като намерим възела за изтриване, има 3 основни различни случая:

  • възел няма деца - това е най-простият случай; просто трябва да заменим този възел с null в неговия родителски възел
  • възел има точно едно дете - в родителския възел ние заместваме този възел с единственото му дете.
  • възел има две деца - това е най-сложният случай, защото изисква реорганизация на дърво

Нека да видим как можем да реализираме първия случай, когато възелът е листен възел:

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

Сега нека продължим със случая, когато възелът има едно дете:

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

Тук връщаме ненулевото дете, за да може да бъде присвоено на родителския възел.

И накрая, трябва да се справим със случая, когато възелът има две деца.

Първо, трябва да намерим възела, който ще замени изтрития възел. Ще използваме най-малкия възел на възела, за да бъде изтрито дясното под-дърво:

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

След това присвояваме най-малката стойност на възела за изтриване и след това ще го изтрием от дясното поддърво:

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

И накрая, нека създадем публичния метод, който стартира изтриването от корена :

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

Сега нека проверим дали изтриването работи както се очаква:

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

4. Преминаване през дървото

В този раздел ще видим различни начини за обхождане на дърво, като обхващаме в детайли търсенията с дълбочина и ширина.

Ще използваме същото дърво, което използвахме преди, и ще покажем реда на обхождане за всеки случай.

4.1. Дълбочина първо търсене

Търсенето с дълбочина първо е вид обход, който се задълбочава колкото е възможно повече при всяко дете, преди да проучи следващия брат или сестра.

Има няколко начина за извършване на първоначално търсене в дълбочина: по поръчка, предварителна поръчка и след поръчка.

Обръщането по ред се състои от първо посещение на лявото поддърво, след това на основния възел и накрая на дясното поддърво:

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

Ако извикаме този метод, изходът на конзолата ще покаже обръщането по ред:

3 4 5 6 7 8 9

Обръщането с предварителна поръчка посещава първо коренния възел, след това лявото поддърво и накрая дясното поддърво:

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

И нека проверим обхождането на предварителната поръчка в изхода на конзолата:

6 4 3 5 8 7 9

Обръщането след поръчка посещава лявото поддърво, дясното поддърво и коренния възел в края:

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

Ето възлите в пост-поръчка:

3 5 4 7 9 8 6

4.2. Широко-първо търсене

Това е друг често срещан тип обход, който посещава всички възли на ниво, преди да премине към следващото ниво .

Този вид обход се нарича още ред на ниво и посещава всички нива на дървото, започвайки от корена и отляво надясно.

За изпълнението ще използваме Опашка, за да задържим възлите от всяко ниво в ред. Ще извлечем всеки възел от списъка, ще отпечатаме неговите стойности, след което ще добавим неговите деца в опашката:

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

В този случай редът на възлите ще бъде:

6 4 8 3 5 7 9

5. Заключение

В тази статия видяхме как да реализираме сортирано двоично дърво в Java и най-често срещаните операции.

Пълният изходен код за примерите е достъпен на GitHub.