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