Какие знаешь алгоритмы обхода дерева?

Алгоритмы обхода дерева

Общее описание

Обход дерева — это процесс посещения всех узлов дерева в определённом порядке. Существуют различные стратегии обхода, каждая из которых полезна для конкретных задач. Рассмотрим основные алгоритмы и их реализации на Java.

Поиск в глубину (DFS — Depth-First Search)

Этот алгоритм идёт глубоко в дерево, прежде чем перейти на следующую ветвь.

Прямой обход (Preorder)

Порядок: узел → левое поддерево → правое поддерево

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

public void preorderTraversal(TreeNode root) {
    if (root == null) return;
    
    System.out.print(root.val + " ");  // Посещаем узел
    preorderTraversal(root.left);        // Обходим левое поддерево
    preorderTraversal(root.right);       // Обходим правое поддерево
}

// Итеративная реализация через стек
public void preorderIterative(TreeNode root) {
    if (root == null) return;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        
        // Добавляем в стек в обратном порядке (правое перед левым)
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

Пример: Для дерева [1, 2, 3] результат: 1 2 3

Средний обход (Inorder)

Порядок: левое поддерево → узел → правое поддерево

public void inorderTraversal(TreeNode root) {
    if (root == null) return;
    
    inorderTraversal(root.left);         // Левое поддерево
    System.out.print(root.val + " ");   // Узел
    inorderTraversal(root.right);        // Правое поддерево
}

// Итеративная реализация
public void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // Идём в левое поддерево
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        current = stack.pop();
        System.out.print(current.val + " ");
        current = current.right;  // Переходим в правое поддерево
    }
}

Пример: Для дерева [1, 2, 3] результат: 2 1 3

Особенность: Для бинарного дерева поиска (BST) inorder обход возвращает элементы в отсортированном порядке!

Обратный обход (Postorder)

Порядок: левое поддерево → правое поддерево → узел

public void postorderTraversal(TreeNode root) {
    if (root == null) return;
    
    postorderTraversal(root.left);       // Левое поддерево
    postorderTraversal(root.right);      // Правое поддерево
    System.out.print(root.val + " ");   // Узел
}

// Итеративная реализация
public void postorderIterative(TreeNode root) {
    if (root == null) return;
    
    Stack<TreeNode> stack = new Stack<>();
    TreeNode lastVisited = null;
    TreeNode current = root;
    
    while (!stack.isEmpty() || current != null) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {
            TreeNode peekNode = stack.peek();
            // Если есть правое поддерево и оно ещё не посещено
            if (peekNode.right != null && lastVisited != peekNode.right) {
                current = peekNode.right;
            } else {
                System.out.print(peekNode.val + " ");
                lastVisited = stack.pop();
            }
        }
    }
}

Пример: Для дерева [1, 2, 3] результат: 2 3 1

Поиск в ширину (BFS — Breadth-First Search)

Обход по уровням: посещаем все узлы одного уровня перед переходом к следующему.

public void levelOrderTraversal(TreeNode root) {
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

// Обход с информацией об уровнях
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        
        result.add(level);
    }
    
    return result;
}

Пример: Для дерева [1, 2, 3] результат: 1 2 3

Сравнительная таблица

Все обходы имеют временную сложность O(n), где n — количество узлов.