LISP - Дерево

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

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

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

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

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

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

Древовидные функции в LISP

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

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

Sr. No.	Описание функции
1	copy-tree x & необязательный vecp Он возвращает копию дерева cons-ячеек x. Он рекурсивно копирует как car, так и cdr направления. Если x не является cons-ячейкой, функция просто возвращает x без изменений. Если необязательный аргумент vecp истинен, эта функция копирует векторы (рекурсивно), а также cons-ячейки.
2	tree-equal xy & ключ: тест: тест-не: ключ Он сравнивает два дерева cons-ячеек. Если x и y являются cons-ячейками, их автомобили и cdr сравниваются рекурсивно. Если ни x, ни y не являются cons-ячейкой, они сравниваются с помощью eql или в соответствии с указанным тестом. Функция: key, если она указана, применяется к элементам обоих деревьев.
3	subst новое старое дерево и ключ: test: test-not: key Он заменяет вхождения данного старого элемента новым элементом в дереве , которое представляет собой дерево cons-ячеек.
4	nsubst новое старое дерево и ключ: test: test-not: key Он работает так же, как subst, но разрушает исходное дерево.
5	sublis дерево списка и ключ: test: test-not: key Он работает так же, как и subst, за исключением того, что принимает список ассоциаций, состоящий из старых и новых пар. Каждый элемент дерева (после применения функции: key, если она есть) сравнивается с автомобилями из alist; если он совпадает, он заменяется соответствующим cdr.
6	nsublis дерево списка и ключ: test: test-not: key Работает так же, как sublis, но в деструктивной версии.

Пример 1

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

(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))

Пример 2

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

(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))))

Создание собственного дерева

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

Сначала давайте создадим новый узел, содержащий некоторые данные

(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))
)

пример

В этом примере используются вышеуказанные функции -

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

(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)

Когда вы выполняете код, он возвращает следующий результат -

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

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