帮助编写二叉树的 Lisp 代码

Question

我有

(setq l2 '(1 (2 b (c 1 b))(a (1 2) d))) 

(defun drumuri (l3) 
  (cond ((atom l3) (cons l3 nil))
     (t (append
           (cons (car l3) nil)
           (drumuri (cadr l3))
           (cons (car l3) nil)
           (drumuri (caddr l3))))))

(drumuri l2)

，它给了我：

 Break 2 
[4]>     DRUMURI
 Break 2 
[4]>     (1 2 B 2 C 1 C B 1 A 1 2 1 NIL A D)

但我需要：

((1 2 B)(1 2 C 1)(1 2 C B)(1 A 1 2)(1 A D)) 

好的好消息，我找到了一些答案：

(setq l2 '(1 (2 b (c 1 b))(a (1 2) d)))
( defun drumuri (l3) 
( cond ( (atom l3) ( cons l3 nil))
       (t (append  ( cons ( car l3 ) nil)
          (drumuri ( cadr l3) )))))
          (drumuri l2)

答案是：

[1]> 
(1 (2 B (C 1 B)) (A (1 2) D))
[2]> 
DRUMURI
[3]> 
(1 2 B)

接下来是第二个答案：

(defun drumuri (l4) 
    (cond ((atom l4)(cons l4 nil))
    ( t   ( append  (cons ( car l4)nil)
        (drumuri ( caddr l4))))))
            (drumuri l2)

答案是：

[1]> 
(1 (2 B (C 1 B)) (A (1 2) D))
[2]> 
DRUMURI
[3]> 
(1 A D)

所以剩下的就是找到：

(1 2 C 1) (1 2 CB) (1 A 1 2)

Answer 1

一个棘手的问题。不是特别复杂，但有一些挑剔的边缘。由于这显然是家庭作业，因此我将尽力帮助您，但同时避免只是用勺子喂您（并且可能无法实现其中一个或两个目标）。所以我用 Python 编写了它。希望这与 Lisp 相差足够远，您仍然需要自己进行大量思考。

>>> import operator
>>> def drumuri(a):
...     if isinstance(a, list):
...         return reduce(operator.add,
...                       [[a[:1] + d for d in drumuri(x)] for x in a[1:]])
...     else:
...         return [[a]]
... 
>>> drumuri( [1, [2, 'b', ['c', 1, 'b']], ['a', [1, 2], 'd']] )
[[1, 2, 'b'], [1, 2, 'c', 1], [1, 2, 'c', 'b'], [1, 'a', 1, 2], [1, 'a', 'd']]
>>> 

这是您的 Lisp 版本中缺少的关键见解。因为rumuri是递归的，所以每个级别都必须向其调用者返回相同类型的结构：路径列表，其中每个路径都是一个列表。简而言之，drumuri 必须始终返回一个列表列表。您的叶案例返回一个包含单个原子的列表。

您在使用 append 时也会犯一些错误，但叶子问题可能会使其他所有内容都变形。

编辑：让我们看看是否可以帮助您自己找到解决方案。请按照以下步骤操作：

1. 编写一个名为 prepend-to-paths 的函数，该函数采用单个头和路径列表，并返回一个路径列表，其中头添加到每个原始路径的前面小路。它应该按如下方式工作：

   <前><代码>> (路径前缀 1 '((2 B) (2 C 1) (2 CB) (A 1 2) (AD))) ;'
   ((1 2 B) (1 2 C 1) (1 2 CB) (1 A 1 2) (1 AD))

2. 编写一个名为 convert-to-paths 的函数，该函数获取未处理的尾部元素列表并将它们转换为路径。然而，它不应该自己完成所有工作，而应该只关心将输入映射到路径列表（依靠尚未编写的 drumuri 来映射每个元素），然后连接返回的列表路径到单个路径列表中。输出（一旦 drumuri 存在）应该如下所示：

   <前><代码>> （转换为路径 '((2 b (c 1 b)) (a (1 2) d))) ;'
   ((2 B) (2 C 1) (2 CB) (A 1 2) (AD))

3. 编写 drumuri 函数。它应该按照原始版本使用 cond ，但将叶大小写替换为将原子作为路径列表返回的表达式：

   <前><代码>> (drumuri 'b) ;'
   ((b))

   然后将 (append ...) 替换为使用您在前面步骤中编写的函数来转换输入列表输入路径列表的头部和尾部的代码。

4. 一旦这三个函数很好地协同工作，您就可以尝试弄清楚如何将前两个函数折叠到 drumuri 的主体中。请注意，最终结果可能在结构上与我给出的 Python 解决方案不同。

如果您遇到困难，只需用您取得的任何进展以及您设法拼凑在一起的任何代码来更新您的问题即可。