Количество всех вершин данного дерева заданной высоты - Lisp

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

Определите функцию, подсчитывающую количество всех вершин данного дерева заданной высоты. Как это сделать?

Решение задачи: «Количество всех вершин данного дерева заданной высоты»

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

(defun tree-count (tree lv)
  (cond ((null tree) 0)
        ((zerop lv) 1)
        (t (+ (tree-count (car tree) (- lv 1))
              (tree-count (caddr tree) (- lv 1))))))
 
==> tree-count
 
(tree-count '(((nil 2 nil) 6 (nil -8 nil)) 7 (nil 12 nil)) 1)
 
==> 2
 
(tree-count '(((nil 2 nil) 6 (nil -8 nil)) 7 (nil 12 nil)) 2)
 
==> 2
 
(tree-count '(((nil 2 nil) 6 (nil -8 nil)) 7 (nil 12 nil)) 3)
 
==> 0

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

В данном коде определен вспомогательный элементарный рекурсивный функционал для подсчета количества вершин в данном дереве с заданной высотой. Функция tree-count принимает два аргумента: tree — кортеж, представляющий собой вершину дерева, и lv — номер текущей вершины дерева. В данном коде реализованы следующие условия:

Если дерево пустое, то возвращается 0.
Если номер вершины равен нулю, то возвращается 1.
В противном случае, рекурсивно вызывается функция tree-count для двух дочерних вершин (car и cadr tree), значение lv уменьшается на 1, и результат рекурсивного вызова суммируется с текущим значением lv. Таким образом, данный код рекурсивно обходит все вершины дерева и подсчитывает количество вершин с заданной высотой. Например, для данного дерева: ((nil 2 nil) 6 (nil -8 nil)) и lv=1, функция вернет 2, так как есть две вершины с высотой 1 (nil 2 nil и (nil 2 nil)). А для данного дерева: ((nil 2 nil) 6 (nil -8 nil)) и lv=2, функция вернет 2, так как есть две вершины с высотой 2 (nil 2 nil и (nil 2 nil)). А для данного дерева: ((nil 2 nil) 6 (nil -8 nil)) и lv=3, функция вернет 0, так как нет вершин с высотой 3.