Geek Answers Handbook

Calculating the depth of a binary tree in LISP is recursive

I have the following binary tree

  A
  / \
  BC
    / \
   DE

is represented as a list in Lisp (A 2 B 0 C 2 D 0 E 0), where the letters are node names and the numbers are the number of child nodes (0 for none, 1 one node, 2 two nodes). I need to find the maximum from the root node to the depth of the tree leaf (the depth of the binary tree that is) recursively. I am new to Lisp and I cannot figure out how to implement it. This is what I still manage to find:

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

but it does not work correctly. I also looked at similar posts, but I did not find anything useful that could help me. Can someone give me a suggestion to help figure this out? Thanks!

PS This is part of a small project that I will be presenting at the University, but also my own way of improving in Lisp (I saw that many similar posts had questions related to whether the message was related to homework). :)

+4
source share
4 answers

First I convert the list to a tree:

(defun tlist->tree (tlist) "Transforms a tree represented as a kind of plist into a tree. A tree like: A / \ BC / / \ FDE 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)))

I wonder if you start with this tree view.

Then, searching for the depth of the tree in the tree view is a simple recursive single-line layer.

+2
source

How about this? No tree conversion required.

 (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

Another version:

 (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)
+3
source

Here's one in a sequel style:

 (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)))))
+1
source

Using Artelius and Svante, I managed to solve the problem. Here is the code, maybe it will be useful to someone else.

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

Thanks to Artelius and Svante for your help!

0
source

More articles:


All Articles