查找从树根到叶子的所有路径在方案

所以，对于这种树：

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

具有从根目录（A）到叶（d，E，G）以下路径：

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

如果我表示上文作为树(A (B D E) (C (F G)))则函数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)))))

但是，这看起来完全错误的。我有一段时间没有做过这种想法，但我觉得应该有一个更好的方法来做到这一点。任何想法更好的解决方案（任何语言），将不胜感激。

编辑 - 斯万映射的解决方案到方案提供了：

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

这比我原来的更整洁。

来源

2010-06-10 grifaton

我在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))

来源

2010-06-11 00:07:19 Svante

考虑到它处理具有单个节点的树的方式，这是相当整洁的 - 并且可能更正确：（paths'a）=> （（a）），而（g'a）=>（a）。 CL的地图可以或多或少地等于我的地图2以上？你知道内置的Scheme功能吗？ – grifaton 2010-06-11 07:15:58

我对Scheme的了解不多，但我会猜想像mapcan这样的东西可用。不过，也许它被认为很容易实现。你的'map2'原则上看起来是相同的，但是它的尾部调用错误，所以当列表太长时它会打击栈。也许你应该使用累加器/反向习惯用法。 – Svante 2010-06-11 08:33:20

等同于'mapcan'的方案是来自SRFI-1的'append-map'。 – 2010-06-11 12:14:56

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

来源

2010-06-10 23:35:23 Ismael

我想你误解了我的图 - A是树的根。另外（这个问题可能并不明确），一个节点可以有两个以上的分支，所以我认为你的方法不会奏效。 – grifaton 2010-06-10 23:40:54

我刚刚意识到我误解了你的图表。我会说，如果g函数可以工作，你应该使用:-) – Ismael 2010-06-10 23:42:47

您需要树搜索算法。广度优先或深度优先遍历都可以工作，在这种情况下，由于您需要抓取整个树，所以没有区别。每当你到达叶子时，只需将当前路径存储在结果中。

来源

2010-06-10 23:59:59 Greg

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))))

来源

2010-06-11 08:51:07

查找从树根到叶子的所有路径在方案

回答

相关问题