Определить функцию, которая ищет заданную вершину в дереве - Lisp

Узнай цену своей работы

Формулировка задачи:

Помогите, пожалуйста, с заданием! Определить функцию, которая ищет заданную вершину в дереве и возвращает список, содержащий предка искомой вершины и её потомков: (предок (потомок1 потомок2...))

Решение задачи: «Определить функцию, которая ищет заданную вершину в дереве»

textual
Листинг программы
(defun task (root what &optional (from nil))
  (cond ((null root) nil)
        ((= (cadr root) what) (cons (cadr from) (list (remove what(tree2list root)))))
        (t (append (task (car root) what root) (task (caddr root) what root)))))
 
==> TASK
 
(task '(((nil 111 nil) 23 (nil 8 nil)) 11 (nil -4 (nil 7 nil))) -4)
 
==> (11 (7))
 
(task '(((nil 111 nil) 23 (nil 8 nil)) 11 (nil -4 (nil 7 nil))) 23)
 
==> (11 (111 8))

Объяснение кода листинга программы

В коде определена функция task, которая принимает три аргумента: root (корневой элемент дерева), what (элемент, который нужно найти в дереве) и необязательный аргумент from (используется для возврата коллекции узлов, содержащих искомый элемент). Функция использует конструкцию cond для проверки трех условий:

  1. Если root равен nil, то возвращается nil.
  2. Если cadr root равен what, то возвращается новая коллекция, содержащая what и все поддеревья, которые не содержат what.
  3. Если условие не выполнено, то рекурсивно вызывается функция task для двух новых поддеревьев, которые получаются путем разделения root на две части по what. В примере кода вызывается функция task с аргументами: (((nil 111 nil) 23 (nil 8 nil)) 11 (nil -4 (nil 7 nil))) -4 и nil. Первая строка (11 (7)) в выводе означает, что функция нашла элемент -4 в дереве, и возвращает новый список, содержащий только узлы, которые содержат -4. Вторая строка (11 (111 8)) означает, что функция нашла элемент 23 в дереве, и возвращает новый список, содержащий только узлы, которые содержат 23.

Оцени полезность:

14   голосов , оценка 3.857 из 5
Похожие ответы