Добро пожаловать в очередной выпуск нашей серии «Изучение кода на JavaScript». Сегодня мы собираемся изучить фундаментальное понятие информатики — обход дерева. И не просто обходы деревьев, а именно обходы бинарных деревьев.

Мы начнем с создания простого бинарного дерева. Затем мы рассмотрим три популярных метода обхода дерева: по порядку, по порядку и по порядку и рассмотрим, где и как вы можете использовать их в своих проектах JavaScript.

Что такое бинарное дерево?

Прежде чем мы начнем с обходами, давайте убедимся, что мы все на одной странице о том, что такое бинарное дерево. Бинарное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов, называемых левым дочерним элементом и правым дочерним элементом.

Обход дерева — это концепция информатики, при которой каждый узел древовидной структуры данных посещается систематическим образом. Существует три основных типа обхода дерева: предварительный порядок, порядок и пост-порядок. Каждый тип обхода имеет свои собственные практические варианты использования, в зависимости от конкретных потребностей разрабатываемого алгоритма. Вот упрощенное объяснение каждого типа обхода и пять практических вариантов использования для каждого:

Обход предварительного заказа
При обходе предварительного заказа процесс начинается с корня дерева и заканчивается в самом правом узле. Последовательность обхода такова: корень, левое поддерево, правое поддерево.

Практические варианты использования обхода предварительного заказа:

  • Рендеринг бинарного дерева.
  • Поиск значения в бинарном дереве.
  • Клонирование или копирование бинарного дерева.
  • Удаление бинарного дерева.
  • Получение высоты бинарного дерева.

Обход по порядку
При обходе по порядку процесс начинается с крайнего левого узла и заканчивается в крайнем правом узле. Последовательность обхода: левое поддерево, корень, правое поддерево.

Практические варианты использования обхода по порядку:

  • Сортировка значений в бинарном дереве поиска по возрастанию.
  • Реализация калькулятора инфиксных выражений.
  • Определение того, является ли бинарное дерево бинарным деревом поиска.
  • Поиск k-го наименьшего элемента в бинарном дереве поиска.
  • Получение следующего большего значения (преемника) в бинарном дереве поиска.

Пост-порядковый обход
При пост-порядковом обходе процесс начинается с крайнего левого узла и заканчивается корнем. Последовательность обхода: левое поддерево, правое поддерево, корень.

Практические варианты использования обхода после заказа:

  • Удаление бинарного дерева.
  • Оценка дерева выражений.
  • Нахождение высоты бинарного дерева.
  • Решение систем линейных уравнений с использованием деревьев выражений.
  • Генерация постфиксного представления дерева выражения 1​.

Вот базовый класс Node и класс BinaryTree в JavaScript:

Каждый узел содержит значение и имеет два дочерних узла. Класс BinaryTree по сути представляет собой оболочку для корневого узла.

Обход бинарных деревьев:

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree {
    constructor() {
        this.root = null;
    }
    traverse(callback, node = this.root) {
        if (node) {
            this.traverse(callback, node.left);
            callback(node);
            this.traverse(callback, node.right);
        }
    }
}

Этот код определяет простое двоичное дерево и метод обхода этого дерева в определенном порядке.

Вот разбивка:

  1. Node Класс: этот класс представляет узел в двоичном дереве. Каждый экземпляр класса Node имеет три свойства: value, left и right.
  • value: это свойство содержит значение узла.
  • left и right: эти свойства являются указателями на левого и правого потомков узла соответственно. Первоначально для них установлено значение null, означающее, что у узла нет дочерних узлов.

2. BinaryTree Класс: Этот класс представляет двоичное дерево. Он включает в себя корневое свойство и метод traverse:

  • root: это свойство является самым верхним узлом в дереве (т. е. корнем дерева). Изначально установлено значение null, что означает, что дерево при создании пусто.
  • traverse(callback, node = this.root): Это метод обхода бинарного дерева по порядку (слева -> корень -> справа). Он принимает два аргумента:
  • callback: Это функция, которая вызывается на каждом узле во время обхода. Функция обратного вызова может выполнять любую операцию над узлом, например, распечатывать значение узла или добавлять его в список.
  • node: Это текущий пройденный узел. По умолчанию это this.root, который является корнем дерева.

Вот как работает метод traverse:

  • Если node не равно null, он рекурсивно вызывает метод traverse для левого дочернего элемента узла (this.traverse(callback, node.left)). Это эффективно обходит все узлы в левом поддереве.
  • После полного обхода левого поддерева вызывается функция callback для текущего узла (callback(node)). Это выполняет функцию обратного вызова с текущим узлом в качестве аргумента.
  • Наконец, он рекурсивно вызывает метод traverse для правого потомка узла (this.traverse(callback, node.right)). Это пересекает все узлы в правом поддереве.

В ходе этого процесса каждый узел в дереве посещается один раз по порядку, и функция callback выполняется на каждом узле.

Обход по порядку

Давайте начнем с обхода по порядку. Вот как может выглядеть код для этого:

// In-order traversal
var inorderTraversal = function(root) {
    let result = [];
    const traverse = (node) => {
        if (node) {
            traverse(node.left);
            result.push(node.val);
            traverse(node.right);
        }
    }
    traverse(root);
    return result;
};

При обходе по порядку мы сначала посещаем левый дочерний элемент (включая все его поддерево), затем посещаем сам узел и, наконец, посещаем правый дочерний элемент (включая все его поддерево).

Обход предварительного заказа

Далее идет обход предзаказа. Вот код JavaScript:

// Pre-order traversal
var preorderTraversal = function(root) {
    let result = [];
    const traverse = (node) => {
        if (node) {
            result.push(node.val);
            traverse(node.left);
            traverse(node.right);
        }
    }
    traverse(root);
    return result;
};

В предварительном обходе мы сначала посещаем узел, затем его левое поддерево и, наконец, его правое поддерево.

Обход после заказа

При обратном обходе мы посещаем левое поддерево, затем правое поддерево и, наконец, корневой узел. Это особенно полезно, когда вам нужно посетить узлы в том порядке, в котором корень посещается последним. Например, это можно использовать в математических выражениях, где вам нужно оценить операнды перед оператором, или в сценариях, где вам нужно удалить или освободить все узлы в дереве, поскольку вы не хотите удалять родителя раньше его потомков. .

Вот пример реализации обхода после заказа в JavaScript:

var postorderTraversal = function(root) {
    let result = [];
    const traverse = (node) => {
        if (node) {
            traverse(node.left);
            traverse(node.right);
            result.push(node.val);
        }
    }
    traverse(root);
    return result;
};

В заключение, обходы деревьев являются фундаментальной частью работы с бинарными деревьями в компьютерных науках. Независимо от того, используете ли вы обход в предварительном порядке, по порядку или после заказа, понимание цели и применения каждого из них имеет решающее значение для разработки эффективных алгоритмов. Мы изучили, как эти методы реализованы в JavaScript, и рассмотрели варианты их практического использования. Имейте в виду, что выбранная вами стратегия обхода будет зависеть от конкретных потребностей вашего алгоритма. Будь то поиск значения, сортировка, удаление или оценка, правильный метод обхода может оптимизировать ваши операции и помочь обеспечить максимально эффективную работу вашего алгоритма.

Дополнительные материалы на PlainEnglish.io.

Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .