查找Scheme中从根到叶子的所有路径

Question

给定一棵树，我想找到从根到每片叶子的路径。

因此，对于这棵树：

    D
   /
  B
 / \ 
A   E
 \
  C-F-G

从根（A）到叶子（D，E，G）有以下路径：

(A B D), (A B E), (A C F G)

如果我将上面的树表示为（A（BDE）（C（FG））） 然后函数 g 就完成了任务：

(define (paths tree)
  (cond ((empty? tree)
         '())
        ((pair? tree)
         (map (lambda (path)
                (if (pair? path)
                    (cons (car tree) path)
                    (cons (car tree) (list path))))
              (map2 paths (cdr tree))))
        (else
         (list tree))))

(define (map2 fn lst)
  (if (empty? lst)
      '()
      (append (fn (car lst))
              (map2 fn (cdr lst)))))

但这看起来完全错误。我已经有一段时间没有进行这种思考了，但我觉得应该有一种更简洁的方法来做到这一点。任何更好的解决方案（任何语言）的想法将不胜感激。

---

编辑 - 将 Svante 的解决方案映射到方案中给出：

(define (paths tree)
  (if (pair? tree)
      (append-map (lambda (node)
              (map (lambda (path)
                     (cons (car tree) path))
                   (paths node)))
            (cdr tree))
      (list (list tree))))

这比我原来的要整洁得多。

Answer 1

我更熟悉 Common Lisp。

(defun paths (tree)
  (if (atom tree)
      (list (list tree))
      (mapcan (lambda (node)
                (mapcar (lambda (path)
                          (cons (car tree) path))
                        (paths node)))
              (cdr tree))))

CL-USER> (paths '(A (B D E) (C (F G))))
((A B D) (A B E) (A C F G))

Answer 2

Svante 答案的 R5RS 翻译：

(define (accumulate op init seq)
  (define (iter ans rest)
    (if (null? rest)
        ans
        (iter (op ans (car rest))
              (cdr rest))))
  (iter init seq))

(define (flatten seq)
  (accumulate append '() seq))

(define (flatmap op seq)
  (flatten (map op seq)))

(define (atom? x)
  (not (pair? x)))

(define (paths tree)
  (if (atom? tree)
      (list (list tree))
      (flatmap (lambda (node)
                 (map (lambda (path)
                        (cons (car tree) path))
                      (paths node)))
               (cdr tree))))

Answer 3

我认为您可以将示例树定义为（根左右）每个树都是一个列表。所以你的示例树将是： (D (B (A () (C () (F () G ) ) ) E) () ) 并且更容易遍历

Answer 4

您需要一个树搜索算法。广度优先或深度优先遍历都可以，在这种情况下没有区别，因为您需要爬行整个树。每当您到达叶子时，只需将当前路径存储在结果中即可。