Деревья
Дерево является графом у которого есть единственный узел, называемый корнем. Рёбрами он связан с другими узлами (непосредственными потомками корня). Эти потомки, в свою очередь, имеют собственных потомков и т.д. Перемещаясь от корня по узлам дерева, можно попасть в любой узел, причём единственным образом. Деревья широко используются в различных задачах поиска решений. В этом документе обсуждаются способы визуального представления деревьев. К алгоритмам обработки деревьев мы вернёмся в дальнейшем.
Дерево будем задавать объектом: , где nm — имя узла, а ar — массив ветвей (ближайших потомков). Так, следующий объект tree описывает бинарное дерево глубины 2, изображенное справа на рисунке:
Это дерево имеет 7 узлов, 4 из которых — терминальные. Такие узлы также называются листьями. Далее предполагается, что дерево имеет хотя бы один (корневой) узел: . Как это часто бывает в компьютерной графике (с осью y, направленной вниз), ветви деревьев на картинках растут вниз. Поэтому, говоря о спуске по дереву вниз, мы будем подразумевать продвижение от корня к листьям.
Внутреннее представление структуры любого объекта в виде строки, можно получить при помощи вызова функции JSON.stringify(tree) объекта JSON. Однако она даёт кавычки в названии свойств: , поэтому, для большей читабельности, обернём её регулярным выражением, удаляющим эти кавычки:
У функции replace первым аргументом внутри слешей находится шаблон поиска. Запись \w+ означает символы из латинского алфавита, цифр или подчёркивания: [A-Za-z0-9_], которые идут подряд один или более раз (плюс после \w). Круглые скобки: (\w+) означают, что найденная подстрока запоминается в «переменной» $1, которая используется во втором аргументе функции replace. Там определяется замена, которую необходимо провести в найденном шаблоне (буква g после слеша означает глобальный поиск по всей строке).
Функция 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 ()
Таким образом, класс Tree может в статическом варианте обрабатывать структуры подобные tree, а в динамическом — хранить дерево «внутри себя». Например, дерево в JSON-формате можно вставить в документ также так: var t = new Tree(tree); document.write( t.getJSON() ).
Вывод дерева
При работе с деревьями естественно использовать рекурсивные методы. Напишем, например, функцию вывода дерева в «функциональном» виде, которая для структуры tree, приведенной выше, выдаст строку: :
Небольшие изменения этой функции, позволяют вывести дерево в виде списка html (функция Tree.getUL(tr), выше, справа). Ещё две функции Tree.getGIF(tr) (в виде папочек) и Tree.getSVG(tr) (традиционное преставление) будут рассмотрены позднее.
Копирование деревьев
Присвоение деревьев, как и любых объектов, проводится по ссылке. Чтобы получить независимую копию дерева, напишем незамысловатую функцию:
var tree1 = < nm:"root", ar:[ , ] >; var tree2 = tree1; // тоже дерево (по ссылке) var tree3 = Tree.copy(tree1); // независимая копия tree1.ar[0].nm = "b3"; // меняем имя узла потомка document.write(Tree.getFun(tree1), '; ', Tree.getFun(tree2),' и ', Tree.getFun(tree3));
В функции copy снова использован объект JSON, функция parse которого позволяет преобразовать строку в объект, произведя её синтаксический анализ. Поэтому сначала, при помощи JSON.stringify, дерево превращается в строку, затем эта строка функцией parse преобразуется опять в дерево, но уже в новой памяти. Заметим, что в JavaScript объекты можно копировать (клонировать), как и массивы, следующим образом: copy_obj = Object.assign( <> , obj); Однако метод assign копирует только простые типы и не работает рекурсивно. Так как с узлом в дальнейшем могут быть связаны различные данные, ограничимся таким, не самым эффективным, однако простым способом копирования.
Генерация деревьев
Для тестирования различных алгоритмов, необходимо создавать деревья «на лету». Напишем функцию, генерящую случайные деревья: Рисовать ящики:
Функция 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)
В качестве забавы, найдём среднюю глубину случайного дерева и среднее число узлов на нём (нажмите кнопку start):
depth: 2.64 nodes: 19.65 leaves: 12.18
Стоит попробовать вычислить эти параметры теоретически.
Деревья как функции
В ряде случаев удобнее задавать дерево не структурой, а строкой, подобной . Имена таких вложенных функций являются узлами дерева, а их аргументы — потомками этих узлов. При этом справедлива следующая грамматика:
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.parseNODE возвращает дерево . Функция Tree.parseNAME даёт строку имени (узла или листа), которым будем считать что угодно, кроме скобок и запятых «(,)»:
Tree.parseNODE = function (st) < var tr = ; 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.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; // ошибка синтаксиса >
Вместо функции Tree.getSVG (вывод дерева как svg-картинки), можно воспользоваться любой другой функцией: Tree.getFun (в функциональном виде), Tree.getJSON (в JSON-формат), Tree.getUL (html-список) и Tree.getGIF («файловая» система).
Дерево, как файловая система
Разберём подробнее функцию Tree.getGIF, выводящую дерево, подобно списку файлов и папок на компьютере, с возможностью сворачивания веток дерева и иерархической пометкой узлов (покликайте на папках, листиках и плюсиках):
Прежде чем описывать её устройство, приведём пример использования. Если от дерева не требуется итерактивности, вставка его в html-страницу делается так:
Если же нужна динамичность, то необходимо создать экземпляр класса 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 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 вызывается без второго праметра 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"; // перевод каретки - для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 для рисования красивого дерева. Оределим классы стилей:
При наличии квадратных картинок (18px):
p111.gif: , p110.gif: , l101.gif: , l111.gif: l110.gif: flop.gif: , page.gif: .rootfolderfile1file2file3Именно эти div-ки и img-ы необходимо вставить в функции Tree.getANSII для получения функции Tree.getGIF рисования дерева при помощи gif-ок.
Чтобы придать динамичности дереву из gif-ок, добавляются ссылки на картинки и назавания узлов. Так для картинок с плюсиками надо написать:
Графическое svg-представление
«Традиционное» рисование дерева в виде куста, растущего вниз, реализовано в функции getSVG. Она выводит дерево в виде текста — описания svg-файла. Его можно просто вствить в html-документ. Для настройки отображения дерева в svg-формате служит следующая структура:
Если узел дерева имеет пометку vis==false, то он не рисуется вместе со всеми потомками. При пометке hide==true узел не рисуется, но пространство под него выделяется (не сжимается, как это происходит при vis==false). В зависимости от значения пометки chk=0,1. и наличия массива Tree.svg.colors, можно раскрашивать узлы дерева в различные цвета.
С деталями реализации функции getSVG можно разобраться по исходникам, которые достаточно хорошо задокументированы.
Справочник
Для работы с деревьями, необходимо подключить два модуля: tree.js и draw.js (графическое отображение).
- 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);
Источник