Common lisp 树中的最低级别

Question

我正在尝试编写代码来查找树中的最小级别（嵌套子列表的最小数量）树是这样给出的：

(A (B (E (I))(F))(C (G))(D))

看起来像：

      A
   /  |  \
  B   C   D
 /\   |   
E  F  G   
|
I

这会导致...级别 1。最高级别是级别 3，但我只需要最低级别。

我尝试使用 min 函数，但无论我做什么，它都会 return 1 或 0 因为如果列表为空，我 return 0 和 min（0 或任何东西）总是0. 没有 mapping/lambda 函数如何解决这个问题的任何想法？

我试过这样做：

(defun nrlevels (tail)
  (cond
    ((null tail) 0)
    ((listp (car tail))
     (min (+ 1 (nrlevels (car tail)))
          (nrlevels (cdr tail)))) 
    (t (nrlevels (cdr tail)))))

但是正如我所说，min 将（最终）比较 0 和 0 是最小值的东西，最终结果将是 0。我不知道如何跳出这个循环。

Answer 1

您将级别递归和表示对节点 children 的迭代的递归都放入单个递归中。问题是区分没有 children 的访问节点和已经到达 children 列表末尾的访问节点。

你需要把这些东西分开。我发现将 children 列表上的迭代放入 loop:

中最简单

(defun minimum-child-level (tree)
  (if (atom tree)
      0
      (1+ (loop :for child :in tree
                :when (listp child)
                :minimize (minimum-child-level child)))))

或reduce:

(defun minimum-child-level (tree)
  (if (atom tree)
      0
      (1+ (reduce #'min
                  (mapcar #'minimum-child-level
                          (remove-if-not #'listp tree))))))

编辑： 您可以通过解释 min 累加器并以一种或另一种方式递归来做到这一点，但我不建议这样做生产代码：

(defun minimum-child-level (tree &optional min-so-far)
  (cond ((endp tree)         ; end of child list
         (if min-so-far
             (1+ min-so-far) ; there were children
             0))             ; no children
        ((atom (first tree)) ; ignore symbols, go to next child
         (minimum-child-level (rest tree) min-so-far))
        (t                   ; sublist
         ;; recurse into child
         (let ((child-minlevel (minimum-child-level (first tree))))
           ;; go to next child
           (minimum-child-level (rest tree)
                                (if min-so-far
                                    (min min-so-far child-minlevel)
                                    child-minlevel))))))

Common lisp 树中的最低级别

Minimum level in a tree in Common lisp

lisp

tree

list

common-lisp

min