查找树中子节点的最大数量

首先，我应该明确指出，这是学术项目所必需的。我正在尝试使用Common Lisp来查找树中任何节点的最大子节点数。查找树中子节点的最大数量

我当前的代码如下所示 - 我不是在它的逻辑100％，但我觉得它应该工作，但它是不是给我需要的结果。

(defun breadth (list y) 
    (setf l y) 
     (mapcar #'(lambda (element) 
       (when (listp element) 
     (when (> (breadth element (length element)) l) 
      (setf l (breadth element (length element))) 
      ))) list) 

l) 

(defun max-breadth(list) 
    (breadth list (length list)) 
)

举个例子，运行

(max-breadth '(a ((b (c d)) e) (f g (h i) j)))

应该返回4.

编辑：跟踪结果与实际的返回值，似乎忘记了：

CG-USER(13): (max-breadth '(a ((b (c d)) e) (f g (h i) j))) 
0[6]: (BREADTH (A ((B (C D)) E) (F G (H I) J)) 3) 
    1[6]: (BREADTH ((B (C D)) E) 2) 
    2[6]: (BREADTH (B (C D)) 2) 
     3[6]: (BREADTH (C D) 2) 
     3[6]: returned 2 
    2[6]: returned 2 
    1[6]: returned 2 
    1[6]: (BREADTH (F G (H I) J) 4) 
    2[6]: (BREADTH (H I) 2) 
    2[6]: returned 2 
    1[6]: returned 2 
0[6]: returned 2 
2

没有人有任何想法，我会出错？我怀疑它与第二个条件有关，但我不确定。

来源

2011-01-14 Jim

如果它没有返回4，它会返回什么？ 6？ – FrustratedWithFormsDesigner 2011-01-14 20:51:35

对不起，错过了，添加了追踪结果。 – Jim 2011-01-14 20:56:40

记住，你不应该设置任何地方没有定义的变量。（SETF l ...）就是这样的情况。 l没有在你的代码中引入。它不是一个局部变量，没有全局变量，它不是函数参数，... – 2011-01-14 23:01:59

首先，标准格式：

(defun breadth (list y) 
    (setf l y) 
    (mapcar #'(lambda (element) 
       (when (listp element) 
       (when (> (breadth element (length element)) l) 
        (setf l (breadth element (length element)))))) 
      list) 
    l) 

(defun max-breadth (list) 
    (breadth list (length list)))

你的问题是(setf l y)，这应该给你一个警告有关l是不确定的。 Setf不应该用于未绑定的变量。使用let做一个词汇范围：

(defun breadth (list y) 
    (let ((l y)) 
    (mapcar #'(lambda (element) 
       (when (listp element) 
        (when (> (breadth element (length element)) l) 
        (setf l (breadth element (length element)))))) 
      list) 
    l))

然后，而不是两个嵌套when，使用单一的一个and：

   (when (and (listp element) 
         (> (breadth element (length element)) 1)) 
       (setf l (breadth element (length element))))

我发现这里dolist更简洁：

(dolist (element list) 
    (when (and (listp element) 
       (> (breadth element (length element)) l)) 
     (setf l (breadth element (length element)))))

参数y始终是参数list的长度，所以此调用可以是SIM卡plified。你也不需要别名y：

(defun breadth (list &aux (y (length list))) 
    (dolist (element list) 
    (when (and (listp element) 
       (> (breadth element) y)) 
     (setf y (breadth element)))) 
    y)

您可以消除通过let双递归调用，但我们可以在这里使用max：

(defun breadth (list &aux (y (length list))) 
    (dolist (element list) 
    (when (listp element) 
     (setf y (max y (breadth element))))) 
    y)

您也可以使用reduce此：

(defun breadth (l) 
    (if (listp l) 
     (reduce #'max l 
       :key #'breadth 
       :initial-value (length l)) 
     0))

来源

2011-01-14 22:52:22 Svante

是不是正确答案6？既然你的例子中的e和j在技术上也是子节点？如果这就是你如何定义你的问题，下面的解决方案应该让你有：

(defun max-breadth (lst) 
    (cond 
    ((atom lst) 0) 
    ((every #'atom lst) (length lst)) 
    (t (+ (max-breadth (car lst)) (max-breadth (cdr lst))))))

版本2：

(defun max-breadth (lst) 
    (cond 
    ((atom lst) 0) 
    ((every #'atom lst) (length lst)) 
    (t (+ 
     (max-breadth (car lst)) 
     (max-breadth (remove-if-not #'consp (cdr lst)))))))

来源

2011-01-14 21:49:06 yan

我可能没有足够好地解释这个问题 - 在给出的例子中，根节点有三个节点，其中一个节点分支分成4个节点（FG（HI）J）。这是树中任何父节点的最大子节点数，这正是我所追求的。如果你看上面的轨迹，y参数代表正确的节点数，其中4是最高的。问题在于，如果随后发生，它似乎会用2覆盖该值。 – Jim 2011-01-14 22:03:50

L不是一个局部变量，因此函数会返回一个值分配给它（即，最后一个子树的宽度）。

使用LET声明一个局部变量：

(LET ((l y)) 
    ... 
)

来源

2011-01-14 22:50:56 angus

查找树中子节点的最大数量

回答

相关问题