LISP의 이진 트리의 깊이를 계산 재귀

Question

I는 다음의 이진 트리 문자 노드 이름은 리스프 (A 2 B 0 C 2 D 0 E 0)의리스트로 표시

 
    A 
/\ 
B C 
/\ 
    D E 

을 숫자는 자식 노드의 수입니다 (0이면 none, 1 노드가 1, 2 노드가 2). 루트 노드에서 트리 깊이 (이진 트리 깊이)를 재귀 적으로 발견해야합니다. 저는 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. 이것은 내가 대학에서 선물 할 작은 프로젝트의 일부이지만, 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))) 

당신이 시작하는이 트리 표현으로 시작하지 수 있는지가 궁금합니다.

그런 다음, 트리 표현 트리의 깊이를 찾는 것은 간단한 재귀 한 줄입니다. Artelius의 및 반테의 답변을 사용

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