Russian (Pусский) translation by Masha Kolesnikova (you can also view the original English article)
Деревья являются одной из наиболее часто используемых структур данных в веб-разработке. Это утверждение справедливо как для разработчиков, так и для пользователей. Каждый веб-разработчик, который писал HTML и загружал его в веб-браузер, создавал дерево, которое называется Document Object Model (DOM). Каждый пользователь Интернета, который, в свою очередь, потреблял информацию в Интернете, получал ее в виде дерева - DOM.
Теперь, вот кульминация: статья, которую вы читаете в данный момент, отображается в вашем браузере как дерево! Абзац, который вы читаете, представлен как текст в элементе <p>; Элемент <p> вложен внутри элемента <body>; И элемент <body> вложен внутри элемента <html>.
Вложение данных аналогично генеалогическому дереву. Элемент <html> является родителем, элемент <body> является дочерним, а элемент <p> является дочерним элементом элемента <body>. Если эта аналогия дерева кажется вам полезной, то вам определенно понравится идея того, что во время нашей реализации дерева будет использовано еще больше аналогий.
В этой статье мы создадим дерево, используя два разных метода обхода дерева: поиск по глубине (DFS) и поиск по ширине (BFS). (Если слово обход незнакомо вам, считайте его посещением каждого узла дерева.) Оба этих типа обхода выделяют различные способы взаимодействия с деревом; Более того, оба путешествия включают использование структур данных, которые мы рассмотрели в этой серии. DFS использует стек, а BFS использует очередь для посещения узлов. Это круто!
Дерево (поиск по глубине и поиск по ширине)
В информатике дерево представляет собой структуру данных, имитирующую иерархические данные с узлами. Каждый узел дерева содержит свои собственные данные и указатели на другие узлы.
Терминология узлов и указателей может быть новой для некоторых читателей, поэтому давайте опишем их далее с помощью аналогии. Давайте сравним дерево с графиком организации. График имеет позицию верхнего уровня (корневой узел), например, CEO. Прямо под этой позицией находятся другие должности, такие как вице-президент (VP).
Чтобы представить это соотношение, мы используем стрелки, указывающие от генерального директора на VP. Позиция, такая как генеральный директор, является узлом; Отношения, которые мы создаем от генерального директора к VP, являются указателями. Чтобы создать больше связей в нашем графике, мы просто повторяем этот процесс - у нас есть узел, указывающий на другой узел.
На концептуальном уровне я надеюсь, что узлы и указатели вам и так понятны. На практическом уровне мы можем воспользоваться более техническим примером. Рассмотрим DOM. DOM имеет элемент <html> в качестве позиции верхнего уровня (корневой узел). Этот узел указывает на элемент <head> и <body>. Этот процесс повторяется для всех узлов в DOM.
Красота этого дизайна заключается в способности встраивать узлы: элемент <ul>, например, может содержать много элементов <li>, вложенных в него; Кроме того, каждый элемент <li> может иметь узлы-соседи <li>. Это странно, но забавно и верно!
Операции над деревом
Поскольку каждое дерево содержит узлы, которые могут быть отдельным конструктором из дерева, мы будем описывать операции для обоих конструкторов: Node и Tree.
Узел
-
dataхранит значение. -
parentуказывает на родительский элемент узла. -
childrenуказывают на следующий узел в списке.
Дерево
-
_rootуказывает на корневой узел дерева. -
traverseDF(callback)обходит узлы дерева с DFS. -
traverseBF(callback)перемещает узлы дерева с BFS. -
contains(data, traversal)ищет узел в дереве. -
add(data, toData, traverse)добавляет узел в дерево. -
remove(child, parent)удаляет узел из дерева.
Реализация дерева
Теперь давайте напишем код для дерева!
Свойства узла
Для нашей реализации мы сначала определим функцию с именем Node, а затем конструктор с именем Tree.
1 |
function Node(data) { |
2 |
this.data = data; |
3 |
this.parent = null; |
4 |
this.children = []; |
5 |
}
|
Каждый экземпляр узла содержит три свойства: data, parent и children. Первое свойство содержит данные, связанные с узлом. Второе свойство указывает на один узел. Третье свойство указывает на множество дочерних узлов.
Свойства дерева
Теперь давайте определим наш конструктор для Tree, который включает в себя конструктор Node в его определении:
1 |
function Tree(data) { |
2 |
var node = new Node(data); |
3 |
this._root = node; |
4 |
}
|
Tree содержит две строки кода. Первая строка создает новый экземпляр Node; Вторая строка назначает node как корень дерева.
Определения Tree и Node требуют только лишь нескольких строк кода. Однако этих строк достаточно, чтобы помочь нам имитировать иерархические данные. Чтобы доказать этот момент, давайте использовать некоторые примеры для создания экземпляра Tree (и, косвенно, Node).
1 |
var tree = new Tree('CEO'); |
2 |
|
3 |
// {data: 'CEO', parent: null, children: []}
|
4 |
tree._root; |
Благодаря существованию parent и children, мы можем добавлять узлы как дочерние элементы _root, а также присваивать _root родителям этих узлов. Другими словами, мы можем имитировать создание иерархических данных.
Методы дерева
Затем мы создадим следующие пять методов:
Tree
traverseDF(callback)traverseBF(callback)contains(data, traversal)add(child, parent)remove(node, parent)
Поскольку каждый метод дерева требует от нас обхода дерева, мы сначала реализуем методы, которые определяют разные типы обхода дерева. (Обход дерева - это формально посещение каждого узла дерева.)
1 из 5: traverseDF(callback)
Этот метод обходит дерево с поиском в глубину.
1 |
Tree.prototype.traverseDF = function(callback) { |
2 |
|
3 |
// this is a recurse and immediately-invoking function
|
4 |
(function recurse(currentNode) { |
5 |
// step 2
|
6 |
for (var i = 0, length = currentNode.children.length; i < length; i++) { |
7 |
// step 3
|
8 |
recurse(currentNode.children[i]); |
9 |
}
|
10 |
|
11 |
// step 4
|
12 |
callback(currentNode); |
13 |
|
14 |
// step 1
|
15 |
})(this._root); |
16 |
|
17 |
};
|
traverseDF(callback) имеет параметр с именем callback. Если это непонятно из имени, считается, что callback является функцией, которая будет называться позже в traverseDF(callback).
Тело traverseDF(callback) включает в себя другую функцию с именем recurse. Эта функция является рекурсивной функцией! Другими словами, она сама себя вызывает. Используя шаги, упомянутые в комментариях recurse, я опишу общий процесс, который recurse использует для перемещения по всему дереву.
Вот эти шаги:
- Сразу вызовите
recurseс корневым узлом дерева в качестве аргумента. В настоящий моментcurrentNodeуказывает на текущий узел. - Входим в цикл
forи проходимся по каждому элементуcurrentNode, начиная с первого дочернего элемента. - Внутри тела цикла
forвызывается recurse с дочерним элементомcurrentNode. Каждый конкретный дочерний элемент зависит от текущей итерации циклаfor. - Когда
currentNodeбольше не имеет дочерних элементов, мы выходим из циклаforи вызываемcallback, который мы передали во время вызоваtraverseDF(callback).
Шаги 2 (выход из функции), 3 (вызов себя) и 4 (callback) повторяются до тех пор, пока мы не пройдем каждый узел дерева.
Рекурсия - очень трудная тема для обучения и требует подробного объяснения. Поскольку объяснение рекурсии не в центре внимания этой статьи, основное внимание уделяется внедрению дерева. Я предлагаю, чтобы все читатели, не обладающие хорошим пониманием рекурсии, сделали следующие две вещи.
Во-первых, экспериментируйте с нашей текущей реализацией traverseDF(callback) и попытайтесь понять, как это работает. Во-вторых, если вы хотите, чтобы я написал статью о рекурсии, пожалуйста, запросите ее в комментариях к этой статье.
В следующем примере показано, как дерево будет пройдено через traverseDF(callback). Чтобы обойти дерево, я создам его в следующем примере. Подход, который я буду использовать в данный момент, не идеален, но он работает. Лучшим подходом было бы использовать add(value), который мы реализуем на шаге 4 из 5.
1 |
var tree = new Tree('one'); |
2 |
|
3 |
tree._root.children.push(new Node('two')); |
4 |
tree._root.children[0].parent = tree; |
5 |
|
6 |
tree._root.children.push(new Node('three')); |
7 |
tree._root.children[1].parent = tree; |
8 |
|
9 |
tree._root.children.push(new Node('four')); |
10 |
tree._root.children[2].parent = tree; |
11 |
|
12 |
tree._root.children[0].children.push(new Node('five')); |
13 |
tree._root.children[0].children[0].parent = tree._root.children[0]; |
14 |
|
15 |
tree._root.children[0].children.push(new Node('six')); |
16 |
tree._root.children[0].children[1].parent = tree._root.children[0]; |
17 |
|
18 |
tree._root.children[2].children.push(new Node('seven')); |
19 |
tree._root.children[2].children[0].parent = tree._root.children[2]; |
20 |
|
21 |
/*
|
22 |
|
23 |
creates this tree
|
24 |
|
25 |
one
|
26 |
├── two
|
27 |
│ ├── five
|
28 |
│ └── six
|
29 |
├── three
|
30 |
└── four
|
31 |
└── seven
|
32 |
|
33 |
*/
|
Теперь давайте обратимся к traverseDF(callback).
1 |
tree.traverseDF(function(node) { |
2 |
console.log(node.data) |
3 |
});
|
4 |
|
5 |
/*
|
6 |
|
7 |
logs the following strings to the console
|
8 |
|
9 |
'five'
|
10 |
'six'
|
11 |
'two'
|
12 |
'three'
|
13 |
'seven'
|
14 |
'four'
|
15 |
'one'
|
16 |
|
17 |
*/
|
2 из 5: traverseBF(callback)
Этот метод использует поиск по ширине для перемещения по дереву.
Разница между поиском в глубину и поиском в ширину включает в себя последовательность, в которой посещаются узлы дерева. Чтобы проиллюстрировать этот момент, давайте используем дерево, которое мы создали из traverseDF(callback).
1 |
/*
|
2 |
|
3 |
tree
|
4 |
|
5 |
one (depth: 0)
|
6 |
├── two (depth: 1)
|
7 |
│ ├── five (depth: 2)
|
8 |
│ └── six (depth: 2)
|
9 |
├── three (depth: 1)
|
10 |
└── four (depth: 1)
|
11 |
└── seven (depth: 2)
|
12 |
|
13 |
*/
|
Теперь давайте пройдем traverseBF(callback) тот же обратный вызов, который мы использовали для traverseDF(callback).
1 |
tree.traverseBF(function(node) { |
2 |
console.log(node.data) |
3 |
});
|
4 |
|
5 |
/*
|
6 |
|
7 |
logs the following strings to the console
|
8 |
|
9 |
'one'
|
10 |
'two'
|
11 |
'three'
|
12 |
'four'
|
13 |
'five'
|
14 |
'six'
|
15 |
'seven'
|
16 |
|
17 |
*/
|
Логи с консоли и диаграммы нашего дерева показывают образец поиска в ширину. Начните с корневого узла; Затем пройдите одну глубину и посетите каждый узел на этой глубине слева направо. Повторяйте этот процесс до тех пор, пока не будет больше глубины для перемещения.
Поскольку у нас есть концептуальная модель поиска в ширину, давайте теперь реализуем код, который заставит наш пример работать.
1 |
Tree.prototype.traverseBF = function(callback) { |
2 |
var queue = new Queue(); |
3 |
|
4 |
queue.enqueue(this._root); |
5 |
|
6 |
currentTree = queue.dequeue(); |
7 |
|
8 |
while(currentTree){ |
9 |
for (var i = 0, length = currentTree.children.length; i < length; i++) { |
10 |
queue.enqueue(currentTree.children[i]); |
11 |
}
|
12 |
|
13 |
callback(currentTree); |
14 |
currentTree = queue.dequeue(); |
15 |
}
|
16 |
};
|
Наше определение traverseBF(callback) содержит много логики. По этой причине я объясню логику в управляемых шагах:
- Создайте экземпляр
Queue. - Добавьте узел, который вызвал
traverseBF(callback)к экземпляруQueue. - Объявите переменную с именем
currentNodeи инициализируйте ее кnode, который мы только что добавили в нашу очередь. - Пока
currentNodeуказывает на узел, выполните код внутри циклаwhile. - Используйте цикл
forдля итерации по дочерним элементамcurrentNode. - Внутри тела цикла
forдобавьте каждый дочерний элемент в очередь. - Возьмите
currentNodeи передайте его как аргумент вcallback. - Перенесите
currentNodeна удаляемый узел из очереди. - Пока
currentNodeне указывает на узел - каждый узел в дереве был посещен - повторите шаги с 4 по 8.
3 из 5: contains(callback, traversal)
Давайте определим метод, который позволит нам искать конкретное значение в нашем дереве. Чтобы использовать любой из наших методов обхода дерева, я определил contains(callback, traversal) таким образом, чтобы он принимал два аргумента: данные для поиска и тип обхода.
1 |
Tree.prototype.contains = function(callback, traversal) { |
2 |
traversal.call(this, callback); |
3 |
};
|
В теле contains(callback, traversal), мы используем метод с именем call для передачи this и callback. Первый аргумент связывает traversal с деревом которые вызывало contains(callback, traversal); второй аргумент - это функция, которая вызывается на каждом узле нашего дерева.
Представьте себе, что мы хотим отобразить в консоли любые узлы, содержащие данные с нечетным числом, и обойти при этом каждый узел нашего дерева с помощью BFS. Это код, который мы напишем:
1 |
// tree is an example of a root node
|
2 |
tree.contains(function(node){ |
3 |
if (node.data === 'two') { |
4 |
console.log(node); |
5 |
}
|
6 |
}, tree.traverseBF); |
4 из 5: add(data, toData, traversal)
Теперь у нас есть метод поиска определенного узла в нашем дереве. Давайте теперь определим метод, который позволит нам добавить узел к определенному узлу.
1 |
Tree.prototype.add = function(data, toData, traversal) { |
2 |
var child = new Node(data), |
3 |
parent = null, |
4 |
callback = function(node) { |
5 |
if (node.data === toData) { |
6 |
parent = node; |
7 |
}
|
8 |
};
|
9 |
|
10 |
this.contains(callback, traversal); |
11 |
|
12 |
if (parent) { |
13 |
parent.children.push(child); |
14 |
child.parent = parent; |
15 |
} else { |
16 |
throw new Error('Cannot add node to a non-existent parent.'); |
17 |
}
|
18 |
};
|
add(data, toData, traversal) определяет три параметра. Первый параметр, data, используется для создания нового экземпляра Node. Второй параметр toData используется для сравнения с каждым узлом в дереве. Третий параметр, traversal, является типом обхода дерева, используемого в этом методе.
В теле add(data, toData, traversal) мы объявляем три переменные. Первая переменная, child инициализируется как новый экземпляр Node. Вторая переменная, parent, инициализируется как null; Но позже она укажет на любой узел в дереве, который соответствует значению toData. Перераспределение parent происходит в третьей переменной, которую мы объявляем - callback.
callback - это функция, которая сравнивает toData с данными data каждого узла. Если оператор if возвращает значение true, то parent назначается узлу, который сравнивался в инструкции if.
Фактическое сравнение каждого узла с toData происходит в contains(callback, traversal). Тип обхода и callback должны быть переданы в качестве аргументов contains(callback, traversal).
Наконец, если parent существует в дереве, мы помещаем child в parent.children; Мы также назначаем parent родительскому элементу child. Иначе мы выкидываем ошибку.
Давайте воспользуемся add(data, toData, traversal) на примере:
1 |
var tree = new Tree('CEO'); |
2 |
|
3 |
tree.add('VP of Happiness', 'CEO', tree.traverseBF); |
4 |
|
5 |
/*
|
6 |
|
7 |
our tree
|
8 |
|
9 |
'CEO'
|
10 |
└── 'VP of Happiness'
|
11 |
|
12 |
*/
|
Вот более сложный пример для add(addData, toData, traversal):
1 |
var tree = new Tree('CEO'); |
2 |
|
3 |
tree.add('VP of Happiness', 'CEO', tree.traverseBF); |
4 |
tree.add('VP of Finance', 'CEO', tree.traverseBF); |
5 |
tree.add('VP of Sadness', 'CEO', tree.traverseBF); |
6 |
|
7 |
tree.add('Director of Puppies', 'VP of Finance', tree.traverseBF); |
8 |
tree.add('Manager of Puppies', 'Director of Puppies', tree.traverseBF); |
9 |
|
10 |
/*
|
11 |
|
12 |
tree
|
13 |
|
14 |
'CEO'
|
15 |
├── 'VP of Happiness'
|
16 |
├── 'VP of Finance'
|
17 |
│ ├── 'Director of Puppies'
|
18 |
│ └── 'Manager of Puppies'
|
19 |
└── 'VP of Sadness'
|
20 |
|
21 |
*/
|
5 из 5: remove(data, fromData, traversal)
Чтобы завершить нашу реализацию Tree, мы добавим метод с именем remove(data, fromData, traversal). Подобно удалению узла из DOM, этот метод удалит узел и все его дочерние элементы.
1 |
Tree.prototype.remove = function(data, fromData, traversal) { |
2 |
var tree = this, |
3 |
parent = null, |
4 |
childToRemove = null, |
5 |
index; |
6 |
|
7 |
var callback = function(node) { |
8 |
if (node.data === fromData) { |
9 |
parent = node; |
10 |
}
|
11 |
};
|
12 |
|
13 |
this.contains(callback, traversal); |
14 |
|
15 |
if (parent) { |
16 |
index = findIndex(parent.children, data); |
17 |
|
18 |
if (index === undefined) { |
19 |
throw new Error('Node to remove does not exist.'); |
20 |
} else { |
21 |
childToRemove = parent.children.splice(index, 1); |
22 |
}
|
23 |
} else { |
24 |
throw new Error('Parent does not exist.'); |
25 |
}
|
26 |
|
27 |
return childToRemove; |
28 |
};
|
Подобно add(data, toData, traversal), метод remove обходит дерево, чтобы найти узел, содержащий второй аргумент fromData. Если этот узел найден, то parent указывает на него.
В этот момент мы достигаем нашего первого if выражения. Если parent не существует, мы выдаем ошибку. Если parent существует, мы вызываем findIndex() с parent.children и данные, которые мы хотим удалить из дочерних узлов parent. (findIndex() - вспомогательный метод, который я определил ниже.)
1 |
function findIndex(arr, data) { |
2 |
var index; |
3 |
|
4 |
for (var i = 0; i < arr.length; i++) { |
5 |
if (arr[i].data === data) { |
6 |
index = i; |
7 |
}
|
8 |
}
|
9 |
|
10 |
return index; |
11 |
}
|
Внутри findIndex() происходит следующая логика. Если какой-либо из узлов в parent.children содержит данные, соответствующие data, переменной index присваивается целое число. Если ни одно из данных у дочерних элементов не соответствует data, index сохраняет значение по умолчанию undefined. В последней строке findIndex() мы возвращаем index.
Теперь мы возвращаемся назад к remove(data, fromData, traversal). Если index равен undefined, возникает ошибка. Если index определен, мы используем его для сращивания узла, который хотим удалить из дочерних элементов parent; Мы также присваиваем удаленный дочерний элемент переменной childToRemove.
Наконец, мы возвращаем childToRemove.
Полная реализация дерева
Наша реализация Tree завершена. Взгляните - мы многое сделали:
1 |
function Node(data) { |
2 |
this.data = data; |
3 |
this.parent = null; |
4 |
this.children = []; |
5 |
}
|
6 |
|
7 |
function Tree(data) { |
8 |
var node = new Node(data); |
9 |
this._root = node; |
10 |
}
|
11 |
|
12 |
Tree.prototype.traverseDF = function(callback) { |
13 |
|
14 |
// this is a recurse and immediately-invoking function
|
15 |
(function recurse(currentNode) { |
16 |
// step 2
|
17 |
for (var i = 0, length = currentNode.children.length; i < length; i++) { |
18 |
// step 3
|
19 |
recurse(currentNode.children[i]); |
20 |
}
|
21 |
|
22 |
// step 4
|
23 |
callback(currentNode); |
24 |
|
25 |
// step 1
|
26 |
})(this._root); |
27 |
|
28 |
};
|
29 |
|
30 |
Tree.prototype.traverseBF = function(callback) { |
31 |
var queue = new Queue(); |
32 |
|
33 |
queue.enqueue(this._root); |
34 |
|
35 |
currentTree = queue.dequeue(); |
36 |
|
37 |
while(currentTree){ |
38 |
for (var i = 0, length = currentTree.children.length; i < length; i++) { |
39 |
queue.enqueue(currentTree.children[i]); |
40 |
}
|
41 |
|
42 |
callback(currentTree); |
43 |
currentTree = queue.dequeue(); |
44 |
}
|
45 |
};
|
46 |
|
47 |
Tree.prototype.contains = function(callback, traversal) { |
48 |
traversal.call(this, callback); |
49 |
};
|
50 |
|
51 |
Tree.prototype.add = function(data, toData, traversal) { |
52 |
var child = new Node(data), |
53 |
parent = null, |
54 |
callback = function(node) { |
55 |
if (node.data === toData) { |
56 |
parent = node; |
57 |
}
|
58 |
};
|
59 |
|
60 |
this.contains(callback, traversal); |
61 |
|
62 |
if (parent) { |
63 |
parent.children.push(child); |
64 |
child.parent = parent; |
65 |
} else { |
66 |
throw new Error('Cannot add node to a non-existent parent.'); |
67 |
}
|
68 |
};
|
69 |
|
70 |
Tree.prototype.remove = function(data, fromData, traversal) { |
71 |
var tree = this, |
72 |
parent = null, |
73 |
childToRemove = null, |
74 |
index; |
75 |
|
76 |
var callback = function(node) { |
77 |
if (node.data === fromData) { |
78 |
parent = node; |
79 |
}
|
80 |
};
|
81 |
|
82 |
this.contains(callback, traversal); |
83 |
|
84 |
if (parent) { |
85 |
index = findIndex(parent.children, data); |
86 |
|
87 |
if (index === undefined) { |
88 |
throw new Error('Node to remove does not exist.'); |
89 |
} else { |
90 |
childToRemove = parent.children.splice(index, 1); |
91 |
}
|
92 |
} else { |
93 |
throw new Error('Parent does not exist.'); |
94 |
}
|
95 |
|
96 |
return childToRemove; |
97 |
};
|
98 |
|
99 |
function findIndex(arr, data) { |
100 |
var index; |
101 |
|
102 |
for (var i = 0; i < arr.length; i++) { |
103 |
if (arr[i].data === data) { |
104 |
index = i; |
105 |
}
|
106 |
}
|
107 |
|
108 |
return index; |
109 |
}
|
Вывод
Деревья моделируют иерархические данные. Большая часть окружающего нас мира напоминает этот тип иерархии, как например веб-страницы и наши семьи. Каждый раз, когда вам нужно структурировать данные в виде иерархии, подумайте об использовании дерева.
By
