предисловие
Всякий раз, когда я беру короткий отпуск, я обычно размышляю и пересматриваю свои навыки, особенноПарад Лодок-Драконов. почему я пишубинарное деревостатья? На самом деле в этом участвует программистростЭта проблема. для0-3 годаизфронтенд-программистНапример, может быть мало возможностей для работы со структурами данных и алгоритмами, если только вы не пойдете на большой завод или не займетесь архитектурой. Однако многие фронтенд-инженеры, проработавшие 2-3 года, относительно знакомы с бизнес-работой и более или менее используют различные технологии, так что на данном этапе каждому программисту, имеющему погоню, стоит ли пробиться через себя? узкое место, чтобы изучить некоторые более глубокие знания? Да, самое главное, что мы должны знать на этом этапе, этоструктура данных,алгоритм,Шаблоны проектированиясоответствующие знания,Шаблоны проектированияа такжеалгоритмАвтор систематизировал его в предыдущих статьях, и те, кому это интересно, могут узнать об этом.
Далее автор систематически обобщает знания, связанные с двоичным деревом, и шаг за шагом ведет вас к реализации фактического кода.бинарное дерево поиска.
Введение в бинарные деревья
бинарное дерево (Binary tree) является важным типом древовидной структуры. Структуры данных, абстрагированные от многих практических задач, часто имеют форму бинарных деревьев, и даже обычные деревья можно легко преобразовать в бинарные деревья, а структура хранения и алгоритмы бинарных деревьев относительно просты, поэтому бинарные деревья особенно важны.Характеристика бинарного дерева состоит в том, что каждый узел может иметь не более двух поддеревьев, и есть левая и правая точки..
Реализовать дерево бинарного поиска (BST)
Перед его реализацией нам нужно проанализировать дерево BST (бинарный поиск). Для построения практичного дерева нам понадобитсяузела такжеметод,Как показано ниже:
function BinarySearchTree() {
let Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
}
let root = null;
}
Мы реализуем базовый метод бинарного дерева в соответствии со структурной организацией бинарного дерева поиска на рисунке выше.
// 插入
this.insert = function(key) {
let newNode = new Node(key);
if(root === null) {
root = newNode;
}else {
insertNode(root, newNode);
}
}
вinsertNodeЭтот метод используется для оценки логики выполнения, когда корневой узел не пуст. Конкретный код выглядит следующим образом:
function insertNode(node, newNode) {
// 如果新节点值小于当前节点值，则插入左子节点
if(newNode.key < node.key) {
if(node.left === null) {
node.left = newNode;
}else{
insertNode(node.left, newNode);
}
}else {
// 如果新节点值大于当前节点值，则插入右子节点
if(node.right === null) {
node.right = newNode;
}else {
insertNode(node.right, newNode);
}
}
}
Приведенный выше код реализованBSTЧасть логики вставки, конкретное использование выглядит следующим образом:
let tree = new BinarySearchTree()
tree.insert(19)
tree.insert(10)
tree.insert(20)
Структура двоичного дерева, созданная приведенным выше кодом, выглядит следующим образом:
обход дерева
обход деревапроцесс посещения каждого узла дерева и выполнения над ними какой-либо операции. В частности, разделены наНеупорядоченный обход,обход предварительного заказаа такжепост-порядковый обход. Далее я представлю их вам один за другим.
Неупорядоченный обход
Неупорядоченный обходэтоПосетите все узлы в порядке от меньшего к большемуМетод обхода реализуется следующим образом:
this.inOrderTraverse = function(cb) {
inOrderTraverseNode(root, cb)
}
function inOrderTraverseNode(node, cb) {
if(node !== null) {
inOrderTraverseNode(node.left, cb)
cb(node.key)
inOrderTraverseNode(node.right, cb)
}
}
Конкретный процесс обхода показан на следующем рисунке:
обход предварительного заказа
Обход предварительного порядка заключается в посещении каждого узла в порядке приоритета над узлами-потомками.. Конкретная реализация выглядит следующим образом:
this.preOrderTraverse = function(cb) {
preOrderTraverseNode(root, cb)
}
function preOrderTraverseNode(node, cb) {
if(node !== null) {
cb(node.key)
preOrderTraverseNode(node.left, cb)
preOrderTraverseNode(node.right, cb)
}
}
Конкретный обход показан на следующем рисунке:
пост-порядковый обход
Обход в обратном порядке заключается в том, чтобы сначала посетить узлы-потомки узла, а затем посетить сам узел.. Конкретная реализация выглядит следующим образом:
this.postOrderTraverse = function(cb) {
preOrderTraverseNode(root, cb)
}
function postOrderTraverseNode(node, cb) {
if(node !== null) {
postOrderTraverseNode(node.left, cb)
postOrderTraverseNode(node.right, cb)
cb(node.key)
}
}
Конкретная последовательность обхода показана на следующем рисунке:
поиск по дереву
Наш общий поиск будет иметь поиск наибольшего значения (то есть максимальное значение, минимальное значение, медианное значение) и поиск конкретных значений, а затем мы их реализуем.
Поиск определенного значения
Поиск определенного значения в дереве BST реализован следующим образом:
this.search = function(key) {
return searchNode(root, key)
}
function searchNode(ndoe, key) {
if(node === null) {
return false
}
if(key < node.key) {
return searchNode(node.left, key)
}else if(key > node.key) {
return searchNode(node.right, key)
}else {
return true
}
}
Логика реализации тоже очень проста, изучить ее можно здесь.
поиск минимального значения
Из структурных характеристик бинарного дерева мы можем обнаружить, что крайний левый конец бинарного дерева является минимальным значением, а крайний правый конец бинарного дерева — максимальным значением, поэтому мы можем найти минимальное значение путем обхода кода составляет:
this.min = function() {
return minNode(root)
}
function minNode(node) {
if(node) {
while(node && node.left !== null) {
node = node.left;
}
return node.key
}
return null
}
поиск максимального значения
Как и в случае с минимальным значением, максимальное значение также можно использовать аналогичным образом, код выглядит следующим образом:
this.max = function() {
return maxNode(root)
}
function maxNode(node) {
if(node) {
while(node && node.right !== null) {
node = node.right;
}
return node.key
}
return null
}
удалить узел
Удаление узлов в BST относительно сложно, и необходимо учитывать множество ситуаций. Конкретные ситуации следующие:
- удалить листовой узел
- Удалить узел, у которого есть левый или правый дочерний элемент
- удалить узел с двумя дочерними элементами
Разобравшись с тремя вышеперечисленными ситуациями, начинаем реализовывать логику удаления узлов:
this.remove = function(key) {
root = removeNode(root, key)
}
function removeNode(node, key) {
if(node === null) {
return null
}
if(key < node.key) {
node.left = removeNode(node.left, key)
return node
}else if(key > node.key) {
node.right = removeNode(node.right, key)
return node
}else {
// 一个叶节点
if(node.left === null && node.right === null) {
node = null;
return node
}
// 只有一个子节点的节点
if(node.left === null) {
node = node.right;
return node
}else if(node.right === null) {
node = node.left;
return node
}
// 有两个子节点的节点情况
let aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node
}
}
function findMinNode(node) {
if(node) {
while(node && node.left !== null) {
node = node.left;
}
return node
}
return null
}
На данный момент реализовано полное бинарное дерево поиска, разве это не большое достижение? Исходный код этой статьи выложен на гитхабе автора, и заинтересованные друзья могут его пощупать.
Применение бинарного дерева
Двоичные деревья обычно можно использовать для:
- связующая древовидная структура
- алгоритм поиска в базе данных
- Использование шифрования бинарного дерева
- Рассчитать размер всех файлов в каталоге и подкаталогах,
- распечатать структурированный документ
- Используется в играх для планирования пути и т. д.
расширять
фактическиДеревоСуществует много типов деревьев, и эти различные типы деревьев имеют широкий спектр применения в компьютерах, например,красно-черное дерево,B-дерево,Самобалансирующееся бинарное дерево поиска,дерево разделов пространства,хэш-дерево,R-дерево ГильбертаПодождите, если вам интересны эти деревья, вы можете их подробно изучить, ведь это очень поможет вашему будущему техническому видению.
наконец
Если вы хотите узнать большеИнтерфейсные навыки,настоящий бойа такжемаршрут обучения, Добро пожаловать в нашу техническую группу в общедоступном аккаунте «Интересный интерфейс», чтобы вместе учиться и обсуждать, а также вместе исследовать границы интерфейса.
использованная литература
бинарное дерево -baike.baidu.com/item/бинарное дерево
больше рекомендаций
- Когда серверная часть выдает вам 100 000 единиц данных за один раз, что вам как фронтенд-инженеру следует делать?
- Краткое изложение нескольких распространенных алгоритмов сортировки и алгоритмов поиска, необходимых программистам
- Реализовать проект полного стека CMS от 0 до 1 на основе nodeJS (включено)
- Реализовать проект полного стека CMS от 0 до 1 на основе nodeJS (средний) (включая исходный код)
- Vue и React для проекта полного стека CMS (часть 2) (включая исходный код)
- Научу разрабатывать библиотеку компонентов на основе vue с нуля до единицы
- Научу строить компонентную систему фронтенд команды от 0 до 1 (обязательно для продвинутых и продвинутых)