scheme - 方案：递归广度优先树遍历

Question

我正在努力弄清楚如何在方案中实现广度优先树遍历。我已经用 Java 和 C++ 完成了它。如果我有代码，我会发布它，但我不确定如何开始。

给定下面的树定义，如何使用递归实现广度优先搜索？

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

Answer 1

我敢打赌，当您使用其他语言执行此操作时，您使用了 dfs 的堆栈和 bfs 的队列。当您进行深度优先搜索时，您基本上是使用堆栈来决定接下来要探索哪个节点，而递归为您提供了一个函数调用堆栈，因此很容易概念化两者如何相互镜像。使用广度优先搜索，问题就变成了，如何递归遍历队列？

现在回想一下，任何你可以迭代地做的事情，你都可以递归地做。你可以写“while x < 10: x += 1”，你可以写

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

突然间，您正在递归地进行迭代。伟大的。

所以我们有这个队列。我们把东西放在一端，把东西从另一端拿下来。就像我们在上面的循环中传递循环控制变量 x 一样，您必须显式地传递队列。在下一个“迭代”中，现在成为下一个递归级别，您将希望在队列中放置一些新的孩子，并且下一次递归将把一个孩子从队列的另一端带走，或者停止（返回) 如果没有更多的孩子。

现在调用堆栈不再反映您在树中的位置，因此很难看出为什么递归会更好或更直观，但它总是可能的。

希望有帮助，
格雷姆

Answer 2

0. 这是作业吗？如果是这样，请停止阅读:)。

BFS算法：如果队列为空，则放弃。否则，将队列分为第一个和剩余，检查第一个是否是您想要的，否则使用包含剩余元素和所有新可达元素的队列递归。

当然，我可以在 Scheme 中“说”出同样的句子：

#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. 列表不是一个很好的队列实现。

Answer 3

你可以做这样的事情：有一个递归辅助函数，它到达深度 n，并将元素与一行连接起来......输出将是一个列表，其中包含深度 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)))))

这是未经测试的，并且根据您的参数/lisp 方言可能略有不同，以及您是否想做的不仅仅是测试项目是否在树中，但也许它有助于了解如何去做。