tree - LISP 二叉树 - 最大深度

Question

使用这种表示树的方式:(A (B) (C (D) (E)))(据我所见，我认为这是标准方式，但我可能错了)。

  A
 / \
 B  C
   / \
   D  E 

我想找到最大深度并构建一个列表，其中包含从根到该级别的节点。对于上面的示例，答案将是 2(根在 0 级)，具有以下两个列表之一:(A C D) 或 (A C E)。

maxdepth 算法应该很简单:

maxdepth( tree ):
    if ( !tree )    return 0
    leftdepth   = maxdepth( left sub-tree )
    rightdepth  = maxdepth( right sub-tree )
    return max ( leftdepth + 1, rightdepth + 1 ) 

所以我尝试了类似的东西:

(defun maxdepth(l)
    (cond
        ((null l) 0)
        ((atom l) 0)
        ((+ 1 (max (maxdepth(car l)) (maxdepth(cdr l)))))
    )
)

CAR 树应该给我左子树，CDR 树应该给我右子树。如果我到达终点或一个原子(这感觉不对)，我就会停下来。我检查 maxdepth(car l) 是否大于 maxdepth(cdr l) 并使用更大的深度。但这给了我上面这棵树的 8 分。我还没有开始构建列表。

我离一个好主意和一个好的实现还有多远？

Answer 1

在您使用的表示中，(car l) 是当前节点，(cadr l) 是左子树，(caddr l ) 是右子树。所以你的递归步骤应该是:

(+ 1 (max (maxdepth (cadr l)) (maxdepth (caddr l)))

您还缺少 cond 的默认子句中的 t 条件。所以完整版应该是:

(defun maxdepth (l)
  (cond ((null l) 0)
        ((atom l) 0)
        (t (+ 1 (max (maxdepth (cadr l)) (maxdepth (caddr l)))))))

(maxdepth '(A (B) (C (D) (E))))

返回 3