Реализовать дерево в JavaScript
Поработав с сайтами, которые ежегодно посещают более 50 миллиардов веб-сайтов с Higglo Digital, я пишу на технические темы и учу инженеров иметь прочную основу, которая поможет им продвинуться по карьерной лестнице. Я также создаю потрясающие продукты для цифровых кочевников — посмотрите!
Дерево — это широко используемая структура данных в информатике, состоящая из набора узлов, организованных иерархическим образом. У каждого узла в дереве есть родительский узел, за исключением корневого узла, у которого нет родителя. Узлы, которые подключены к родительскому узлу, называются дочерними узлами, а родительский узел называется родительским узлом.
В JavaScript мы можем реализовать дерево с помощью объектов, где каждый узел представляет собой объект с такими свойствами, как значение, лево и право. Свойство left представляет левый дочерний узел, а свойство right представляет правый дочерний узел.
Существуют различные типы деревьев, такие как бинарные деревья, бинарные деревья поиска и красно-черные деревья.
Бинарное дерево — это дерево, в котором каждый узел имеет не более двух дочерних узлов. Двоичное дерево поиска — это особый тип двоичного дерева, в котором значение каждого левого дочернего узла меньше значения его родительского узла, а значение каждого правого дочернего узла больше значения его родительского узла. Это свойство называется свойством бинарного дерева поиска и позволяет нам быстро искать определенное значение в дереве.
Красно-черное дерево — это самобалансирующееся бинарное дерево поиска, что означает, что дерево автоматически корректирует свою структуру для поддержания баланса. Это гарантирует, что дерево остается эффективным с точки зрения операций поиска и вставки.
Одной из основных операций, выполняемых с деревом, является обход, то есть процесс посещения каждого узла дерева. Существует три основных типа обхода дерева: предварительный порядок, порядок и пост-порядок.
- Обход в предварительном порядке сначала посещает корневой узел, затем левый дочерний узел, а затем правый дочерний узел.
- Обход по порядку сначала посещает левый дочерний узел, затем корневой узел, а затем правый дочерний узел.
- Обход в обратном порядке сначала посещает левый дочерний узел, затем правый дочерний узел, а затем корневой узел.
Другой распространенной операцией в дереве является вставка, то есть процесс добавления нового узла в дерево. В бинарном дереве поиска нам нужно убедиться, что свойство бинарного дерева поиска сохраняется после вставки нового узла.
Удаление — еще одна операция, выполняемая над деревом. В бинарном дереве поиска нам нужно убедиться, что дерево остается сбалансированным после удаления узла.
Вот простая реализация структуры данных Tree в JavaScript:
class TreeNode { constructor(value) { this.value = value; this.children = []; } addChild(value) { const newNode = new TreeNode(value); this.children.push(newNode); return newNode; } } class Tree { constructor() { this.root = null; } traverseDF(callback) { (function recurse(currentNode) { for (let i = 0, length = currentNode.children.length; i < length; i++) { recurse(currentNode.children[i]); } callback(currentNode); })(this.root); } traverseBF(callback) { const queue = [this.root]; let currentNode = queue.shift(); while (currentNode) { for (let i = 0, length = currentNode.children.length; i < length; i++) { queue.push(currentNode.children[i]); } callback(currentNode); currentNode = queue.shift(); } } contains(callback, traversal) { traversal.call(this, callback); } add(value, toNodeValue, traversal) { let child = new TreeNode(value), parent = null, callback = function(node) { if (node.value === toNodeValue) { parent = node; } }; this.contains(callback, traversal); if (parent) { parent.children.push(child); child.parent = parent; } else { throw new Error('Cannot add node to a non-existent parent.'); } } remove(nodeValue, fromNodeValue, traversal) { let tree = this, parent = null, childToRemove = null, index; let callback = function(node) { if (node.value === fromNodeValue) { parent = node; } }; this.contains(callback, traversal); if (parent) { index = findIndex(parent.children, nodeValue); if (index === undefined) { throw new Error('Node to remove does not exist.'); } else { childToRemove = parent.children.splice(index, 1); } } else { throw new Error('Parent does not exist.'); } return childToRemove; } } function findIndex(arr, value) { let index; for (let i = 0; i < arr.length; i++) { if (arr[i].value === value) { index = i; } } return index; }
Эта реализация включает класс TreeNode
, представляющий один узел в дереве, и класс Tree
, представляющий само дерево. Класс Tree
включает в себя методы обхода дерева в порядке глубины или ширины, добавления и удаления узлов, а также поиска узлов в дереве.
В заключение, древовидная структура данных является важной структурой данных в информатике и широко используется в различных приложениях. Это позволяет нам эффективно хранить и получать доступ к данным в иерархическом порядке и полезно в различных операциях, таких как поиск, вставка и удаление.
Я основал Higglo Digital, и мы можем помочь вашему бизнесу сокрушить веб-игры с помощью отмеченного наградами веб-сайта и передовой цифровой стратегии. Если вы хотите увидеть красиво оформленный веб-сайт, загляните к нам.
Я также создал Wanderlust Extension, чтобы открывать для себя самые красивые места по всему миру с тщательно подобранным контентом. Проверьте это!