0

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

(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，这意味着它不平衡。

这是最小/最大级别的代码：

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

)

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

4

2 回答 2

1

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

这个想法是计算一棵树的最大级别和它的最小级别，并检查它们的差异。

为了计算树的最大（或最小）级别，我们使用两个相互递归的函数：第一个计算树的最大（最小）级别，第二个计算其所有子节点的最大（最小）级别。

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

对于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))
于 2015-12-11T23:17:06.767 回答
0

我以前的解决方案效率不高，原因有两个：

  1. 这棵树被访问了两次，
  2. 一旦发现从根到叶的路径违反了平衡条件，该算法就不会停止。

所以，这是一个更有效的解决方案，它只访问树一次，一旦发现路径太短或太长就停止。

基本思想是：

  1. 所有工作都由一个min-max返回几个值的内部函数执行：以函数的当前参数为根的子树的最小深度和最大深度，这允许只访问树一次；

  2. 在每次递归调用时，该函数接收当前级别、当前最小级别和当前最大级别，以便它可以尽快检查树是否不平衡并且必须立即停止访问。对于节点的第一个子节点，当前最大值和最小值设置为nil（因此我定义了两个辅助函数，即使第二个参数是 也计算最小值或最大值nil）。

请注意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))))

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

于 2015-12-22T07:41:59.810 回答