Проверка упорядоченности двоичного дерева - Lisp

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

Дано S-выражение, представляющее дерево вида "(РебенокЛевый Родитель РебенокПравый)" с числами в качестве вершин. Определить функцию для проверки упорядоченности бинарного дерева, т.е. возвращающая Т, если дерево упорядочено, Nil -нет. Например, если дано '(((nil 1 nil) 5 (nil 7 nil)) 10 (nil 15 (nil 16 nil))), ответом будет "Т".

Решение задачи: «Проверка упорядоченности двоичного дерева»

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

(defun is-ordered (tree)
  (cond ((null tree) t)
        (t (let ((v      (cadr tree))
                 (l-tree (car tree))
                 (r-tree (caddr tree)))
             (cond ((and l-tree r-tree) 
                    (and (>= v (cadr l-tree))
                         (<= v (cadr r-tree))
                         (is-ordered l-tree)
                         (is-ordered r-tree)))
                   (l-tree (and (>= v (cadr l-tree)) (is-ordered l-tree)))
                   (r-tree (and (<= v (cadr r-tree)) (is-ordered r-tree)))
                   (t t)))))) 
 
==> is-ordered
 
(is-ordered '(((nil 1 nil) 5 (nil 7 nil)) 10 (nil 15 (nil 1 nil))))
 
==> NIL
 
(is-ordered '(((nil 1 nil) 5 (nil 7 nil)) 10 (nil 15 (nil 16 nil))))
 
==> T

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

В коде определён вспомогательный числовой рекурсивный функция (ВЧРФ) is-ordered для проверки упорядоченности двоичного дерева. is-ordered принимает два аргумента: tree — кортеж, представляющий двоичное дерево, и счётчик, который следит за глубиной рекурсии. Если дерево пустое, то есть если его корневой узел равен nil, то функция возвращает t. Если дерево не пустое, то есть если его корневой узел не равен nil, то функция возвращает значение, полученное с помощью вызова рекурсивной функции is-ordered для левого поддерева и правого поддерева, которые получаются с помощью доступа к соответствующим полям кортежа tree. Если левое поддерево и правое поддерево упорядочены, то есть если для каждого узла в левом поддереве значение в поле car меньше значения в поле cadr, а для каждого узла в правом поддереве значение в поле car больше значения в поле cadr, то рекурсивная функция возвращает t. Если левое поддерево упорядочено, то есть если для каждого узла в левом поддереве значение в поле car меньше значения в поле cadr, то рекурсивная функция возвращает результат вызова функции is-ordered для левого поддерева. Если правое поддерево упорядочено, то есть если для каждого узла в правом поддереве значение в поле car больше значения в поле cadr, то рекурсивная функция возвращает результат вызова функции is-ordered для правого поддерева. Если ни одно из условий не выполняется, то рекурсивная функция возвращает nil.