Определить, является ли второе дерево поддеревом первого

@user_name · Регистрация: 21.04.2011

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

Заданы два дерева с помощью цепных списков. *Определить, является ли второе дерево поддеревом первого.

Помогите пожалуйста реализовать это на лиспе

@Nameless One · 22.04.2011, 05:34

user_name, что такое "цепной список"?

@user_name · 22.04.2011, 07:01 **[ТС]**

знать бы

Добавлено через 3 минуты
Самый простой цепной список — это последовательность однотипных элементов, которые произвольно расположены в памяти, а связываются друг с другом благодаря имеющейся в каждом объекте ссылке на следующий элемент. Ссылка у последнего элемента цепочки имеет какое-то специальное значение, по которому распознается конец списка.

Для работы с цепным списком нужно иметь ссылку на его голову — начальный элемент. В некоторых случаях удобно иметь еще и ссылку на последний элемент списка, — эта необходимость возникает, когда новые элементы нужно вставлять и в начало и в конец списка.

@Nameless One · 23.04.2011, 06:15

Дерево будет определяться так - это список, в котором голова - это корень дерева (атом), а хвост - это список поддеревьев (ветвей) дерева (списков). Соответственно, лист дерева - это список из одного атома. nil - пустое дерево.

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defun tree-equal (tree1 tree2)
  (or (and (null tree1) (null tree2))
      (and (listp tree1) (listp tree2)
       (eq (car tree1) (car tree2))
       (= (length (cdr tree1)) (length (cdr tree2)))
       (every #'listp (cdr tree1))
       (every #'listp (cdr tree2))
       (every #'tree-equal (cdr tree1) (cdr tree2)))))
 
 
(defun subtree-p (tree subtree-candidate)
  (or (and (listp tree) (null subtree-candidate))
      (tree-equal tree subtree-candidate)
      (some #'(lambda (subtree)
        (subtree-p subtree subtree-candidate))
        (cdr tree))))

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
CL-USER> (subtree-p 
      '(a 
        (b 
         (c) 
         (d 
          (e)) 
         (f))
        (g
         (h)))
      '(b
        (c)
        (d
         (e))
        (f)))
T
CL-USER>

@user_name · 23.04.2011, 10:45 **[ТС]**

Спасибо большое, спасли просто

@KatrinOops · 19.05.2012, 16:15

Подскажите, пожалуйста, как реализовать это же задание, но на mu_lisp

@bokunopico · 19.05.2012, 16:30

Сообщение от KatrinOops

Подскажите, пожалуйста, как реализовать это же задание, но на mu_lisp

Взять решение от Nameless One и удалить из кода решётку.

@KatrinOops · 19.05.2012, 16:35

Огромное спасибо))))
Bokunopico, Вы снова помогли мне))))

@Pavluk · 27.05.2012, 20:15

Подскажите, пожалуйста, как написать программу, решающую эту задачу, на хаскеле

@bokunopico · 27.05.2012, 20:18

Форум программистов и сисадминов CyberForum.ru > Форум программистов > Форум Другие языки программирования > Форум Lisp

Сообщение от Pavluk

Подскажите, пожалуйста, как написать программу, решающую эту задачу, на хаскеле

Спросить в соответствующем разделе?

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение Это мой обзор планшета X220 с точки зрения школьника. Недавно я решила попытаться уменьшить свой. . .	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 - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@user_name 1 / 1 / 0 Регистрация: 21.04.2011 Сообщений: 8

	Определить, является ли второе дерево поддеревом первого 22.04.2011, 00:45. Показов 1680. Ответов 9 Метки нет (Все метки) Заданы два дерева с помощью цепных списков. *Определить, является ли второе дерево поддеревом первого. Помогите пожалуйста реализовать это на лиспе 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	22.04.2011, 05:34
	user_name, что такое "цепной список"? 0

@user_name 1 / 1 / 0 Регистрация: 21.04.2011 Сообщений: 8
	22.04.2011, 07:01 [ТС]
	знать бы Добавлено через 3 минуты Самый простой цепной список — это последовательность однотипных элементов, которые произвольно расположены в памяти, а связываются друг с другом благодаря имеющейся в каждом объекте ссылке на следующий элемент. Ссылка у последнего элемента цепочки имеет какое-то специальное значение, по которому распознается конец списка. Для работы с цепным списком нужно иметь ссылку на его голову — начальный элемент. В некоторых случаях удобно иметь еще и ссылку на последний элемент списка, — эта необходимость возникает, когда новые элементы нужно вставлять и в начало и в конец списка. 1

@user_name 1 / 1 / 0 Регистрация: 21.04.2011 Сообщений: 8
	23.04.2011, 10:45 [ТС]
	Спасибо большое, спасли просто 0

@KatrinOops 0 / 0 / 0 Регистрация: 13.05.2012 Сообщений: 6
	19.05.2012, 16:15
	Подскажите, пожалуйста, как реализовать это же задание, но на mu_lisp 0

@KatrinOops 0 / 0 / 0 Регистрация: 13.05.2012 Сообщений: 6
	19.05.2012, 16:35
	Огромное спасибо)))) Bokunopico, Вы снова помогли мне)))) 0

@Pavluk 0 / 0 / 0 Регистрация: 06.12.2017 Сообщений: 2
	27.05.2012, 20:15
	Подскажите, пожалуйста, как написать программу, решающую эту задачу, на хаскеле 0