Разработать функцию, которая находит наибольшее значение в заданном бинарном дереве - Lisp

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

Разработать функцию, которая находит наибольшее значение в заданном бинарном дереве

Решение задачи: «Разработать функцию, которая находит наибольшее значение в заданном бинарном дереве - Lisp»

Листинг программы

(defun max-in-tree (tree)
  (cond ((and (null (car tree)) (null (caddr tree))) (cadr tree))
        ((null (car tree)) (max (cadr tree) (max-in-tree (caddr tree))))
        ((null (caddr tree)) (max (cadr tree) (max-in-tree (car tree))))
        (t (max (cadr tree) (max-in-tree (car tree)) (max-in-tree (caddr tree))))))
 
==> MAX-IN-TREE
 
(setq *t* '((nil 12 nil) 7 ( (nil -1 nil) 8 (nil 77 nil) ))) 
 
==> ((NIL 12 NIL) 7 ((NIL -1 NIL) 8 (NIL 77 NIL)))
 
(max-in-tree *t*)
 
==> 77

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

В данном коде реализована рекурсивная функция max-in-tree, которая должна найти максимальное значение в заданном бинарном дереве. Давайте разберём этот код по шагам:

Функция max-in-tree принимает два аргумента: tree — кортеж, представляющий собой бинарное дерево, и x — значение, которое на данный момент считается максимальным.
С помощью cond происходит проверка базовых случаев: — Если car tree и cadr tree оба равны nil, то это означает, что мы достигли листового узла, и значение этого узла (которое равно 12) и будет максимальным. — Если car tree равен nil, а cadr tree не равен nil, то это означает, что мы достигли узла с одним дочерним узлом. В этом случае рекурсивно вызывается max-in-tree для cadr tree, и максимальное значение (7) будет равно 7. — Если cadr tree равен nil, а car tree не равен nil, то это означает, что мы достигли узла с одним дочерним узлом. В этом случае рекурсивно вызывается max-in-tree для car tree, и максимальное значение (8) будет равно 8. — Если ни одно из вышеописанных условий не выполнено, то у нас есть два дочерних узла. В этом случае рекурсивно вызывается max-in-tree для обоих дочерних узлов, и максимальное значение (77) будет равно 77.
В конце функции возвращается максимальное значение, которое было найдено в дереве.
Задаётся пример использования функции: создаётся переменная *t* и инициализируется значением (nil 12 nil) 7 (nil -1 nil) 8 (nil 77 nil).
Вызывается функция max-in-tree с аргументом *t*, и результат (77) выводится на экран.