Деревья
Структура
Дерево является графом у которого есть единственный узел, называемый корнем. Рёбрами он связан с другими узлами (непосредственными потомками корня). Эти потомки, в свою очередь, имеют собственных потомков и т.д. Перемещаясь от корня по узлам дерева, можно попасть в любой узел, причём единственным образом. Деревья широко используются в различных задачах поиска решений. В этом документе обсуждаются способы визуального представления деревьев. К алгоритмам обработки деревьев мы вернёмся в дальнейшем.
Дерево будем задавать объектом: { nm, ar }, где nm - имя узла, а ar - массив ветвей (ближайших потомков). Так, следующий объект tree описывает бинарное дерево глубины 2, изображенное справа на рисунке:
var tree = {
nm:"root",
ar:[
{nm: "b1", ar:[ {nm:"a"}, {nm:"b"}] },
{nm: "b2", ar:[ {nm:"c"}, {nm:"d"}] },
]
};
JSON.stringify
Tree.getJSON = function (tr)
{
return JSON.stringify(tr).replace(/"(\w+)":/g, "$1:");
}
replace
Функция getJSON является статической и не требует создания экземпляра класса Tree при помощи new. Можно просто написать: document.write( Tree.getJSON(tree) ), что даст строку:
В классе Tree все статические функции продублированы как "динамические", при помощи указателя prototype:
function Tree(tr)
{
if(tr){
this.nm = tr.nm;
this.ar = tr.ar;
}
}
Tree.prototype.getJSON = function ()
{
return Tree.getJSON(this);
}
Таким образом, класс Tree может в статическом варианте обрабатывать структуры подобные tree,
а в динамическом - хранить дерево "внутри себя".
Например, дерево в JSON-формате можно вставить в документ также так: var t = new Tree(tree); document.write( t.getJSON() ).
Вывод дерева
При работе с деревьями естественно использовать рекурсивные методы. Напишем, например, функцию вывода дерева в "функциональном" виде, которая для структуры tree, приведенной выше, выдаст строку: :
Небольшие изменения этой функции, позволяют вывести дерево в виде списка html (функция Tree.getUL(tr), выше, справа). Ещё две функции Tree.getGIF(tr) (в виде папочек) и Tree.getSVG(tr) (традиционное преставление) будут рассмотрены позднее.Копирование деревьев
Присвоение деревьев, как и любых объектов, проводится по ссылке. Чтобы получить независимую копию дерева, напишем незамысловатую функцию:
Tree.copy = function (tr)
{
return JSON.parse(JSON.stringify(tr));
}
Теперь для следующего кода
var tree1 = { nm:"root", ar:[ {nm: "b1"}, {nm: "b2"} ] };
var tree2 = tree1; // тоже дерево (по ссылке)
var tree3 = Tree.copy(tree1); // независимая копия
tree1.ar[0].nm = "b3"; // меняем имя узла потомка
document.write(Tree.getFun(tree1), '; ', Tree.getFun(tree2),' и ', Tree.getFun(tree3));
получим:
.
JSON.parse
Генерация деревьев
Для тестирования различных алгоритмов, необходимо создавать деревья "на лету".
Напишем функцию, генерящую случайные деревья:
Рисовать ящики:
Функция Tree.rand принимает на вход 3 параметра: depth - максимальная глубина, branches - максимальное число ветвей и cut - вероятность обрыва ветки (0 < cut < 1). При каждом рекурсивном вызове depth уменьшается, пока не станет равным нулю:
Tree.rand = function (depth, branches, cut)
{
if(this.count===undefined) // статическая переменная
this.count = -1; // для нумерации узлов
this.count++; // следующий узел
if(depth < 1 || Math.random() < cut) // обрываем рост дерева по глубине
return { nm: this.count}; // или по вероятности 0 < cut < 1
var nm = this.count; // запоминаем (потомки увеличат)
var ar = new Array(1+Math.floor(Math.random()*branches));
for(var i=0; i < ar.length; i++) // рекурсивно для потомков
ar[i] = this.rand(depth-1, branches, cut);
return { nm:nm, ar:ar };
}
Получить максимальную глубину дерева tr и количество узлов можно при помощи следующих рекурсивных функций:
В качестве забавы, найдём среднюю глубину случайного дерева и среднее число узлов на нём (нажмите кнопку start):
Стоит попробовать вычислить эти параметры теоретически.
Деревья как функции
В ряде случаев удобнее задавать дерево не структурой, а строкой, подобной . Имена таких вложенных функций являются узлами дерева, а их аргументы - потомками этих узлов. При этом справедлива следующая грамматика:
NODE :- NAME(LIST) | NAME // узел - это функция или имя листа LIST :- NODE,LIST | NODE // список, это множество узлов через запятуюГрамматика является набором правил порождения синтаксически верных выражений. Она может выдать выражение f(x,g(h(a),z)), но не приведёт к синтаксически неверной записи типа f(,),(g(h,(a,z). В первой строке утверждается, что узлом дерева NODE может быть имя NAME (для терминальных узлов) или функция NAME(LIST) для нетеминальных. Эти две возможности перечисляются через вертикальную черту. Вторая строка - определение списка аргументов функции. При этом правило LIST :- NODE,LIST содержит в себе рекурсию (список - это узел NODE, после которого через запятую снова идёт список).
Функция Tree.parse(st) парсит строку st, выдавая на входе дерево в виде структуры. В ней введена статическая переменная pos указателя на текущее положение в анализируемой строке и вызывается первое грамматическое правило:
Tree.parse = function (st)
{
this.pos = 0; // статическая перемнная положение в st
return Tree.parseNODE(st);
}
Напишем функции для каждого элемента грамматики.
Функция Tree.parseNODE возвращает дерево { nm, ar }.
Функция Tree.parseNAME
даёт строку имени (узла или листа), которым будем считать что угодно, кроме скобок и запятых "(,)":Метод st.charAt(i) даёт i-й символ (начиная от 0) в строке (можно также писать st[i]). Метод s.indexOf(ch) возвращает положение символа ch в строке s или -1, если его там нет. Выше при помощи этого метода проверяется наличие в строке скобок или запятой. Наконец, st.substring(n1,n2) возвращает подстроку начиная с n1 и до (но не включая) n2.
Последняя функция парсинга вычитывает список переменных в "функции":
Tree.parseLIST = function (st)
{
var lst = [ this.parseNODE(st) ]; // первый элемент списка
if(this.pos >= st.length)
return lst; // конец строки и списка
else if(st.charAt(this.pos)===","){
this.pos++; // дошли до запятой
return lst.concat(this.parseLIST(st));
}
else if(st.charAt(this.pos)===")"){
this.pos++; // закрывающая скобка, конец списка
return lst;
}
else
return lst; // ошибка синтаксиса
}
Теперь в html-документе можно написать следующий код:
<script>
document.write(Tree.getSVG( // выводим как svg-картинку
Tree.parse( // получаем дерево из строки
"entity("
+"object(thing,being(creature(animal,bird,fish,insect),plant),part,group,stuff,space),"
+"concept(action,time,attr,mental,sound)"
+")"
)));
</script>
что приведёт к:
Вместо функции Tree.getSVG (вывод дерева как svg-картинки), можно воспользоваться любой другой функцией: Tree.getFun (в функциональном виде), Tree.getJSON (в JSON-формат), Tree.getUL (html-список) и Tree.getGIF ("файловая" система).
Дерево, как файловая система
Разберём подробнее функцию Tree.getGIF, выводящую дерево, подобно списку файлов и папок на компьютере, с возможностью сворачивания веток дерева и иерархической пометкой узлов (покликайте на папках, листиках и плюсиках):
<script>
var myTree = {
nm:"root",
ar:[ { nm:"folder", ar:[{nm: "file1"}] },
{ nm:"file2" },
{ nm:"file2" },
]};
document.write(Tree.getGIF(myTree));
</script>
Если же нужна динамичность, то необходимо создать экземпляр
класса Tree при помощи оператора new.
Его имя, как строку, необходимо передать в функцию и задать функцию рисования show,
которая вызывается деревом при его изменении.
Кроме стандартных сворачиваний и разворачиваний узлов (папок), реализована рекурсивная пометка узлов и листьев
(необходимо кликнуть на папку или лист). Соответствующие пометки
добавляются в каждый узел дерева свойством chk, равным 1
или 0. Статической функцией Tree.arrProp(tr,"chk",1) можно получить массив
всех выбранных листьев. Кроме этого, непомеченный узел-папки имеет значение
chk=2, если хотя бы один его потомок помечен. Если папка
помечается (chk=1), то автоматически помечаются все её потомки.
Если с папки снята пометка, то она снимается и с потомков. При изменении пометки вызывается функция select, а при клике на имя узла - функция click:
var myTree = new Tree(); // создаём экземпляр класса Tree
myTree.parse( // помещаем в него дерево, парся его из строки
"entity(object(thing,being(creature(animal,bird,fish,insect),plant),part,group,stuff,space))" );
myTree.show = function () { // функция вывода дерева в div-ке c id=myTreeID
document.getElementById("myTreeID").innerHTML = myTree.getGIF("myTree"); // имя объекта!!!
Tree.svg.skpY = 40; // сильнее растягиваем вниз
Tree.svg.colors = ["#FFC", "#F9F", "#FDF"]; // цвет для непомеченных и помеченных узлов для svg
document.getElementById("myTree2ID").innerHTML = myTree.getSVG(); // рисуем как svg-картинку
Tree.svg.skpY = 30; // исходное значение
}
myTree.click = function(n) { // функция вызовется при клике на узел n
if(n.ar) alert('this is node '+n.nm+' has ' + Tree.numNodes(n) + ' nodes');
else alert('this is leaf '+n.nm);
}
myTree.select = function(n) { // произошло изменение в пометке узлов
var arr = myTree.arrProp("chk", 1); // получить массив узлов с пометкой chk:1
var st = ""; // список помеченных листьев
for(var i=0; i < arr.length; i++)
st += arr[i].nm+(i+1 < arr.length? ", ":"");
document.getElementById("mySelectID").innerHTML = st;
}
myTree.getNodes(); // список всех узлов (нужно сделать один раз)
myTree.close(2); // закрыть все узлы ниже второго
myTree.show(); // выводим дерево
Реализация getANSII
Чтобы не погрязнуть в дизайнерских изысках, нарисуем сначала дерево при помощи псевдографики (ниже первый результат):
Tree.getANSII = function (tr, calc)
{
if(!calc){ // первый запуск (не рекурсия)
var st = "";
var lst = this.getANSII(tr, true); // получаем массив строк, котрые
for(var i=0; i < lst.length; i++) // сворачиваем в одну стрку
st += lst[i]+"\n"; // перевод каретки - для <pre>
return st;
}
if(!tr.ar || tr.ar.length===0) // это лист, возвращаем только имя
return ["-"+tr.nm];
var lst = []; // список строк, который вернёт узел
lst.push("-" + tr.nm);
for(var i=0; i < tr.ar.length; i++){ // по всем потомкам
var nxt = this.getANSII(tr.ar[i], true); // получаем массив строк потомка
for(var j=0; j < nxt.length; j++){ // добавляем его в массив этого узла
var ch = " "; // линии, соединяющие узлы
if(j===0){ // первая строка (с именем потомка)
if(i+1 !== tr.ar.length) // не последний потомок
ch = tr.ar[i].ar? " +-": " |-"; // " + " для папки и " |-" для листа
else // последний потомок
ch = tr.ar[i].ar? " +-": " L-"; // тоже, но нет линии вниз
}
else if(i+1 !== tr.ar.length) // соединительная линия вниз
ch = " | ";
lst.push(ch+nxt[j]);
}
}
return lst;
}
Реализация getGIF
Теперь можно модифицировать функцию getANSII для рисования красивого дерева. Оределим классы стилей:
.tree {
font-family: Verdana, Geneva, Arial, Helvetica, sans-serif;
font-size: 12px; /* размер шрифта */
line-height:normal; /* если в документе была изменена */
white-space: nowrap; /* перевод строки никогда не будет вставлен */
overflow: auto; /* при переполнении полоса прокрутки */
}
.tree .block {
display:block; /* div-ки прижимаются друг к другу снизу */
}
.tree img {
border: 0px;
vertical-align: middle; /* картинки центрируются по веритикали */
}
При наличии квадратных картинок (18px):p111.gif:
,
p110.gif:
,
l101.gif:
,
l111.gif:
l110.gif:
flop.gif:
,
page.gif:
.
следующий html-код:
<div class="tree">
<div class="blk">
<img src="p111.gif"/><img src="flop.gif"/>root</div>
<div class="blk">
<img src="l101.gif"/><img src="p110.gif"/><img src="flop.gif"/>folder</div>
<div class="blk">
<img src="l101.gif"/><img src="empt.gif"/><img src="l110.gif"/><img src="page.gif"/>file1</div>
<div class="blk">
<img src="l111.gif"/><img src="page.gif"/>file2</div>
<div class="blk">
<img src="l110.gif"/><img src="page.gif"/>file3</div>
</div>
приведёт к вполне себе симпатичному дереву:

root

folder


file1

file2
file3Чтобы придать динамичности дереву из gif-ок, добавляются ссылки на картинки и назавания узлов. Так для картинок с плюсиками надо написать:
<a href="javascript: alert(!);"> <img src="_p111.gif"/></a>Дальнейшие детали можно найти в исходниках.
Графическое svg-представление
"Традиционное" рисование дерева в виде куста, растущего вниз, реализовано в функции getSVG. Она выводит дерево в виде текста - описания svg-файла. Его можно просто вствить в html-документ. Для настройки отображения дерева в svg-формате служит следующая структура:
Tree.svg = {
h : 20, // высота ящика для узла
w : 20, // минимальная ширина ящика для узла
chW : 10, // ширина буквы
skpY: 30, // отступить от имени узла
skpX: 10, // отступить от соседнего узла влево
cFill: "#FFFFCC", // цвет заливки
cText: "blue", // цвет текста
cLine: "black", // цвет линий
bound: false, // показывать ограничивающие ящики
colors: [], // массив цветов заливки ящиков по номеру свойства chk узла
};
Если узел дерева имеет пометку vis==false, то он не рисуется вместе со всеми потомками.
При пометке hide==true узел не рисуется, но пространство под него выделяется
(не сжимается, как это происходит при vis==false).
В зависимости от значения пометки chk=0,1,...
и наличия массива Tree.svg.colors, можно раскрашивать узлы дерева в различные цвета.
С деталями реализации функции getSVG можно разобраться по исходникам, которые достаточно хорошо задокументированы.
Справочник
Для работы с деревьями, необходимо подключить два модуля: tree.js и draw.js (графическое отображение).
Функции отображения дерева tr:
- getJSON(tr) - в JSON-формате;
- getFun(tr) - в функциональном виде типа: node(n1,n2);
- getUL(tr) - в виде html-перечислений ul-li;
- getSVG(tr) - графическое представление в svg-формате;
- getANSII(tr) - в символах псевдографики;
- getGIF(tr, name) - подобно файловой структуре, помощи картинок и css; если параметр name есть, он равен имени объекта Tree, создаваемого по new (для обработки интерактивного поведения);
- getNodes() - получить список всех узлов дерева и присовить им id в этом массиве, установить поля vis,opn,chk;
- close(depth) - для вывода функцией getGIF закрыть все узлы глубже depth
- depth(tr) - получить максимальную глубину дерева ;
- numNodes(tr) - получить количество узлов дерева tr;
- numLeaves(tr) - получить количество листьев дерева tr;
- copy(tr) - создать копиию дерева tr;
- set(tr, par, val, depth) - установить свойство par в значение val для всего дерева tr, не более чем на глубину depth;
- setNm(tr, par, val, nm) - установить свойство par в значение val для узлов дерева tr, имеющих имя узла равное nm;
- arrProp(tr, prop, val) - получить массив узлов дерева tr, имеющих свойство prop в значении val;
- create(depth, branches) - вернуть дерево глубиной depth c branches ветвями в каждом узле;
- rand(depth, branches, cut) - вернуть случайное дерево максимальной глубиной depth и branches ветвями, с вероятностью обрыва cut;
- calc(tr, fun) - Вызвать функицю fun(tr) для каждого узла дерева;
- parse(st) - получить дерево из строки st, задащей дерево в функциональной форме root(node1(leaf1,leaf2),leaf3);