查找樹中子節點的最大數量

首先，我應該明確指出，這是學術項目所必需的。我正在嘗試使用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

查找樹中子節點的最大數量

回答

相關問題