Подсчет листьев в дереве - Lisp
Формулировка задачи:
Привет всем!
Было задание написать функцию (countt t), считающую количество листьев у в бинарном дереве t.
Я попробовал написать следующим образом:
Функция вроде бы прошла без ошибок, а вот если ввести значения дерева:
Выбивает ошибку. Как поправить?
(defun countrr (t (tree) (cond ( (nullL tree) 0 ) ( (equal (cdr tree) (list NIL NIL)) 1 ) ( T (+ (countrr (left tree)) (countrr (right tree))) ) ) ))
(countrr'((5(3(1 NIL NIL)(4 NIL NIL))(7(6 NIL NIL)(13(11 NIL NIL)(15 NIL NIL))))))
Решение задачи: «Подсчет листьев в дереве»
textual
Листинг программы
(defun lcounter (tree) (cond ((null tree) 0) ((and (null (cadr tree)) (null (caddr tree))) 1) (t (+ (lcounter (cadr tree)) (lcounter (caddr tree))))))
Объяснение кода листинга программы
В данном коде реализована функция lcounter
, которая подсчитывает количество листьев в древовидной структуре.
Вложенные условные конструкции cond
проверяют следующие условия:
- Если переданный аргумент
tree
равенnil
, то возвращается 0. Это происходит в случае, когда дерево пустое. - Если второй и третий элементы дерева (соответственно
cadr
иcaddr
дерева) также равныnil
, то возвращается 1. Это условие покрывает случай, когда у дерева есть только один узел (лист). - В противном случае, то есть когда дерево не является пустым и имеет два или более узла, функция рекурсивно вызывает саму себя, передавая в качестве аргументов
cadr
иcaddr
дерева, и возвращает результат их вызова, увеличенный на результат вызова функции дляcadr
иcaddr
дерева. Таким образом, функцияlcounter
выполняет обход дерева по узлам, подсчитывая количество листьев.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д