1

我有一棵树：

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

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

4

3 回答 3

1

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

tree->paths返回路径列表；也是如此recurse。因此，它们可以在不包含在list调用中的情况下被附加。

于 2013-01-20T20:09:55.977 回答
0

正如我在问题中尝试的那样，我重新开始并选择了相反的方法，即从叶到根而不是从根到叶：

(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-20T18:55:54.587 回答
0

在这里，我尝试重写它以使其线性工作（因为您的原始函数会耗尽堆栈空间）。但是，在这样做的同时，我发现了一些东西，您通常会认为这是您最初的想法：

(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-21T14:53:11.070 回答