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 основні різні випадки:
- у вузла немає дітей - це найпростіший випадок; нам просто потрібно замінити цей вузол на нульовий у його батьківському вузлі
- у вузла є рівно одна дочірня особа - у батьківському вузлі ми замінюємо цей вузол на його єдину дочірню організацію.
- вузол має двох дітей - це найскладніший випадок, оскільки він вимагає реорганізації дерева
Давайте подивимося, як ми можемо реалізувати перший випадок, коли вузол є листовим вузлом:
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 64.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 95. Висновок
У цій статті ми побачили, як реалізувати відсортоване бінарне дерево в Java та найпоширеніші операції.
Повний вихідний код для прикладів доступний на GitHub.