BinaryTree

BinaryTree.java

package lab4.tree;

/**
 * Клас для представлення бінарного дерева пошуку,
 * модифікація прикладу 3.9 з додаванням функції видалення елемента
 */
public class BinaryTree {

    // Клас для представлення вузла
    public static class Node {
        int    key;
        String value;
        Node   leftChild;
        Node   rightChild;
        Node(int key, String name) {
            this.key = key;
            this.value = name;
        }
        @Override
        public String toString() {
            return "Key: " + key + " Value:" + value;
        }
    }

    private Node root;

    /**
     * Додає новий вузол до дерева
     * @param key ключ вузла
     * @param value значення вузла
     */
    public void addNode(int key, String value) {
        // Створюємо новий вузол:
        Node newNode = new Node(key, value);
        if (root == null) { // перший доданий вузол
            root = newNode;
        }
        else {
            // Починаємо обхід:
            Node currentNode = root;
            Node parent;
            while (true) {
                parent = currentNode;
                // Перевіряємо ключі:
                if (key < currentNode.key) {
                    currentNode = currentNode.leftChild;
                    if (currentNode == null) {
                        // Розміщуємо вузол в потрібному місці:
                        parent.leftChild = newNode;
                        return;
                    }
                }
                else { 
                    currentNode = currentNode.rightChild;
                    if (currentNode == null) {
                        // Розміщуємо вузол в потрібному місці:
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

    /**
     * Обхід вузлів в порядку зростання ключів (in-order traversal)
     * @param currentNode поточний вузол
     */
    public void traverseTree(Node currentNode) {
        if (currentNode != null) {
            traverseTree(currentNode.leftChild);
            System.out.println(currentNode);
            traverseTree(currentNode.rightChild);
        }
    }

    /**
     * Обхід дерева, починаючи з кореня
     */
    public void traverseTree() {
        traverseTree(root);
    }

    /**
     * Виводить структуру дерева
     */
    public void printTree() {
        System.out.println("Структура дерева:");
        if (root == null) {
            System.out.println("Дерево порожнє");
            return;
        }
        
        printTree(root, "", true);
    }
    
    /**
     * Рекурсивно виводить структуру дерева
     * @param node поточний вузол
     * @param prefix префікс для візуалізації
     * @param isLeft чи є вузол лівим дочірнім
     */
    private void printTree(Node node, String prefix, boolean isLeft) {
        if (node == null) {
            return;
        }
        
        System.out.println(prefix + (isLeft ? "├── " : "└── ") + node.key + " (" + node.value + ")");
        
        // Додаємо відступи для наступних рівнів
        printTree(node.leftChild, prefix + (isLeft ? "│   " : "    "), true);
        printTree(node.rightChild, prefix + (isLeft ? "│   " : "    "), false);
    }

    /**
     * Пошук вузла за ключем
     * @param key ключ для пошуку
     * @return знайдений вузол або null, якщо вузол не знайдено
     */
    public Node findNode(int key) {
        Node focusNode = root;
        while (focusNode != null && focusNode.key != key) {
            if (key < focusNode.key) {
                focusNode = focusNode.leftChild;
            }
            else {
                focusNode = focusNode.rightChild;
            }
        }
        return focusNode; // повертає null, якщо вузол не знайдено
    }
    
    /**
     * Видаляє вузол з заданим ключем
     * @param key ключ вузла, який потрібно видалити
     * @return true, якщо вузол був видалений, false - якщо вузол не знайдено
     */
    public boolean removeNode(int key) {
        // Спеціальна обробка пустого дерева
        if (root == null) {
            return false;
        }
        
        // Змінні для відстеження поточного вузла та його батька
        Node current = root;
        Node parent = null;
        boolean isLeftChild = false;
        
        // Пошук вузла, який потрібно видалити
        while (current != null && current.key != key) {
            parent = current;
            
            if (key < current.key) {
                current = current.leftChild;
                isLeftChild = true;
            } else {
                current = current.rightChild;
                isLeftChild = false;
            }
        }
        
        // Якщо вузол не знайдено
        if (current == null) {
            return false;
        }
        
        // Випадок 1: Вузол, що видаляється, є листом (не має дочірніх вузлів)
        if (current.leftChild == null && current.rightChild == null) {
            // Якщо це корінь
            if (current == root) {
                root = null;
            } 
            // Якщо це лівий дочірній вузол
            else if (isLeftChild) {
                parent.leftChild = null;
            } 
            // Якщо це правий дочірній вузол
            else {
                parent.rightChild = null;
            }
        }
        
        // Випадок 2: Вузол, що видаляється, має тільки лівого дочірнього
        else if (current.rightChild == null) {
            // Якщо це корінь
            if (current == root) {
                root = current.leftChild;
            } 
            // Якщо це лівий дочірній вузол
            else if (isLeftChild) {
                parent.leftChild = current.leftChild;
            } 
            // Якщо це правий дочірній вузол
            else {
                parent.rightChild = current.leftChild;
            }
        }
        
        // Випадок 3: Вузол, що видаляється, має тільки правого дочірнього
        else if (current.leftChild == null) {
            // Якщо це корінь
            if (current == root) {
                root = current.rightChild;
            } 
            // Якщо це лівий дочірній вузол
            else if (isLeftChild) {
                parent.leftChild = current.rightChild;
            } 
            // Якщо це правий дочірній вузол
            else {
                parent.rightChild = current.rightChild;
            }
        }
        
        // Випадок 4: Вузол, що видаляється, має обох дочірніх
        else {
            // Знаходимо наступника (найменший вузол у правому піддереві)
            Node successor = getSuccessor(current);
            
            // Якщо це корінь
            if (current == root) {
                root = successor;
            } 
            // Якщо це лівий дочірній вузол
            else if (isLeftChild) {
                parent.leftChild = successor;
            } 
            // Якщо це правий дочірній вузол
            else {
                parent.rightChild = successor;
            }
            
            // Підключаємо ліве піддерево поточного вузла до наступника
            successor.leftChild = current.leftChild;
        }
        
        return true;
    }
    
    /**
     * Знаходить наступника для вузла, що видаляється
     * (найменший вузол у правому піддереві)
     * @param nodeToDelete вузол, для якого шукаємо наступника
     * @return наступник
     */
    private Node getSuccessor(Node nodeToDelete) {
        Node successorParent = nodeToDelete;
        Node successor = nodeToDelete.rightChild;
        Node current = successor;
        
        // Пошук найменшого вузла в правому піддереві
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        
        // Якщо наступник не є правим дочірнім вузлом вузла, що видаляється
        if (successor != nodeToDelete.rightChild) {
            // Переконфігуруємо посилання
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = nodeToDelete.rightChild;
        }
        
        return successor;
    }
}