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

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

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

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

@Nameless One · 24.09.2011, 03:31

По индукции:

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

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

Lisp

(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

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

(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

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

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

(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

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>

Новые блоги и статьи
Списки в Haskell hw_wired 28.01.2025 Haskell является функциональным языком программирования, который отличается лаконичностью синтаксиса и мощными абстракциями. Важным концептом в Haskell являются списки — упорядоченные коллекции. . .	Функции высшего порядка в Haskell hw_wired 28.01.2025 Haskell – это современный функциональный язык программирования, который получил широкое распространение благодаря своей выразительности и мощным абстракциям. Одной из ключевых особенностей Haskell. . .	Как в цикле обойти все поля объекта в JavaScript bytestream 28.01.2025 Объекты в JavaScript представляют собой фундаментальные структуры данных, которые позволяют хранить и организовывать связанную информацию в виде пар ключ-значение. Каждый объект можно представить как. . .	Как выбрать строки в DataFrame по значению столбца в Pandas bytestream 28.01.2025 В области анализа данных библиотека Pandas стала незаменимым инструментом для работы с табличными данными в Python. Эта мощная библиотека предоставляет множество функций для эффективной обработки и. . .	Как сделать перенос строки в Bash bytestream 28.01.2025 При работе с командной оболочкой Bash разработчики часто сталкиваются с необходимостью форматирования текстового вывода, где ключевую роль играет правильное управление переносами строк. Умение. . .	Поиск подстроки в строке с помощью Bash bytestream 28.01.2025 Поиск подстроки в строке является одной из важных задач в программировании и обработке текстов. Применение такого поиска можно найти в самых разных областях, от анализа данных до разработки. . .
[golang] 169. Majority Element alhaos 28.01.2025 Тут надо вернуть "мажористый" элемент который встречается в слайсе больше чем в половине случаев. По условиям задачи во входных данных такой элемент обязан присутствовать. / / . . .	Когда лучше использовать LinkedList вместо ArrayList в Java bytestream 28.01.2025 При разработке Java-приложений выбор правильной структуры данных играет ключевую роль в обеспечении эффективности и производительности программы. ArrayList и LinkedList являются двумя. . .	Какой ответ HTTP лучше использовать: 403 Forbidden или 401 Unauthorized, когда недостаточно прав bytestream 28.01.2025 В современной веб-разработке правильная обработка ошибок и точное информирование клиентов о статусе их запросов играют критическую роль в создании надежных и безопасных приложений. Особое внимание. . .	Как получить список всех файлов коммита в Git bytestream 28.01.2025 Система контроля версий Git представляет собой мощный инструмент для управления изменениями в программном коде и других файлах проекта. В основе работы Git лежит концепция коммитов - снимков. . .	Как записать только часть изменений файла в Git bytestream 28.01.2025 В процессе разработки программного обеспечения часто возникает необходимость сохранить только определенные изменения из множества внесенных правок в файлах. Система контроля версий Git предоставляет. . .	[golang] 80. Remove Duplicates from Sorted Array II alhaos 28.01.2025 В предоставленном упорядоченном по возрастанию целочисленном слайсе, оставить уникальные элементы полюс один возможный дубликат. Вернуть количество таких элементов. / / . . .

@RUSya82 242 / 120 / 14 Регистрация: 15.10.2010 Сообщений: 395
		1
	Представление дерева в виде списка 23.09.2011, 20:40. Показов 4842. Ответов 10 Метки нет (Все метки) Здравствуйте. Так и не могу понять, каким образом представляются деревья в виде списков! Можно пример? 0

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

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

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