检查Common Lisp中的n元树是否平衡 [英] Check if n-ary tree is balanced in Common Lisp

问题描述

我正在尝试编写代码以检查n元树是否处于平衡状态. 树是这样给出的:

I'm trying to write the code to check whether an n-ary tree is balanced or not in clisp. The tree is given like this:

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

如下所示:

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

那将会是不平衡的.

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

I was thinking about solving it using something like:

• 一个字母的所有叶子的最大水平-所有叶子的最小水平不应大于1.

• the max level of all leaves of a letter - the min level of all leaves shouldnt be bigger than 1.

我考虑过首先将此规则应用于A，B，C.如果差异不大于1，则检查E，F，G，直到我检查了所有可能的字母并且树是平衡的，或者我得到的差异大于1，这意味着它是不平衡的.

I thought about applying this rule for A,B,C first. If the difference is not bigger than 1, then check for E,F,G until I either checked all the possible letters and the tree is balanced or I got a difference bigger than 1 which means it's unbalanced.

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

This is the code for the min/max level:

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

)

我不知道如何解析列表并应用我的规则.我不应该仅使用基础知识就使用map/lamba函数.如何解析给定列表?

I don't know how to parse the list and apply my rule. I shouldn't be using map/lamba functions, only like basics. How to parse the given list?

推荐答案

以下是不使用高阶函数的可能解决方案.

Here is a possible solution that does not use higher order functions.

这个想法是要计算一棵树的最大水平及其最小水平，并检查它们之间的差异.

The idea is to calculate the maximum level of a tree and its minimun level, and check their difference.

要计算树的最大(或最小)级别，我们使用两个相互递归的函数:第一个计算树的最大(最小)级别，第二个计算所有子级的最大(最小)级别.

To calculate the maximum (or minimun) level of a tree we use two mutually recursive functions: the first calculates the maximun (minimun) level of tree, the second calculates the maximum (minimun) of all its children.

当然，如果一棵树有子级，则其级别为1加其子级的最大(最小)级别.

Of course, if a tree has children, then its level is 1 plus the maximum (minimun) level of its children.

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

The function for the children has two parameters, the first one is the rest of the children to be considered, the second one is the current value of the maximum (minimum).

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

这是用于完美平衡的树木.如果您允许两棵树之间的差异最大为一棵的树，则将最后一个函数替换为:

This is for perfectly balanced trees. If you allow trees with difference of at most one between the levels of the tree, then substitute the last function with:

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

这篇关于检查Common Lisp中的n元树是否平衡的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！