LISP二叉树-最大深度

Question

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

  A
 / \
 B  C
   / \
   D  E 

我希望找到最大深度，并用从根到那个级别的节点构造一个列表。对于上面的例子，答案是2(根位于0级)，有以下两个列表之一：(A、C、D)或(A、C、E)。

最大深度算法应该很简单：

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

汽车树应该给我左边的子树，CDR树应该给我右边的树。如果我到了终点或原子(这感觉不对)，我就停下来。我检查最大深度(Car l)是否大于最大深度(Cdr)，并与较大深度(Cdr)进行进一步的分析。但这给了我8个以上的树。我还没有开始构建这个列表。

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

Answer 1

我理解您的要求是，您希望返回两个值:深度和从根到完全深度的一条(任意)路径。这是一个展示如何使用多值语义的好机会。

在根部，骨架看起来如下(假设是一棵二叉树)：

(defun max-depth (tree)
  (if (null (rest tree))
      (values 0 tree)
      (with-sub-depths (left-depth left-path right-depth right-path tree)
        (if (> right-depth left-depth)
            (values (1+ right-depth) (cons (car tree) right-path))
            (values (1+ left-depth) (cons (car tree) left-path))))))

With-sub-depths是目前实际递归的占位符。

假设我们使其正常工作，max-depth将返回所需的两个值。如果我们只调用它并使用它的返回值，我们将得到第一个(主要)值：

(let ((d (max-depth tree)))
  (format t "Depth is ~a." d))

如果我们需要附加值，我们可以使用multiple-value-bind

(multiple-value-bind (depth path) (max-depth tree)
  (format t "Depth is ~a.  Example path: ~s." depth path))

我们现在还需要在递归中使用multiple-value-bind：

(defun max-depth (tree)
  (if (null (rest tree))
      (values 0 tree)
      (multiple-value-bind (left-depth left-path) (max-depth (second tree))
        (multiple-value-bind (right-depth right-path) (max-depth (third tree))
          (if (> right-depth left-depth)
              (values (1+ right-depth) (cons (first tree) right-path))
              (values (1+ left-depth) (cons (first tree) left-path)))))))

在REPL中尝试显示返回的所有值：

CL-USER> (max-depth '(A (B) (C (D) (E))))
2
(A C D)

Answer 2

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

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

您还在您的t的默认子句中缺少了cond条件。因此，完整的版本应该是：

(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