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

Question

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

 
    A 
/\ 
B C 
/\ 
    D E 

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

 
(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. Это часть небольшого проекта, который я буду представлять в Университете, но также и мой собственный способ стать лучше в Lisp (я видел, что на многих похожих постов были вопросы, задающие вопрос о том, связано ли сообщение с домашней работой). :)

Answer 1

Я бы первый преобразовать список в дерево:

(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 2

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

 
(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)))) 

Спасибо Artelius и Svante за помощь!

Answer 3

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

(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 4

Вот один в продолжающей мимолетной стиле:

(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)))))