Вход:  Пароль:  
FreeSource: AltLinux/Sisyphus/Alterator/tree ...
Free Source | Каталог | Изменения | НовыеКомментарии | Пользователи | Регистрация |
Эта страница была перенесена на altlinux.org. Текст на freesource.info заморожен.

О представлении деревьев списками.


Самый простой способ представление деревьев списками – представление узлового (не листового) элемента списком вершин на которые он ссылается.

Это есть представление дерева:

Работать с таким представлением одно удовольствие – все алгоритмы простые и понятные. Однако имеется один существенный недостаток – значения могут содержаться только в листовых вершинах такого дерава. Очевидное усовершенствование – хранение в каждом узле как значения так и указателей на дочерние узлы.

Это есть представление дерева:

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

А леса очень часто требуются именно в описании интерфейса, например, для задания содержимого виджета treeview. Примем следующее правило: если за элементом следует вложенный список, то это есть не что иное как список дочерних узлов этого элемента.
Тогда приведённый выше лес, можно записать следующим, более наглядным образом:


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

Функция возвращает хвост списка начиная с данного элемента, хвост – потому что если потом потребуется переход на дочерние виджеты – мы просто берём второй элемент получившегося списка (если конечно сможем).
Ещё одна полезная операция – получение пути по данному элементу, заданным адресом (<номер первого узла> <номер следующего узла> ...)

Здесь используется функция cond-cadr, которая действует следующим образом: если можно получить второй элемент – она его возвращает, иначе – возвращает #f.


Определение, является ли данный элемент листом или нет: если за элементом следует список, то это промежуточная вершина – иначе листовая.
В результате небольшой модификации предыдущей функции – получаем полезный предикат.

Ну и наконец самое интересное – пособираем букет из отдельных веточек. То есть на вход функции подаётся отсортированная последовательность путей в будущем лесе, на выходе получается лес, в который включены все переданные пути.

Первым делом с помощью функции row->branch превращаем пути в отдельные веточки.

А потом пользуясь отсортированностью списка аккуратненько, начиная с хвоста начинаем соединять отдельные веточки в целое дерево.
Ниже приведён весь оставшийся код – главная функция rows->tree-items.


 
Файлов нет. [Показать файлы/форму]
Комментарии [Скрыть комментарии/форму]