Подсчет листьев в дереве - 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 проверяют следующие условия:

  1. Если переданный аргумент tree равен nil, то возвращается 0. Это происходит в случае, когда дерево пустое.
  2. Если второй и третий элементы дерева (соответственно cadr и caddr дерева) также равны nil, то возвращается 1. Это условие покрывает случай, когда у дерева есть только один узел (лист).
  3. В противном случае, то есть когда дерево не является пустым и имеет два или более узла, функция рекурсивно вызывает саму себя, передавая в качестве аргументов cadr и caddr дерева, и возвращает результат их вызова, увеличенный на результат вызова функции для cadr и caddr дерева. Таким образом, функция lcounter выполняет обход дерева по узлам, подсчитывая количество листьев.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 4.143 из 5
Похожие ответы