如何形成树成单独的路径通向每个叶

我得到了一棵树：如何形成树成单独的路径通向每个叶

(A . ((C . ((D . nil)(E . nil))) 
     (B . ((F . nil)(G . nil)))))

我想这棵树变成：

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

我已经实现了这个功能，这样做的：

(defun tree->paths (tree &optional buff) 
    (labels ((recurse (follow-ups extended-list) 
      (if follow-ups 
       (append (list (tree->paths (car follow-ups) extended-list)) 
         (recurse (cdr follow-ups) extended-list)) 
       nil))) 
    (rstyu:aif (cdr tree) 
       (recurse it (append buff (list (car tree)))) 
       (append buff (list (car tree))))))

但应用它导致：

(tree->paths '(A . ((C . ((D . nil) (E . nil))) 
        (B . ((F . nil) (G . nil)))))) 
=> 
(((A C D) (A C E)) ((A B F) (A B G)))

我必须在递归中缺少某种附加/合并，但我没有看到它。

来源

2013-01-20 Sim

在这里，我试图重写它，以便它线性工作（因为你的原始函数会耗尽堆栈空间）。然而，在这样做时，我发现的东西，你可能在通用再保你最初的想法考虑：

(defun tree-to-paths (tree) 
    (loop with node = tree 
     with trackback = nil 
     with result = nil 
     with head = nil 
     with head-trackback = nil 
     while (or node trackback) do 
     (cond 
     ((null node) 
      (setf node (car trackback) 
       trackback (cdr trackback) 
       result (cons head result) 
       head (car head-trackback) 
       head-trackback (cdr head-trackback))) 
     ((consp (car node)) 
      (setf trackback (cons (cdr node) trackback) 
       head-trackback (cons head head-trackback) 
       head (copy-list head) 
       node (car node))) 
     (t (setf head (cons (car node) head) 
        node (cdr node)))) 
     finally (return (nreverse (mapcar #'nreverse result)))))

在您的示例数据要接收的结果似乎直觉是正确的，但你能想到的它也好像有更多的路径，例如：

A -> C -> NIL - 从查看您的数据，这个结果似乎是多余的，但一般来说，你可能也想要这些结果/这将是很难过滤他们都在一般。

来源

2013-01-21 14:53:11

我开始了和去叶，因为我在这个问题试图根除，而不是根叶选择了相反的方法：

(defun tree->paths2 (tree) 
    (labels ((recurse (follow-ups) 
     (if follow-ups 
     (append (tree->paths2 (car follow-ups)) 
      (recurse (cdr follow-ups))) 
     nil))) 
    (rstyu:aif (cdr tree) 
      (mapcar #'(lambda(arg) 
       (cons (car tree) arg)) 
       (recurse it)) 
      (list tree)))) 

(tree->paths2 '(A . ((C . ((D . nil) (E . nil))) 
        (B . ((F . nil) (G . nil)))))) 
=> 
((A C D) (A C E) (A B F) (A B G))

但如果有一种方法可以解决我的第一个方法，我想宁愿接受这样的解决方案作为答案。

来源

2013-01-20 18:55:54 Sim

您必须删除list在(append (list (tree->paths

的tree->paths回报的路径列表; recurse也是如此。所以，他们可能被追加，而不包装在list呼叫。

来源

2013-01-20 20:09:55

如何形成树成单独的路径通向每个叶

回答

相关问题