tree - 检查 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，这意味着它是不平衡的。

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

(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

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

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

为了计算树的最大(或最小)层级，我们使用两个相互递归的函数:第一个计算树的最大(最小)层级，第二个计算其所有子树的最大(最小)层级。

当然，如果一棵树有 child ，那么它的级别就是 1 加上它的 child 的最大(最小)级别。

子项函数有两个参数，第一个是要考虑的其余子项，第二个是当前值的最大值(最小值)。

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