如何形成樹成單獨的路徑通向每個葉

Question

我得到了一棵樹：

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

我必須在遞歸中缺少某種附加/合併，但我沒有看到它。

Answer 1

在這裏，我試圖重寫它，以便它線性工作（因爲你的原始函數會耗盡堆棧空間）。然而，在這樣做時，我發現的東西，你可能在通用再保你最初的想法考慮：

(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 - 從查看您的數據，這個結果似乎是多餘的，但一般來說，你可能也想要這些結果/這將是很難過濾他們都在一般。

Answer 2

我開始了和去葉，因爲我在這個問題試圖根除，而不是根葉選擇了相反的方法：

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

但如果有一種方法可以解決我的第一個方法，我想寧願接受這樣的解決方案作爲答案。

Answer 3

您必須刪除list在(append (list (tree->paths

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