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

2015-10-20 0 ∞ 3

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

Заключение

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

код не рабочий.
не определена функция Queue().

Ответить

Markin D.

Кроме того, в описании add(data, toData, traversal) по коду мы проверяем if (parent), а в комментариях - "Если parent в дереве не существует, мы помещаем child в parent.children"

В комментариях к traverseBF(callback) пишется о currentNode, в то время как в коде используется currentTree - это вводит в заблуждение.