Структурирование данных с помощью 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;
}
Заключение
Каждый раз, когда вам нужно будет задать иерархическую структуру данных, вы можете использовать для этого дерево.