Деревья

Структура

Дерево является графом у которого есть единственный узел, называемый корнем. Рёбрами он связан с другими узлами (непосредственными потомками корня). Эти потомки, в свою очередь, имеют собственных потомков и т.д. Перемещаясь от корня по узлам дерева, можно попасть в любой узел, причём единственным образом. Деревья широко используются в различных задачах поиска решений. В этом документе обсуждаются способы визуального представления деревьев. К алгоритмам обработки деревьев мы вернёмся в дальнейшем.

Дерево будем задавать объектом: { 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"}] },
   ]
};
root b1 a b b2 c d
Это дерево имеет 7 узлов, 4 из которых - терминальные. Такие узлы также называются листьями. Далее предполагается, что дерево имеет хотя бы один (корневой) узел: { nm: "root" }. Как это часто бывает в компьютерной графике (с осью y, направленной вниз), ветви деревьев на картинках растут вниз. Поэтому, говоря о спуске по дереву вниз, мы будем подразумевать продвижение от корня к листьям.

JavaScript
JSON.stringify
Внутреннее представление структуры любого объекта в виде строки, можно получить при помощи вызова функции JSON.stringify(tree) объекта JSON. Однако она даёт кавычки в названии свойств: {"nm":"root","ar":..., поэтому, для большей читабельности, обернём её регулярным выражением, удаляющим эти кавычки:
Tree.getJSON = function (tr)
{
   return JSON.stringify(tr).replace(/"(\w+)":/g, "$1:");
}
JavaScript
replace
У функции replace первым аргументом внутри слешей находится шаблон поиска. Запись \w+ означает символы из латинского алфавита, цифр или подчёркивания: [A-Za-z0-9_], которые идут подряд один или более раз (плюс после \w). Круглые скобки: (\w+) означают, что найденная подстрока запоминается в "переменной" $1, которая используется во втором аргументе функции replace. Там определяется замена, которую необходимо провести в найденном шаблоне (буква g после слеша означает глобальный поиск по всей строке).

Функция getJSON является статической и не требует создания экземпляра класса Tree при помощи new. Можно просто написать: document.write( Tree.getJSON(tree) ), что даст строку: 

{nm:"root",ar:[{nm:"b1",ar:[{nm:"a"},{nm:"b"}]},{nm:"b2",ar:[{nm:"c"},{nm:"d"}]}]}

В классе 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, приведенной выше, выдаст строку: root(b1(a,b),b2(c,d)):

Tree.getFun = function (tr)
{
   if(!tr.ar)
      return  tr.nm;                              // финальный лист
 
   var res = tr.nm+"(";                           // имя функции и открытие скобки
   for(var i=0; i < tr.ar.length ; i++)           // выводим список аргументов
      res += this.getFun(tr.ar[i])                // рекурсивно для ветвей
           + (i+1 < tr.ar.length? "," : "");      // запятая в списке, но не в конце
   return res + ")";                              // закрываем скобку
}
  • root
    • b1
      • a
      • b
    • b2
      • c
      • d
Небольшие изменения этой функции, позволяют вывести дерево в виде списка 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));
получим: root(b3,b2); root(b3,b2) и root(b1,b2) .

JavaScript
JSON.parse
В функции copy снова использован объект JSON, функция parse которого позволяет преобразовать строку в объект, произведя её синтаксический анализ. Поэтому сначала, при помощи JSON.stringify, дерево превращается в строку, затем эта строка функцией parse преобразуется опять в дерево, но уже в новой памяти. Заметим, что в JavaScript объекты можно копировать (клонировать), как и массивы, следующим образом: copy_obj = Object.assign( {} , obj); Однако метод assign копирует только простые типы и не работает рекурсивно. Так как с узлом в дальнейшем могут быть связаны различные данные, ограничимся таким, не самым эффективным, однако простым способом копирования.

Генерация деревьев

Для тестирования различных алгоритмов, необходимо создавать деревья "на лету". Напишем функцию, генерящую случайные деревья: Рисовать ящики:
глубина:3 узлов:27 листьев:16

0 17 22 26 25 24 23 18 21 20 19 7 15 16 10 14 13 12 11 8 9 4 5 6 1 3 2

Функция 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 и количество узлов можно при помощи следующих рекурсивных функций:

Tree.depth = function (tr)
{
   if(!tr.ar || tr.ar.length==0)
      return  0;
 
   var max = 0;
   for(var i=0; i < tr.ar.length; i++){
      var d = this.depth(tr.ar[i]);
      if(d > max)
         max = d;
   }
   return max+1;
}
Tree.numNodes = function (tr)
{
   if(!tr.ar || tr.ar.length==0)
      return  1;
 
   var sum = 0;
   for(var i=0; i < tr.ar.length; i++)
      sum += this.numNodes(tr.ar[i]);
 
   return 1+sum;
}

В качестве забавы, найдём среднюю глубину случайного дерева и среднее число узлов на нём (нажмите кнопку start):

depth= branches= cut= num=
depth: 2.64 nodes: 19.65 leaves: 12.18
Стоит попробовать вычислить эти параметры теоретически.

Деревья как функции

В ряде случаев удобнее задавать дерево не структурой, а строкой, подобной root(b1(a,b),b2(c,d)). Имена таких вложенных функций являются узлами дерева, а их аргументы - потомками этих узлов. При этом справедлива следующая грамматика: 

   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 даёт строку имени (узла или листа), которым будем считать что угодно, кроме скобок и запятых "(,)":
Tree.parseNODE = function (st)
{
   var tr = {nm: this.parseNAME(st) };
   if(st.charAt(this.pos)==="("){
      this.pos++;
      tr.ar = this.parseLIST(st);
   }
   return tr;
}
Tree.parseNAME = function (st)
{
   var pos1 = this.pos;      // начало имени
   while(this.pos < st.length
      && "(,)".indexOf(st.charAt(this.pos)) < 0
   )
      this.pos++;
   return st.substring(pos1, this.pos);
}
Метод 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>
что приведёт к: entity object thing being creature animal bird fish insect plant part group stuff space concept action time attr mental sound

Вместо функции Tree.getSVG (вывод дерева как svg-картинки), можно воспользоваться любой другой функцией: Tree.getFun (в функциональном виде), Tree.getJSON (в JSON-формат), Tree.getUL (html-список) и Tree.getGIF ("файловая" система).

Дерево, как файловая система

Разберём подробнее функцию Tree.getGIF, выводящую дерево, подобно списку файлов и папок на компьютере, с возможностью сворачивания веток дерева и иерархической пометкой узлов (покликайте на папках, листиках и плюсиках):


entity object thing being part group stuff space

Прежде чем описывать её устройство, приведём пример использования. Если от дерева не требуется итерактивности, вставка его в html-страницу делается так:
<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

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

-0
 +--1
 |  +--3
 |  |  +--5
 |  |     |--6
 |  |     |--7
 |  |     L--8
 |  L--4
 L--2
0 1 3 5 6 7 8 4 2
  • 0
    • 1
      • 3
        • 5
          • 6
          • 7
          • 8
      • 4
    • 2
0
1
3
5
6
7
8
4
2
При стартовом запуске статическая функция Tree.getANSII вызывается без второго праметра calc и возвращает строку, разбитую на линии символами возврата каретки ("\n"). Если параметр clac=true (при рекурсивных вызовах), то функция возвращает массив строк отображения данного узла:
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
Именно эти div-ки и img-ы необходимо вставить в функции Tree.getANSII для получения функции Tree.getGIF рисования дерева при помощи gif-ок.

Чтобы придать динамичности дереву из 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:

Параметры дерева tr: Обработка и создание деревьев: Разное:

Приоритетная очередь <
> Графы