tree - 使用 MAP 函数从根到给定节点的 Lisp 路径

Question

我一直在想这个问题，但我自己想不通。给定一棵 n 元树和一个节点，在 lisp 中找到路径(我使用的是 common lisp，但它的任何版本都可以)到给定节点。n 元树是这样的: ( root (subtree1) (subtree2) (subtree3) ...)，例如 (A (B (C) (D)) (E (F) (G)) (H (I) ( J)))是这样表示的:

           A
       /   |   \
      B    E    H
     /\    /\   /\
    C D   F G  I  J

给定三个(A (B (C) (D)) (E (F) (G)) (H (I) (J)))和节点F ，结果应该是:(A E F)。

P.S.:我搜索了一个使用 map 函数的解决方案，但我只找到了没有 map 函数的递归解决方案。

Answer 1

这是一个使用 mapcan together 和递归的人为解决方案:

(defun path (tree leaf)
  (cond ((null tree) nil)
        ((eq (car tree) leaf) (list leaf))
        (t (mapcan (lambda (subtree)
                     (let ((p (path subtree leaf))) 
                       (when p (cons (car tree) p))))
                   (cdr tree)))))