Понимание алгоритмов важно для каждого разработчика программного обеспечения. Алгоритмы — обычная часть любого собеседования по кодированию, решаете ли вы проблемы на JavaScript, Java или Python. Вы можете использовать алгоритмы для прохождения собеседований по кодированию, получить работу или решить специфические проблемы на работе.
Сегодняшнее руководство будет сосредоточено на алгоритмах обхода элементов в дереве. Обход дерева выглядит по-разному на разных языках программирования; мы будем использовать JavaScript. Начнём с обновления наших знаний о деревьях. Далее мы изучим несколько полезных алгоритмов и рассмотрим некоторые общие вопросы интервью.
Какие деревья?
В информатике деревья — это нелинейные структуры данных, представленные как набор узлов, соединённых рёбрами. Каждый узел хранит данные любого типа, и все узлы в дереве имеют один и тот же тип данных.
Древовидные структуры данных обычно используются для хранения информации с сохранением её иерархии, для реализации быстрого поиска, работы в сети и наследования.
Основные компоненты дерева включают:
- Корень, который является самым верхним узлом (он не имеет родительского узла). Обычно это начальная точка вашего дерева.
- Родительский узел, который подключён вниз к одному или двум узлам.
- Дочерний узел, который имеет входящую ссылку (или соединительную кромку) от родительского узла над ним.
- Родственные узлы — это узлы, которые имеют одного и того же родителя.
- В листовых узлах имеют родительские узлы, но нет дочерних узлов. Обычно это базовые / нижние узлы.
- Поддерево дерево удерживается в рамках большого дерева.
- Степень узла относится к числу поддеревьев в дереве.
- Глубина дерева относится к числу рёбер между определённым узлом и корнем.
- Высота узла относится к числу рёбер в самом длинном пути от заданного узла к узлу листа.
Как пересекать деревья
Пройденное дерево — это дерево, в котором каждый узел дерева был посещён. Обход — это процесс, включающий итерацию по всем узлам определённым образом.
В отличие от линейных структур данных (таких как массивы, связанные списки или очереди ), которые имеют только один логический способ обхода с помощью рекурсии, деревья можно обходить разными способами. Обычно существует 2 итерационных способа обхода деревьев:
- Поиск / обход в глубину (DFS).
- Поиск / обход в ширину (BFS).
Обход в глубину
Обход в глубину включает обход дерева сверху вниз. Они реализованы по принципу FILO (First In Last Out), как и структура данных стека. Сначала проходят левые поддеревья, затем правые поддеревья.
Это обычно наблюдается при обходе двоичного дерева. Двоичные деревья — это деревья, в которых каждый узел имеет не более 2 дочерних узлов. В приведённом ниже дереве узел со значением 1 будет первым, который будет помещён в стек, за ним последуют узлы со значениями 2, 3 и 4, затем он вернётся наверх к узлу со значением 5 вниз..
Когда достигается конец дерева, значения извлекаются из стека обратно в дерево.
Существует 3 типа обхода в глубину:
1. Обход по порядку
В обходе по порядку мы проходим левый дочерний элемент и его поддерево (я), затем посещаем корень, а затем проходим правый дочерний элемент и его поддерево (я). Требуется порядок «влево-корень-вправо».
Прежде чем мы рассмотрим образец кода для этого алгоритма, давайте попробуем обрисовать в общих чертах необходимые шаги:
- Начиная с корневого узла, мы рекурсивно проходим левый узел и его поддеревья.
- Мы начинаем чтение с левого листового узла, за которым следует его родительский и родственный узел.
- Мы делаем это рекурсивно, пока не вернёмся к корневому узлу, затем повторяем процесс для правого узла, начиная чтение с его самого левого листового узла.
inOrderprint(currentNode) {//if the currentNode IS NOT EQUAL to nullif (currentNode!==null) {//make recursive call to the left subtreethis.inOrderPrint(currentNode.leftChild);//print the value of the currentNodeconsole.log(currentNode.val);//make recursive call to the right subtreethis.inOrderPrint(currentNode.rightChild);}}
Вот код для inOrderPrint:
class Node {constructor(value) {this.val = value;this.leftChild = null;this.rightChild = null;}}class BinarySearchTree {constructor(rootValue) {this.root = new Node(rootValue);}insert(currentNode, newValue) {if (currentNode === null) {currentNode = new Node(newValue);} else if (newValue < currentNode.val) {currentNode.leftChild = this.insert(currentNode.leftChild, newValue);} else {currentNode.rightChild = this.insert(currentNode.rightChild, newValue);}return currentNode;}insertBST(newValue) {if(this.root==null){this.root=new Node(newValue);return;}this.insert(this.root, newValue);}preOrderPrint(currentNode) {if (currentNode!==null) {console.log(currentNode.val);this.preOrderPrint(currentNode.leftChild);this.preOrderPrint(currentNode.rightChild);}}inOrderPrint(currentNode) {if (currentNode!==null) {this.inOrderPrint(currentNode.leftChild);console.log(currentNode.val);this.inOrderPrint(currentNode.rightChild);}}}var BST = new BinarySearchTree(6);console.log(«The root val for BST : «, BST.root.val)BST.insertBST(4);BST.insertBST(9);BST.insertBST(5);BST.insertBST(2);BST.insertBST(8);BST.insertBST(12);BST.inOrderPrint(BST.root);
В нашей реализации, мы создаём объект с именем BSTиз BinarySearchTreeкласса и вставить некоторые значения в нём. Затем мы передадим в inOrderPrint()функцию корень объекта в качестве отправной точки для обхода.
Если узел, переданный в функцию, не является null, эта функция inOrderPrint()сначала рекурсивно вызывает левый дочерний элемент, то есть левое поддерево, а затем печатает значение в узле. Затем он inOrderPrint()рекурсивно вызывает правого потомка, то есть правого поддерева.
Узел распечатает свое собственное значение после того, как будут выполнены все последующие вызовы левого поддерева.
Когда рекурсивные вызовы попадут в нулевые узлы, они вернутся из функции, ничего не делая.
2. Предварительный заказ
Обход предварительного заказа считывает узлы в дереве в порядке уровня за уровнем, левый дочерний элемент перед правым дочерним элементом. Элементы читаются в порядке «корень-влево-вправо».
preOrderPrint(currentNode) {//if the currentNode IS NOT EQUAL to nullif (currentNode!==null) {//print its valueconsole.log(currentNode.val);//make recursive call to the left subtreethis.preOrderPrint(currentNode.leftChild);//make recursive call to the right subtreethis.preOrderPrint(currentNode.rightChild);}//if the currentNode IS EQUAL to null, then//we simply return}
Как реализовать preOrderPrint в JavaScript
class Node {constructor(value) {this.val = value;this.leftChild = null;this.rightChild = null;}}class BinarySearchTree {constructor(rootValue) {this.root = new Node(rootValue);}insert(currentNode, newValue) {if (currentNode === null) {currentNode = new Node(newValue);} else if (newValue < currentNode.val) {currentNode.leftChild = this.insert(currentNode.leftChild, newValue);} else {currentNode.rightChild = this.insert(currentNode.rightChild, newValue);}return currentNode;}insertBST(newValue) {if(this.root==null){this.root=new Node(newValue);return;}this.insert(this.root, newValue);}preOrderPrint(currentNode) {if (currentNode!==null) {console.log(currentNode.val);this.preOrderPrint(currentNode.leftChild);this.preOrderPrint(currentNode.rightChild);}}}var BST = new BinarySearchTree(6);console.log(«The root val for BST : «, BST.root.val)BST.insertBST(4);BST.insertBST(9);BST.insertBST(5);BST.insertBST(2);BST.insertBST(8);BST.insertBST(12);BST.insertBST(10);BST.insertBST(14);BST.preOrderPrint(BST.root);
Алгоритм обхода предзаказа, начиная с корневого узла, выглядит следующим образом:
- Посетите currentNodeи отобразите данные.
- currentNode Рекурсивно пройти по левому поддереву.
- currentNode Рекурсивно пройти по правому поддереву.
Теперь рассмотрим код обхода предзаказа.
Создаём новый объект BinarySearchTreeкласса и вставляем в него значения. Затем мы передаём корневой узел preOrderPrint()функции.
Эта функция печатает значение узла, а затем рекурсивно вызывается для левого потомка. Когда узлы в левом поддереве были посещены, оно рекурсивно вызывается для правого дочернего дерева и его поддеревьев.
Когда рекурсивные вызовы достигнут нулевых узлов, они вернутся из функции, ничего не делая.
3. Пост-заказ
Последняя стратегия обхода дерева — это обход после заказа. Здесь мы проходим левое поддерево, затем правое поддерево перед тем, как посетить корневой узел. Требуется порядок «влево-вправо-корень».
postOrderPrint(currentNode) {//if the currentNode IS NOT EQUAL to nullif (currentNode!==null) {//make recursive call to the left subtreethis.postOrderPrint(currentNode.leftChild);//make recursive call to the right subtreethis.postOrderPrint(currentNode.rightChild);//print its valueconsole.log(currentNode.val);}}
Как реализовать postOrderPrint
class Node {constructor(value) {this.val = value;this.leftChild = null;this.rightChild = null;}}class BinarySearchTree {constructor(rootValue) {this.root = new Node(rootValue);}insert(currentNode, newValue) {if (currentNode === null) {currentNode = new Node(newValue);} else if (newValue < currentNode.val) {currentNode.leftChild = this.insert(currentNode.leftChild, newValue);} else {currentNode.rightChild = this.insert(currentNode.rightChild, newValue);}return currentNode;}insertBST(newValue) {if(this.root==null){this.root=new Node(newValue);return;}this.insert(this.root, newValue);}preOrderPrint(currentNode) {if (currentNode !== null) {console.log(currentNode.val);this.preOrderPrint(currentNode.leftChild);this.preOrderPrint(currentNode.rightChild);}}inOrderPrint(currentNode) {if (currentNode !== null) {this.inOrderPrint(currentNode.leftChild);console.log(currentNode.val);this.inOrderPrint(currentNode.rightChild);}}postOrderPrint(currentNode) {if (currentNode !== null) {this.postOrderPrint(currentNode.leftChild);this.postOrderPrint(currentNode.rightChild);console.log(currentNode.val);}}}var BST = new BinarySearchTree(6);console.log(«The root val for BST : «, BST.root.val)BST.insertBST(4);BST.insertBST(9);BST.insertBST(5);BST.insertBST(2);BST.insertBST(8);BST.insertBST(12);BST.postOrderPrint(BST.root);
Шаги, необходимые для обхода пост-заказа, следующие:
- currentNode Рекурсивно пройти по левому поддереву.
- currentNode Рекурсивно пройти по правому поддереву.
- Посетите currentNode и распечатайте его значение.
Опять же, мы создаём объект с именем BSTи вставляем в него значения. Затем мы передадим корневой узел postOrderPrint()функции в качестве отправной точки для обхода.
Если узел, переданный в функцию, не является нулём, эта функция postOrderPrint()сначала вызывает левый дочерний элемент, а затем — правый дочерний элемент. Наконец, он печатает значение currentNode.
Значение родительского или корневого узла будет напечатано только после выполнения всех вызовов.
Обход уровня-порядка (в ширину)
При обходе по уровням деревья проходят по уровням. Это означает, что мы посещаем каждый узел на уровне слева направо, прежде чем перейти на более низкий уровень. Все дочерние узлы проходят до следующего уровня узлов-внуков.
Это похоже на поиск в ширину из алгоритмов графа.
traverseBFS() {if (!this.root) return;this.queue = [];this.queue.push(this.root);this.output = [];while (this.queue.length) {const node = this.queue.shift();if (node.left) {this.queue.push(node.left);}if (node.right) {this.queue.push(node.right);}this.output.push(node.data);}return this.output;}
При обходе по уровням мы используем очередь для хранения ссылки на узлы, которые мы хотим посетить. Это гарантирует, что мы можем перемещаться по дереву слева направо на одном уровне.
При обходе дерева выше корневой узел будет первым, который будет помещён в очередь, затем узел со значением 12, затем 18, 14, 16 и 20. Результатом будет:
[10,12,18,14,16,20]
