方案：遞歸寬度第一棵樹遍歷

Question

我拉我的頭髮試圖找出如何在計劃中實現廣度第一遍樹遍歷。我已經在Java和C++中完成了它。如果我有代碼，我會發布它，但我不知道如何開始。

鑑於下面的樹定義，如何使用遞歸實現廣度優先搜索？

(define tree1 '(A (B (C()()) (D()())) (E (F()()) (G()())))) 

Answer 1

我敢打賭，當你在其他語言中使用堆棧來存儲dfs和bfs隊列時，當你進行深度優先搜索時，你基本上使用堆棧來決定接下來探索哪個節點，並且遞歸給你一個函數調用堆棧，因此很容易概念化兩者如何相互映射。隨着寬度的第一次搜索，問題就變成了，你如何遞歸地遍歷一個隊列？

現在回想一下，你可以迭代地做任何事情，你可以遞歸地做。在這裏你可以寫「而X < 10：X + = 1」，你可以代替寫

(define (my-loop x) 
    (if (< x 10) 
     (my-loop (+ x 1)) 
     ... ;; your base case 
    )) 

，突然你做遞歸迭代。大。

所以我們有這個隊列。我們把事情放在一端，把事情從另一端拿下來。就像我們在上面的循環中傳遞循環控制變量x一樣，您必須顯式傳遞隊列。在下一個「迭代」中，現在成爲遞歸的下一個級別，您需要在隊列中放置一些新的子元素，並且下一個遞歸將從隊列的另一端取出一個子元素，或者停止（返回）如果沒有更多的孩子。

現在調用堆棧不再反映您在樹中的位置，因此很難明白爲什麼遞歸會更好或更直觀，但始終可能。

希望幫助，
GREM

Answer 2

你可以做這樣的事情： 有進入深度n遞歸輔助函數，並concats與行的元素...輸出將是一個列表與深度n的樹的所有元素。

(defun findAtN (tree n) 
(cond ((equal tree nil) nil) 
     ((equal (n 0)  (car tree)) 
     (t    (append (findAtN (cadr tree) (- n 1)) 
           (findAtN (caddr tree) (- n 1)))))) 

然後增加深度的第二個函數，搜索給定節點的每個級別。

(defun ContainsElt (tree Elt n) 
(cond ((equal (findAtN tree n) nil) nil) 
     ((member Elt (findAtN tree n)) true) 
     (t        (ContainsElt tree Elt (+ n 1))))) 

這是未經測試並可能略有不同根據您的參數/口齒不清的方言，以及如果你想要做的不僅僅是測試，如果一個項目是樹，但也許它會與幫助爲一個想法如何去做。

Answer 3

0）這是功課嗎？如果是這樣，請停止閱讀:)。

BFS算法：如果隊列爲空，放棄。否則，將隊列分爲第一個和剩餘的，檢查第一個是否是您想要的，否則重複包含剩餘元素的隊列以及所有可訪問的隊列。

當然，我可以 「說」 的方案同一句話：

 
#lang scheme 

(define (bfs pred queue) 
    (match queue 
    [empty #f] 
    [(cons elt queue-rest) 
    (or (pred elt) 
     (bfs pred (append queue-rest (remove* queue-rest (reachable-from elt)))))])) 

1）沒有經過測試的，幾乎可以肯定越野車（本書雖然不是衡量論的意義:)）

2 ）你需要你自己的圖形表示&「可到達 - 從」。

3）列表不是很好的隊列實現。