О представлении деревьев списками.
Самый простой способ представление деревьев списками – представление
узлового (не листового) элемента списком вершин на которые
он ссылается.
Это есть представление дерева:
Работать с таким представлением одно удовольствие –
все алгоритмы простые и понятные. Однако имеется один
существенный недостаток – значения могут содержаться только
в листовых вершинах такого дерава. Очевидное усовершенствование –
хранение в каждом узле как значения
так и указателей на дочерние узлы.
Это есть представление дерева:
Алгоритмы сильных изменений не претерпевают, остаются такими
же простыми и понятными. Однако есть одно маленькое
неудобство на практике – если мы захотим представить
лес – список деревьев, то описание получится достаточно
громоздким:
А леса очень часто требуются именно в описании интерфейса,
например, для задания содержимого виджета treeview. Примем
следующее правило: если за элементом следует вложенный список,
то это есть не что иное как список дочерних узлов этого
элемента.
Тогда приведённый выше лес, можно записать следующим, более наглядным образом:
Оказывается что для такого представления основные алгоритмы
получаются не намного сложнее, хотя определённую цену конечно
приходится платить за удобство представления.
Например, поиск узла с данным номером на данном уровне производится следующей функцией:
Функция возвращает хвост списка начиная с данного элемента, хвост
– потому что если потом потребуется переход на дочерние
виджеты – мы просто берём второй элемент получившегося списка
(если конечно сможем).
Ещё одна полезная операция – получение пути по данному элементу,
заданным адресом (<номер первого узла> <номер следующего
узла> ...)
Здесь используется функция cond-cadr, которая действует следующим
образом: если можно получить второй элемент – она его возвращает,
иначе – возвращает #f.
Определение, является ли данный элемент листом или нет: если
за элементом следует список, то это промежуточная вершина –
иначе листовая.
В результате небольшой модификации предыдущей функции – получаем полезный предикат.
Ну и наконец самое интересное – пособираем букет из отдельных
веточек. То есть на вход функции подаётся отсортированная
последовательность путей в будущем лесе, на выходе получается
лес, в который включены все переданные пути.
Первым делом с помощью функции
row->branch превращаем пути в отдельные веточки.
А потом пользуясь отсортированностью списка аккуратненько, начиная
с хвоста начинаем соединять отдельные веточки в целое дерево.
Ниже приведён весь оставшийся код – главная функция
rows->tree-items.