Рекурсивный расчет глубины двоичного дерева в LISP

Question

У меня есть следующее двоичное дерево

  A
 / \
 B  C
   / \
  D   E

представлен в виде списка в Лиспе (A 2 B 0 C 2 D 0 E 0), где буквы - это имена узлов, а числа - это количество дочерних узлов (0 для ни одного, 1 один узел, 2 два узла). Мне нужно найти наибольшую от корневого узла до листа глубину дерева (глубину бинарного дерева) рекурсивно. Я довольно новичок в Лиспе и не могу понять, как это реализовать. Вот что мне до сих пор удается придумать:

(defun depth (tree)
  "Returns the depth of the argument tree."
  (check-type tree list)
  (if (= (second tree) 0)
    0
    (1+ (get-btree-max-depth (cddr tree)))))

(defun get-btree-max-depth (btree)
  "Returns the maximum depth
   of the argument tree."
  (check-type btree list)
  (if (= (second btree) 0)
    0
    (max (depth (cddr btree))
         (get-btree-max-depth (cddr btree))))) 

но это не работает должным образом. Я также просматривал подобные сообщения, но не нашел ничего полезного, что могло бы мне помочь. Может ли кто-нибудь дать мне предложение, чтобы помочь выяснить это? Спасибо!

P.S. Это часть небольшого проекта, который я представлю в университете, но также и мой собственный путь к улучшению в Лиспе (я видел, что у многих похожих постов были вопросы, спрашивающие, связано ли это с домашней работой). :)

Answer 1

Как насчет этого? Не нужно преобразовывать дерево.

(defun depth-rec (tree)
  (labels ((depth-rec-aux (depth)             ; self-recursive function
             (if (null tree)                  ; no more nodes
                 depth                        ;   -> return the current depth
               (let ((n (second tree)))       ; number of subnodes
                 (pop tree) (pop tree)        ; remove the current node
                 (case n
                   (0 (1+ depth))                     ; no subnode,  1+depth
                   (1 (depth-rec-aux (1+ depth)))     ; one subnode, its depth+1
                   (2 (max (depth-rec-aux (1+ depth)) ; two subnodes, their max
                           (depth-rec-aux (1+ depth)))))))))
    (depth-rec-aux 0)))                       ; start depth is 0

Другая версия:

(defun depth-rec (tree &aux (max 0))
  (labels ((depth-rec-aux (depth)
             (when tree
               (pop tree)
               (let ((n (pop tree)))
                 (if (zerop n)
                     (setf max (max max (1+ depth)))
                   (loop repeat n do (depth-rec-aux (1+ depth))))))))
    (depth-rec-aux 0))
  max)

Answer 2

Сначала я бы преобразовал список в дерево:

(defun tlist->tree (tlist)
  "Transforms a tree represented as a kind of plist into a tree.
   A tree like:
               A
              / \
             B   C
            /   / \
           F   D   E
   would have a tlist representation of (A 2 B 1 F 0 C 2 D 0 E 0).
   The tree representation would be (A (B (F)) (C (D) (E)))"
  (let (tree)
    (push (pop tlist) tree)
    (dotimes (i (pop tlist))
      (multiple-value-bind (subnode rest-tlist) (tlist->tree tlist)
        (push subnode tree)
        (setf tlist rest-tlist)))
    (values (nreverse tree) tlist)))

Интересно, не могли бы вы начать с этого древовидного представления?

Тогда, нахождение глубины дерева в представлении дерева является простой рекурсивной однострочностью.

Answer 3

Вот один в стиле продолжения:

(defun oddtree-height (oddtree)
  (suboddtree-height oddtree
                     #'(lambda (h remainder)
                         (if (null remainder) h nil))))

(defun suboddtree-height (oddtree c)
  (max-height-of-suboddtrees (cadr oddtree)
                             0
                             (cddr oddtree)
                             #'(lambda (h remainder)
                                 (funcall c (+ h 1) remainder))))

(defun max-height-of-suboddtrees (n best oddtree c)
  (if (= n 0)
      (funcall c best oddtree)
    (suboddtree-height oddtree
                       #'(lambda (h remainder)
                           (max-height-of-suboddtrees (- n 1) (max best h) remainder c)))))

Answer 4

Используя ответ Артелия и Сванте, мне удалось решить проблему. Вот код, возможно, он поможет кому-то еще нуждающемуся.

(defun btree-max-depth (btree)
  "Returns the maximum depth
  of the binary tree."
  (check-type btree list)
  (if (null btree)
    0 ; the max depth of the members of ()
    (max (depth (first btree))
      (btree-max-depth (rest btree)))))

(defun depth (tree)
  "Returns the depth of the argument TREE."
  (if (atom tree)
    0 ; an atomic tree has a depth of 0
    (1+ (btree-max-depth tree))))

Спасибо Артелиусу и Сванте за помощь!