Структурирование данных с помощью JavaScript: Дерево

Структурирование данных при помощи JavaScript: Дерево Дерево — одна из наиболее часто используемых в веб-разработке структур данных. Каждый веб-разработчик, который писал HTML -код и загружал его в браузер, создавал дерево, которое называют объектной моделью документа( DOM).

Например, статья, которую вы читаете в данный момент, выводится в браузере в виде дерева. Абзацы представлены в виде элементов <p>; элементы <p> вложены в элемент <body>; а <body> вложен в элемент <html>.

Вложение данных похоже на генеалогическое древо. Элемент <html> будет родительским, <body> будет дочерним от него, а элемент <р> будет дочерним от элемента <body>.

В данной статье мы используем два разных способа прохождения дерева: поиск в глубину(DFS) и поиск в ширину(BFS). Оба данных типа прохождения подразумевают разные методы взаимодействия с деревом и включают в себя использование структур данных, которые мы рассмотрели в данной серии статей. DFS использует стек, а BFS использует очередь.

Дерево(поиск в глубину и поиск в ширину)

В информатике дерево представляет собой структуру, которая задает иерархические данные с узлами. Каждый узел дерева включает собственные данные и указатели на иные узлы.

Давайте сравним дерево со структурой организации. Эта структура имеет в себя должность верхнего уровня(корневой узел), к примеру генерального директора. Ниже данной должности располагаются иные должности, такие как вице-президент(VP).

Для представления их подчиненности мы используем стрелки, указывающие от генерального директора на вице-президента. Такие должности, как генеральный директор, будет узлами; связи, которые мы обозначили от генерального директора к вице-президенту, являются указателями. Для создания иных связей в нашей структуре организации мы повторяем этот процесс — добавляем указатели на иные узлы.

Давайте рассмотрим DOM. DOM включает элемент <html>, который будет элементом верхнего уровня(корневой узел). Этот узел указывает на элементы <head> и <body>. Этот процесс повторяется для всех узлов в DOM.

Одним из преимуществ данной конструкции будет функция вкладывать узлы: элемент <ul>, к примеру, может содержать несколько элементов <li>, вложенных в него; кроме того, каждый элемент <li> может иметь узлы <li> того же уровня.

Операции дерева

Любое дерево включает узлы, которые могут являться отдельными конструкторами дерева, и мы определим операции для обоих конструкторов: Node и Tree.

Node

  • data — здесь хранятся значения;
  • parent — указывает на родительский элемент узла;
  • children — указывает на следующий узел в списке.

Tree

  • _root — указывает на корневой узел дерева;
  • traverseDF(callback) — проходит узлы дерева при помощи способа DFS;
  • traverseBF(callback) — проходит узлы дерева при помощи способа BFS;
  • contains(data, traversal) — ищет узел дерева;
  • add(data, toData, traverse) — добавляет узел к дереву;
  • remove(child, parent) — удаляет узел дерева.

Реализация дерева

Сейчас давайте напишем код дерева.

Свойства Node

Для реализации мы сначала определим возможность с именем Node, а далее конструктор с именем Tree:

function Node(data) { this.data = data; this.parent = null; this.children = [];}

Каждый экземпляр Node включает три свойства: data, parent и children. Первое свойство используется для хранения данных, связанных с узлом. Второе свойство указывает на один узел. Третье свойство указывает на дочерние узлы.

Свойства Tree

Определим наш конструктор для Tree, который в теле включает конструктор Node:

function Tree(data) { var node = new Node(data); this._root = node;}

Tree включает две строки кода. Первая строка создает новый экземпляр Node; вторая строка назначает node в виде корневого элемента дерева.

Для определения Tree и Node требуется лишь пару строк кода. Но этого достаточно, чтобы помочь нам задать иерархические данные. Чтобы доказать это, давайте используем пару примеров для создания экземпляра Tree:

var tree = new Tree('CEO');// {data: 'CEO', parent: null, children: []}tree._root;

Благодаря parent и children мы можем добавлять узлы в виде дочерних элементов для _root, а также назначать _root в виде родительского элемента для данных узлов. Иными словами, мы можем задать иерархию данных.

Способы дерева

Мы создадим следующие пять способов:

  • traverseDF(callback);
  • traverseBF(callback);
  • contains(data, traversal);
  • add(child, parent);
  • remove(node, parent).

Поскольку для каждого способа требуется прохождение дерева, мы сначала реализуем способы, которые определяют разные типы прохождения дерева.

Способ traverseDF(callback)

Способ для прохождения дерева при помощи поиска в глубину:

Tree.prototype.traverseDF = function(callback) { // это рекурсивная и мгновенно вызываемая функцию(function recurse(currentNode) {  // шаг 2 for(var i = 0, length = currentNode.children.length; i < length; i++) {            // шаг 3 recurse(currentNode.children[i]);        }        // шаг 4 callback(currentNode);        // шаг 1    })(this._root);};

traverseDF(callback) включает настройка с именем обратного вызова. (callback) — функцию, которая будет вызываться позже в traverseDF(callback).

Тело traverseDF(callback) содержит ещё одну возможность с именем recurse . Эта рекурсивная функцию, ссылающаяся сама на себя и заканчивающаяся автоматом. Используя шаги, описанные в комментариях к возможности recurse , я опишу весь процесс, который использует recurse, чтобы пройти все дерево.

Вот данные шаги:

  • Мы вызываем recurse с корневым узлом дерева в виде аргумента. На данный момент currentNode указывает на текущий узел;
  • Входим в цикл for и повторяем его один раз для каждого дочернего узла для currentNode , начиная с первого;
  • Внутри тела цикла for вызываем рекурсивную возможность с дочерним узлом для узла currentNode . Какой конкретно это узел, зависит от текущей итерации цикла for ;
  • Когда currentNode больше не имеет в себя дочерних элементов, мы выходим из цикла for и вызываем (callback), который мы передали во время вызова traverseDF(callback) .

Шаги 2 (завершающий себя), 3 (вызывающий себя) и 4 (обратный вызов) повторяются до прохождения каждого узла дерева.

Рекурсия — это сложная тема. Для ее понимания можно поэкспериментировать с нашей текущей реализацией traverseDF(callback) и попытаться понять, как это работает.

Следующий пример демонстрирует проход по дереву при помощи traverseDF(callback) . Для этого примера я сначала создам дерево. Подход, который я буду использовать, не будет идеальным, но он работает. Лучше было бы использовать способ add(value) , который мы реализуем в шаге 4:

var tree = new Tree('one');tree._root.children.push(new Node('two'));tree._root.children[0].parent = tree;tree._root.children.push(new Node('three'));tree._root.children[1].parent = tree;tree._root.children.push(new Node('four'));tree._root.children[2].parent = tree;tree._root.children[0].children.push(new Node('five'));tree._root.children[0].children[0].parent = tree._root.children[0];tree._root.children[0].children.push(new Node('six'));tree._root.children[0].children[1].parent = tree._root.children[0];tree._root.children[2].children.push(new Node('seven'));tree._root.children[2].children[0].parent = tree._root.children[2];/*создаем следующее дерево one ├── two │   ├── five │   └── six ├── three └── four     └── seven*/

Сейчас, давайте вызовем traverseDF(callback) :

tree.traverseDF(function(node) {    console.log(node.data)});/*выводим следующие строки на консоль'five''six''two''three''seven''four''one'*/

Способ traverseBF(callback)

Способ для прохождения дерева по ширине. Разница между поиском в глубину и поиском в ширину заключается в последовательности прохождения узлов дерева. Чтобы проиллюстрировать это, давайте используем дерево, которое мы создали для реализации способа traverseDF(callback) :

/* tree one (depth: 0) ├── two (depth: 1) │   ├── five (depth: 2) │   └── six (depth: 2) ├── three (depth: 1) └── four (depth: 1)     └── seven (depth: 2) */

Сейчас давайте передадим в traverseBF(callback) тот же обратный вызов, который мы использовали для traverseDF(callback) :

tree.traverseBF(function(node) {    console.log(node.data)});/*выводим следующие строки на консоль'one''two''three''four''five''six''seven'*/

Выводим строки на консоль, и диаграмма нашего дерева покажет нам картину, отображающую принцип поиска в ширину. Начните с корневого узла; далее пройдите один уровень и посетите каждый узел этого уровня слева направо. Повторите этот процесс до тех пор, пока все уровни не будут пройдены. Реализуем программный код, при помощи которого этот пример будет работать:

Tree.prototype.traverseBF = function(callback) {    var queue = new Queue();    queue.enqueue(this._root);    currentTree = queue.dequeue();    while(currentTree){        for (var i = 0, length = currentTree.children.length; i < length; i++) {            queue.enqueue(currentTree.children[i]);        }        callback(currentTree);        currentTree = queue.dequeue();    }};

Определение traverseBF(callback) я объясню пошагово:

  • Создаем экземпляр Queue ;
  • Добавляем узел, который вызывается traverseBF(callback) для экземпляра Queue ;
  • Объявляем переменную currentNode и инициализируем ее для node , который мы только что добавили в очередь;
  • Пока currentNode указывает на узел, выполняем программный код внутри цикла while ;
  • Используем цикл for для прохождения дочерних узлов currentNode ;
  • В теле цикла for добавляем каждый дочерний узел в очередь;
  • Принимаем currentNode и передаем его в виде аргумента для callback ;
  • Устанавливаем в виде currentNode узел, удаляемый из очереди;
  • До тех пор, пока currentNode указывает на узел, должен быть пройден каждый узел дерева. Для этого повторяем шаги с 4 по 8.

Способ contains(callback, traversal)

Определим способ, который сможет нам находить конкретное значение в дереве. Чтобы использовать любой из способов прохождения дерева, я устанавливаю для contains(callback, traversal) два принимаемых аргумента: данные, которые мы ищем, и тип прохождения:

Tree.prototype.contains = function(callback, traversal) {    traversal.call(this, callback);};

В теле contains(callback, traversal) для передачи this и callback мы используем способ с именем call . Первый аргумент связывает traversal с деревом, для которого вызывается contains(callback, traversal) ; второй аргумент — это функцию, которая вызывается на каждом узле дерева.

Представьте себе, что мы хотим вывести на консоль все узлы, которые содержат данные с нечетным числом и пройти каждый узел дерева при помощи способа BFS . Для этого необходимо написать следующий код:

// дерево - это пример корневого узлаtree.contains(function(node){    if (node.data === 'two') {        console.log(node);    }}, tree.traverseBF);

Способ add(data, toData, traversal)

Сейчас у нас есть способ для поиска узла в дереве. Давайте определим способ, который сможет нам добавить узел к конкретному узлу:

Tree.prototype.add = function(data, toData, traversal) {    var child = new Node(data),        parent = null,        callback = function(node) {            if (node.data === toData) {                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.');    }};

add(data, toData, traversal) определяет три параметры. data используется для создания нового экземпляра узла. toData — используется для сравнения каждого узла в дереве. Третий настройка, traversal — это тип прохождения дерева, используемый в этом способе.

В теле add(data, toData, traversal) мы объявляем три переменные. Первая переменная, child , инициализируется как новый экземпляр Node . Вторая переменная, parent , инициализируется как null ; но позже она будет указывать на любой узел в дереве, который соответствует значению toData . Переназначение parent выполняется в третьей переменной — callback .

callback — это функцию, которая сравнивает toData со свойством data каждого узла. Если узел удовлетворяет условию оператора if , он назначается в виде parent .

Само сравнение каждого узла с toData осуществляется внутри add(data, toData, traversal) . Тип прохождения и callback должны передаваться в виде аргументов add(data, toData, traversal) .

Если parent в дереве не существует, мы помещаем child в parent.children ; мы также назначаем в виде parent родительский элемент для child , иначе выдается ошибка.

Давайте используем add(data, toData, traversal) в нашем примере:

var tree = new Tree('CEO');tree.add('VP of Happiness', 'CEO', tree.traverseBF);/*наше дерево'CEO'└── 'VP of Happiness'*/

Вот более сложный пример использования add(data, toData, traversal) :

var tree = new Tree('CEO');tree.add('VP of Happiness', 'CEO', tree.traverseBF);tree.add('VP of Finance', 'CEO', tree.traverseBF);tree.add('VP of Sadness', 'CEO', tree.traverseBF);tree.add('Director of Puppies', 'VP of Finance', tree.traverseBF);tree.add('Manager of Puppies', 'Director of Puppies', tree.traverseBF);/* дерево 'CEO' ├── 'VP of Happiness' ├── 'VP of Finance' │   ├── 'Director of Puppies' │   └── 'Manager of Puppies' └── 'VP of Sadness' */

Способ remove(data, fromData, traversal)

Для полной реализации Tree нам необходимо добавить способ с именем remove(data, fromData, traversal) . Аналогично удалению узла из DOM этот способ будет удалять узел и все его дочерние узлы:

Tree.prototype.remove = function(data, fromData, traversal) {    var tree = this,        parent = null,        childToRemove = null,        index;    var callback = function(node) {        if (node.data === fromData) {            parent = node;        }    };    this.contains(callback, traversal);    if (parent) {        index = findIndex(parent.children, data);        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;};

Так же, как add(data, toData, traversal) , способ удаления проходит все дерево, чтобы найти узел, который включает второй аргумент, равный в настоящее время fromData . Если этот узел найден, то parent указывает на него в первом операторе if .

Если parent не существует, мы выдаем ошибку. Если parent существует, мы вызываем findIndex() с parent.children и данными, которые мы хотим удалить из дочерних узлов parent. findIndex() — это вспомогательный способ, определение которого приводится ниже:

function findIndex(arr, data) {    var index;    for (var i = 0; i < arr.length; i++) {        if (arr[i].data === data) {            index = i;        }    }    return index;}

Внутри findIndex() выполняется следующая логика. Если любой из узлов в parent.children включает данные, которые соответствуют data , то переменной index присваивается значение (целое число). Если ни одно из свойств дочерних элементов не соответствует data , то index сохраняет ваше значение по умолчанию — undefined . В последней строке findIndex() мы возвращаем index .

Вернемся сейчас к remove(data, fromData, traversal) . Если значение index равно undefined , то выдается ошибка. Если определено иное значение index , мы используем его, чтобы привязать узел, который мы хотим удалить из дочернего узла parent ; мы также назначаем удаленный дочерний узел для childToRemove . В конце мы возвращаем childToRemove .

Полная реализация дерева

Наша реализация дерева сейчас будет полной:

function Node(data) {    this.data = data;    this.parent = null;    this.children = [];}function Tree(data) {    var node = new Node(data);    this._root = node;}Tree.prototype.traverseDF = function(callback) {    // это рекурсивная и мгновенно вызываемая функцию    (function recurse(currentNode) {        // шаг 2 for (var i = 0, length = currentNode.children.length; i < length; i++) {            // шаг 3 recurse(currentNode.children[i]);        }        // шаг 4 callback(currentNode);        // шаг 1    })(this._root);};Tree.prototype.traverseBF = function(callback) {    var queue = new Queue();    queue.enqueue(this._root);    currentTree = queue.dequeue();    while(currentTree){        for (var i = 0, length = currentTree.children.length; i < length; i++) {            queue.enqueue(currentTree.children[i]);        }        callback(currentTree);        currentTree = queue.dequeue();    }};Tree.prototype.contains = function(callback, traversal) {    traversal.call(this, callback);};Tree.prototype.add = function(data, toData, traversal) {    var child = new Node(data),        parent = null,        callback = function(node) {            if (node.data === toData) {                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.');    }};Tree.prototype.remove = function(data, fromData, traversal) {    var tree = this,        parent = null,        childToRemove = null,        index;    var callback = function(node) {        if (node.data === fromData) {            parent = node;        }    };    this.contains(callback, traversal);    if (parent) {        index = findIndex(parent.children, data);        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, data) {    var index;    for (var i = 0; i < arr.length; i++) {        if (arr[i].data === data) {            index = i;        }    }    return index;}

Заключение

Каждый раз, когда вам необходимо будет задать иерархическую структуру данных, вы можете легко использовать для этого дерево.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *