检查 Common Lisp 中的 n 叉树是否平衡

Question

我正在尝试编写代码来检查 clisp 中的 n 叉树是否平衡。树是这样给出的：

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

看起来像：

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

这将是不平衡的。

我正在考虑使用类似的方法解决它：

一个字母的所有叶子的最大层级-所有叶子的最小层级不应大于1。
我考虑先将此规则应用于 A、B、C。如果差异不大于 1，则检查 E、F、G，直到我检查了所有可能的字母并且树是平衡的，或者我得到的差异大于 1，这意味着它是不平衡的。

这是 min/max 级别的代码：

(defun nrlvlmax (tail) 
(cond 
    ( (null tail) 0)
    ( (listp (car tail)) (max ( + 1 (nrlvl (car tail))) (nrlvl (cdr tail))))
    ( t (nrlvl (cdr tail)))
)

)

我不知道如何解析列表并应用我的规则。我不应该使用 map/lamba 功能，只喜欢基础功能。如何解析给定的列表？

Answer 1

这是一个不使用高阶函数的可能解决方案。

思路是计算一棵树的最高等级和最低等级，并检查它们的差异。

为了计算一棵树的最大（或最小）层级，我们使用两个相互递归的函数：第一个计算树的最大（最小）层级，第二个计算其所有树的最大（最小）层级 children.

当然，如果一棵树有children，那么它的等级就是1加上它的children的最高（最低）等级。

这个函数对于children有两个参数，第一个是children剩下的要考虑的，第二个是当前值的最大值（最小值）。

(defun maxlevel(tree)
  (cond ((null tree) 0)
        ((null (cdr tree)) 1)
        (t (1+ (max-for-children (cddr tree) (maxlevel (cadr tree)))))))

(defun max-for-children(children current-max)
  (if (null children)
      current-max
      (max-for-children (cdr children) (max current-max (maxlevel (car children))))))

(defun minlevel(tree)
  (cond ((null tree) 0)
        ((null (cdr tree)) 1)
        (t (1+ (min-for-children (cddr tree) (minlevel (cadr tree)))))))

(defun min-for-children(children current-min)
  (if (null children)
      current-min
      (min-for-children (cdr children) (min current-min (minlevel (car children))))))

(defun balanced(tree)
  (= (maxlevel tree) (minlevel tree)))

这是为了完美平衡的树。如果您允许树的层次之间最多相差一个，则将最后一个函数替换为：

(defun balanced(tree)
  (<= (abs (- (maxlevel tree) (minlevel tree))) 1))

Answer 2

我的效率不高有两个原因：

树被访问了两次，
算法不会在发现从根到叶子的路径违反平衡条件时立即停止。

所以，这是一个更有效的解决方案，只访问树一次，并在发现路径太短或太长时立即停止。

基本思路是：

所有工作都由内部函数 min-max 执行，该函数 returns 有几个值：以函数当前参数为根的子树的最小深度和最大深度, 这只允许访问树一次;
在每次递归调用时，函数接收当前层级、当前最小层级和当前最大层级，以便它可以尽快检查树是否不平衡并且访问必须是立刻停了下来。对于节点的第一个子节点，当前的最大值和最小值设置为 nil（为此我定义了两个辅助函数，即使第二个参数是 nil 也可以计算最小值或最大值）。

注意主函数returns或者nil，如果树是不平衡的，或者树的最小深度。

(defun mymin(x y)
  (if y (min x y) x))

(defun mymax(x y)
  (if y (max x y) x))

(defun balanced(tree)
  (labels ((min-max(tree current-level current-min current-max)
             (when (and current-min (> (1- current-level) current-min))
                (return-from balanced nil))                  ; this path is too long
             (if (null (cdr tree))                           ; if it is a leaf node
                 (if (and current-max (< (1+ current-level) current-max))
                     (return-from balanced nil)              ; this path is too short
                     (values current-level current-level))   ; return normally
                 (loop for child in (cdr tree)               ; find min-max for each child
                    do (multiple-value-bind (min1 max1)
                           (min-max child (1+ current-level) current-min current-max)
                         (setf current-min (mymin min1 current-min)
                               current-max (mymax max1 current-max)))
                    finally (return (values current-min current-max))))))
    (values (min-max tree 0 nil nil))))

最后，注意函数使用了循环。可以生成递归版本，但这只会使解决方案复杂化并使其不自然。

检查 Common Lisp 中的 n 叉树是否平衡

Check if n-ary tree is balanced in Common Lisp

tree

lisp

common-lisp

balance