РебенокЛевый Родитель РебенокПравый - Lisp

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

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

Решение задачи: «РебенокЛевый Родитель РебенокПравый»

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

(defun swap-tree (tree)
  (cond ((null tree) nil)
        (t (list (swap-tree (caddr tree)) (cadr tree) (swap-tree (car tree))))))
 
==> swap-tree
 
(swap-tree '(((nil 1 nil) 5 (nil 7 nil)) 10 (nil 15 (nil 16 nil))))
 
==> (((NIL 16 NIL) 15 NIL) 10 ((NIL 7 NIL) 5 (NIL 1 NIL)))

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

В данном коде определён функционал для перебора и разбора бинарных деревьев. Сам функционал, который в коде реализован, называется «обход дерева в ширину» (или «сбалансированный обход», «псевдослучайный порядок», «ленивый обход», «слайсинг», англ. wide traversal, англ. breadth-first search). Этот код реализует рекурсивную функцию swap-tree, которая вызывает саму себя для каждого элемента (листа) дерева. Функция swap-tree принимает на вход ссылку на узел (лист) дерева и возвращает кортеж, состоящий из трех элементов:

Ссылка на левый поддерево (корень левого поддерева, если оно есть).
Значение (свойство) текущего элемента.
Ссылка на правое поддерево (корень правого поддерева, если оно есть). Сама функция вызывается для каждого листа дерева, начиная с корня. Поэтому, если передать в функцию swap-tree ссылку на корень дерева, то в результате получим последовательность кортежей, перебирающих все элементы (листья) дерева в ширину (сначала слева, потом справа). В данном коде, начиная с корня дерева ((nil 1 nil) 5 (nil 7 nil)), сначала будет перебрано левое поддерево (nil 1 nil), затем правое поддерево (nil 7 nil), а затем следующий элемент (nil 15 (nil 16 nil)) и так далее. Для понимания, как работает данная функция, необходимо понимать, что такое ссылка на корень дерева и что такое левое/правое поддерево. Также необходимо понимать, что такое рекурсия и как она работает. Поэтому, если вы что-то не понимаете в данном коде, рекомендую сначала ознакомиться с базовыми понятиями, связанными с деревьями и рекурсией.