Представление дерева в виде списка

@RUSya82 · Регистрация: 15.10.2010

Студворк — интернет-сервис помощи студентам

Здравствуйте. Так и не могу понять, каким образом представляются деревья в виде списков! Можно пример?

@Nameless One · 24.09.2011, 03:31

По индукции:

Пустое дерево представляется пустым списком.
Узловая вершина представляется списком, в котором голова - это значение, которое хранится в вершине, а хвост - это список поддеревьев

Соответственно, листовая вершина, это узловая вершина, у которой список поддеревьев пуст.
Имеем конструкторы nil, cons, предикаты null, not null и селекторы car, cdr.
Пример - дерево, у которого в корне находится 'a, левое поддерево представляет собой лист 'b, правое -'c:

Lisp
1
2
3
4
(a
  (b)
  (c))
)

@RUSya82 · 24.09.2011, 18:48 **[ТС]**

То есть если мы имеем дерево (см. во вложении), то в виде списка оно будет:

Lisp
1
( a   ((b  ((e (i j k)) f))     (c g)   (d (h (l m)))))

Так, или нет?Tree.doc
Если не так, то можно написать как правильно?

@Nameless One · 25.09.2011, 05:22

Lisp
1
2
3
4
5
6
7
8
9
CL-USER> '(a (b (e (i) (j) (k)) (f)) (c (g)) (d (h (i) (m)))) ; само дерево
(A (B (E (I) (J) (K)) (F)) (C (G)) (D (H (I) (M))))
CL-USER> (car '(a (b (e (i) (j) (k)) (f)) (c (g)) (d (h (i) (m))))) ; значение корневой вершины
A
CL-USER> (cdr '(a (b (e (i) (j) (k)) (f)) (c (g)) (d (h (i) (m))))) ; поддеревья корневой вершины
((B (E (I) (J) (K)) (F)) (C (G)) (D (H (I) (M))))
CL-USER> (cons 'new-a (cdr '(a (b (e (i) (j) (k)) (f)) (c (g)) (d (h (i) (m)))))) ; замена корневой вершины
(NEW-A (B (E (I) (J) (K)) (F)) (C (G)) (D (H (I) (M))))
CL-USER>

@RUSya82 · 25.09.2011, 15:14 **[ТС]**

А не могли бы вы кратенько на словах описать алгоритм нахождения глубины дерева. Хотя бы в общих чертах.

@Nameless One · 25.09.2011, 15:37

Опять же, по индукции:

Глубина пустого дерева равна нулю
Глубина непустого дерева равна 1 + максимальной из глубин его поддеревьев

Lisp
1
2
3
4
(defun tree-depth (tree)
  (if tree ; или (if (not (null tree...
      (+ 1 (apply #'max 0 (mapcar #'tree-depth (cdr tree))))
      0))

Пример для твоего дерева:

Lisp
1
2
3
CL-USER> (tree-depth '(a (b (e (i) (j) (k)) (f)) (c (g)) (d (h (i) (m)))))
4
CL-USER>

@RUSya82 · 25.09.2011, 18:26 **[ТС]**

Возникли вопросы!
1.Для чего перед именами функций max и tree-depth используем # - получение функции с данным именем. Разве не достаточно просто quote? В чём подвох? По крайней мере у меня работает в обоих случаях.
2. Что за функция max? она возвращает максимальный элемент в списке? тогда для чего 0 (ноль) ?

@Nameless One · 25.09.2011, 18:47

По пунктам:

Можно и просто quote. #' - это просто синтаксический сахар для function. Если funcall или apply передан символ, то он приводится к функциональному объекту неявно
Функция max принимает *ненулевое* число аргументов (т.е. один или больше) и возвращает максимальный из них.
Так как список поддеревьев у произвольного дерева может быть пустым (например, листовая вершина), то и выражение (mapcar #'tree-depth (cdr tree)) для такого дерева вернет пустой список. А это значит, что применение (apply) функции max к пустому списку (т.е. передача max нулевого числа аргументов) приведет к ошибке времени выполнения. Поэтому сначала передается "аргумент по умолчанию" - ноль - который не сможет повлиять на результат для случая с деревом, у которого непустой список поддеревьев.

@RUSya82 · 26.09.2011, 17:34 **[ТС]**

Спасибо большое!

Добавлено через 22 часа 29 минут
Еще вопросик! Форма apply:
(apply функция список),
то есть список - это аргументы функции.
а у нас получается:
(apply функция 0 список).
Так если список не пуст, то куда девается этот самый ноль?

Добавлено через 2 минуты
Хотя работает и так и так:

Lisp
1
2
3
4
5
6
7
8
9
10
11
CL-USER 34 > (apply 'max '(5 2 6 4 8 9))
9
 
CL-USER 35 > (apply 'max 5 6 8 9 7 '(5 2 6 4 8 9))
9
 
CL-USER 36 > (apply 'max 5 6 8 9 7 '(5 2 6 24 8 9))
24
 
CL-USER 37 > (apply 'max 5 68 8 9 7 '(5 2 6 24 8 9))
68

@Nameless One · 26.09.2011, 17:52

apply принимает функциональный объект и spreadable argument list designator ("указатель" на расширяемый список аргументов, обозначение расширяемого списка аргументов). Т.е. помимо функционального объекта, apply принимает переменное число (но больше нуля) аргументов, последний из которых должен быть списком. Все предыдущие аргументы как бы "расширяют" список, переданный последним.
Пример:

Lisp
1
2
3
4
5
CL-USER> (apply #'max 0 nil) ; <=> (apply #'max '(0)) <=> (max 0)
0
CL-USER> (apply #'max 0 '(1 2 3)) ; <=> (apply #'max '(0 1 2 3)) <=> (max 0 1 2 3)
3
CL-USER>

В примерах выше все, что идет после первого аргумента (#'max) - и есть spreadable argument list designator
В первом случае у нас 0 расширяет пустой список (получается аналогично '(0)), во втором случае - 0 расширяет непустой список '(1 2 3) (получается аналогично '(0 1 2 3)).
Попробуй в REPL различные варианты (которые у меня показаны после комментариев), и все станет ясно.

@Nameless One · 26.09.2011, 18:15

Вот пример функции, которая принимает функцию, speadable argument list designator, собирает его в простой список, печатает "эквивалентный вызов" функции и возвращает собранный список:

Lisp
1
2
3
4
(defun apply-display (fun arg &rest args)
  (let ((proper-args-list (reduce #'cons (cons arg args) :from-end t)))
    (format t "Equivalent to (~a ~{~a~^ ~})~%" fun proper-args-list)
    proper-args-list))

Пример:

Lisp
1
2
3
4
5
6
7
8
9
10
CL-USER> (apply-display 'max '(1 2 3 4))
Equivalent to (MAX 1 2 3 4)
(1 2 3 4)
CL-USER> (apply-display 'max 1 2 3 '(4))
Equivalent to (MAX 1 2 3 4)
(1 2 3 4)
CL-USER> (apply-display 'max 0 nil)
Equivalent to (MAX 0)
(0)
CL-USER>

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

@RUSya82 242 / 120 / 14 Регистрация: 15.10.2010 Сообщений: 395

	Представление дерева в виде списка 23.09.2011, 20:40. Показов 5007. Ответов 10 Метки нет (Все метки) Здравствуйте. Так и не могу понять, каким образом представляются деревья в виде списков! Можно пример? 0

@RUSya82 242 / 120 / 14 Регистрация: 15.10.2010 Сообщений: 395
	25.09.2011, 15:14 [ТС]
	А не могли бы вы кратенько на словах описать алгоритм нахождения глубины дерева. Хотя бы в общих чертах. 0

@RUSya82 242 / 120 / 14 Регистрация: 15.10.2010 Сообщений: 395
	25.09.2011, 18:26 [ТС]
	Возникли вопросы! 1.Для чего перед именами функций max и tree-depth используем # - получение функции с данным именем. Разве не достаточно просто quote? В чём подвох? По крайней мере у меня работает в обоих случаях. 2. Что за функция max? она возвращает максимальный элемент в списке? тогда для чего 0 (ноль) ? 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	25.09.2011, 18:47
	По пунктам: Можно и просто quote. #' - это просто синтаксический сахар для function. Если funcall или apply передан символ, то он приводится к функциональному объекту неявно Функция max принимает ненулевое число аргументов (т.е. один или больше) и возвращает максимальный из них. Так как список поддеревьев у произвольного дерева может быть пустым (например, листовая вершина), то и выражение (mapcar #'tree-depth (cdr tree)) для такого дерева вернет пустой список. А это значит, что применение (apply) функции max к пустому списку (т.е. передача max нулевого числа аргументов) приведет к ошибке времени выполнения. Поэтому сначала передается "аргумент по умолчанию" - ноль - который не сможет повлиять на результат для случая с деревом, у которого непустой список поддеревьев. 1