Схема: рекурсивная ширина первого обхода дерева

Question

Я дергаю себя за волосы, пытаясь понять, как реализовать обход схемы первого дерева в ширину. Я сделал это на Java и C ++. Если бы у меня был код, я бы опубликовал его, но я не уверен, как именно начать.

Учитывая приведенное ниже определение дерева, как реализовать поиск в ширину с помощью рекурсии?

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

Answer 1

Бьюсь об заклад, когда вы делали это на других языках, вы использовали стек для dfs и очередь для bfs. Когда вы выполняете поиск в глубину, вы в основном используете стек, чтобы решить, какой узел следует исследовать следующим, а рекурсия дает вам стек вызовов функций, поэтому легко понять, как эти два отражают друг друга. При первом поиске по ширине возникает вопрос: как вы рекурсивно пересекаете очередь?

Теперь вспомните, что все, что вы можете делать итеративно, вы можете делать рекурсивно. Там, где вы можете написать «пока x <10: x + = 1», вместо этого вы можете написать </p>

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

и вдруг вы делаете итерацию рекурсивно. Отлично.

Итак, у нас есть эта очередь. Мы кладем вещи с одного конца, снимаем вещи с другого. Точно так же, как мы обошли переменную управления циклом x в цикле выше, вам придется явно обойти очередь. В следующей «итерации», которая теперь становится следующим уровнем рекурсии, вы захотите поместить несколько новых дочерних элементов в очередь, и эта следующая рекурсия выведет одного дочернего элемента из другого конца очереди или остановит ) если детей больше нет.

Теперь стек вызовов больше не отражает ваше местоположение в дереве, поэтому трудно понять, почему рекурсия была бы лучше или интуитивнее, но это всегда возможно.

Надеюсь, это поможет,
Grem

Answer 2

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) списки не являются хорошей реализацией очереди.

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, а также если вы хотите сделать больше, чем просто проверить, есть ли элемент в дереве, но, возможно, это поможет понять, как сделай это.