ЛИСП — Дерево

Вы можете строить древовидные структуры данных из cons-ячеек, как списки списков.

Чтобы реализовать древовидные структуры, вам нужно спроектировать функциональные возможности, которые будут проходить через cons-ячейки в определенном порядке, например, предварительный порядок, порядок и порядок для двоичных деревьев.

Дерево как список списков

Давайте рассмотрим древовидную структуру, состоящую из клеток cons, которые образуют следующий список списков:

((1 2) (3 4) (5 6)).

Схематически это можно выразить как —

Функции дерева в LISP

Хотя в основном вам нужно будет написать свои собственные древовидные функции в соответствии с вашими конкретными потребностями, LISP предоставляет некоторые древовидные функции, которые вы можете использовать.

Помимо всех функций списка, следующие функции работают особенно на древовидных структурах —

дерево копий x & необязательный vecp

Возвращает копию дерева cons клеток x. Он рекурсивно копирует как автомобиль, так и CDR. Если x не является cons-ячейкой, функция просто возвращает x без изменений. Если необязательный аргумент vecp равен true, эта функция копирует векторы (рекурсивно), а также cons-ячейки.

равный дереву xy & key: test: test-not: key

Он сравнивает два дерева минусов. Если x и y оба являются cons-ячейками, их машины и cdrs сравниваются рекурсивно. Если ни x, ни y не являются cons-ячейками, они сравниваются по eql или согласно указанному тесту. Функция: key, если указана, применяется к элементам обоих деревьев.

sub новое старое дерево и ключ: test: test-not: key

Он заменяет вхождения данного старого элемента новым элементом в дереве , которое является деревом клеток-противников.

nsubst новое старое дерево и ключ: test: test-not: key

Он работает так же, как и Sub, но уничтожает исходное дерево.

Sublis Alist Tree & Key: тест: тест-не: ключ

Он работает как субстрат, за исключением того, что он принимает список ассоциативных списков старых-новых пар. Каждый элемент дерева (после применения функции: key, если есть) сравнивается с машинами из alist; если он совпадает, он заменяется соответствующим CDR.

nsublis alist tree & key: test: test-not: key

Он работает так же, как Sublis, но деструктивная версия.

Пример 1

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo

(setq lst (list '(1 2) '(3 4) '(5 6)))
(setq mylst (copy-list lst))
(setq tr (copy-tree lst))

(write lst)
(terpri)
(write mylst)
(terpri)
(write tr)

((1 2) (3 4) (5 6))
((1 2) (3 4) (5 6))
((1 2) (3 4) (5 6))

(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(write tr)
(setq trs (subst 7 1 tr))
(terpri)
(write trs)

((1 2 (3 4 5) ((7 8) (7 8 9))))
((7 2 (3 4 5) ((7 8) (7 8 9))))

(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)

(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree)

(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)

(defun next-sibling (tree)
   (cdr tree)
)

(defun data (tree)
   (car (car tree))
)

(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)
(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)

(defun next-sibling (tree)
   (cdr tree)
)
(defun data (tree)
   (car (car tree))
)
(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree
)

(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(setq mytree (make-tree 10))

(write (data mytree))
(terpri)
(write (first-child tr))
(terpri)
(setq newtree (add-child tr mytree))
(terpri)
(write newtree)