Структуры данных в JavaScript
Двоичное дерево — это особый тип структуры данных графа, и часто это первый граф, который люди изучают. Двоичные деревья содержат корневой узел с двумя ветвями, расположенными слева направо в порядке возрастания. Каждый разветвленный узел может иметь до двух собственных ветвей и так далее. Если эти два требования не выполняются, то структура данных, скорее всего, все еще будет деревом, но не двоичным деревом. Например, если узел имеет три ветви, его можно считать троичным деревом. В этой статье будут рассмотрены только бинарные деревья, поскольку они являются хорошей ступенькой к изучению деревьев. Также отмечается, что дерево не будет содержать повторяющихся данных. Начнем с диаграммы, которая демонстрирует ранее установленные требования.
Класс узла
На основе рисунка 1 можно построить простой класс Node со свойством data, а также со свойствами left и right, которые указывают на дочерние узлы. По умолчанию свойства left и right должны иметь значение null, поскольку они могут быть неизвестны при создании экземпляра класса Node.
Класс двоичного дерева
С этого момента мы можем определить класс BinaryTree, который будет содержать все связанные функции, такие как добавление и удаление узлов. При создании экземпляра BinaryTree он также должен содержать свойство root, указывающее на корень Node. root можно обновлять по мере заполнения BinaryTree.
Добавить функцию
Определив конструктор класса BinaryTree, мы можем добавить первую функцию, add, которая вставляет новый узел в правильное место в дереве. Правильное место в порядке возрастания слева направо.
На рис. 4 создается экземпляр нового узла, который затем назначается свойству root элемента BinaryTree, если root в данный момент равен null, в противном случае новый узел Node передается вспомогательной функции addNode. Эта вспомогательная функция будет проходить через соответствующие ветви дерева, чтобы найти правильное местоположение, как показано на рисунке 5.
В приведенном выше фрагменте кода видно, что когда функция просматривает свойства left и right переданного в node, она будет рекурсивно вызывать себя, если это свойство не null. Это связано с тем, что узел уже определен в этой позиции, поэтому функция должна перейти на другой уровень в дереве. Это продолжается до тех пор, пока не будет найдено свободное место для размещения newNode. Обратите внимание, что эта функция предполагает, что node является экземпляром Node.
Удалить функцию
Теперь, когда мы успешно реализовали методологию добавления экземпляров Node в BinaryTree, следующая логическая функция — remove. Это немного сложнее, чем add, так как есть несколько случаев, которые необходимо обработать; удаление Node с пустыми свойствами left и right, Node с пустым только одним из этих свойств и одного с заполненными left и right. Эта функция также должна будет выйти из root дерева и искать соответствующие данные, поэтому рекурсивное решение имеет смысл.
В функции remove свойство root обновляется, так как удаление Node обновляет все дерево. Отсюда вызывается вспомогательная функция removeNode, чтобы пройтись по дереву, чтобы найти данные перед удалением этого Node.
Первая половина рисунка 7 показывает, как removeNode рекурсивно проходит по дереву, пока не будет найден правильный Node. Существует особый случай, когда найдено null Node, указывающее, что данные не существуют в дереве. Отсюда removeNode проверяет дочерние элементы выбранного Node, чтобы определить, как его удалить. Если дочерних элементов нет, то дополнительная работа не требуется, но если есть один дочерний элемент, этот дочерний элемент должен заменить выбранный Node.
Последний случай, когда выбранный Node имеет двух дочерних элементов, обрабатывается в конце removeNode. Левая сторона выбранного узла остается неизменной, а правая часть изменяется. Минимум Node правой стороны подтягивается для замены выбранных Node данных с помощью функции findMinNode. Затем этот узел minimum удаляется с помощью рекурсивного вызова removeNode.
Резюме
Вы завершили построение бинарного дерева. Этот особый тип графа имеет root Node, который имеет до двух дочерних узлов, которые сами могут иметь до двух дочерних узлов, и так далее. Данные располагаются в порядке возрастания слева направо, как показано на рисунке 1. Добавление узла Node было относительно простым, но удаление узла требовало проверки дочерних элементов существующего узла Node. Потратьте некоторое время, чтобы убедиться, что вы понимаете, как removeNode манипулирует BinaryTree.
