Реализовать дерево в 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, чтобы открывать для себя самые красивые места по всему миру с тщательно подобранным контентом. Проверьте это!