tree - 检查Common Lisp中的n元树是否平衡

我试图编写代码来检查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函数，只是像basics一样如何解析给定的列表？

最佳答案

这里有一个不使用高阶函数的可能解决方案。
其思想是计算树的最大水平及其最小水平，并检查它们的差异。
为了计算树的最大（或最小）水平，我们使用两个相互递归的函数：第一个计算树的最大（最小）水平，第二个计算其所有子集的最大值（最小值）。
当然，如果一棵树有孩子，那么它的水平是1加上它的孩子的最大（最小）水平。
儿童的功能有两个参数，第一个是其余的孩子要考虑的，第二个是最大值（最小值）的当前值。

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

关于tree - 检查Common Lisp中的n元树是否平衡，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34232817/