从根到给定节点的路径 n-ary 树 lisp 没有 map/lambda/labels

Question

我知道之前有人问过这个问题，但只有 map/lambda/labels 才能解决，我希望它尽可能基本地解决

我想要 return 从根到树的给定节点的路径，如下所示：

  A
 / \
B   C
   / \
  D   E

给出为：(A 2 B 0 C 2 D 0 E 0) 从 A（根）到给定节点 E 的路径是：A C E

我不知道如何在找到元素的确切位置之前保留路径。我应该保存部分结果吗？有什么帮助吗？

我尝试检查元素是否在其中，但是...我就是无法构建路径

(defun isinh (l a p)
  (cond ((null l) p)
        ((equal (car l) a) (isinh (cdr l) a 1))
        (t (isinh (cdr l) a p))))

(defun isin (l a)
  (cond (t (isinh l a 0))))

(defun p15 (l el)
  (cond ((null l) '())
        ((equal (car l) el) (list el))
        ((and (listp (car l))
              (= (isin (car l) el)))
         (p15 (car l) el))
        ((and (listp (cadr l))
              (= (isin (cadr l) el)))
         (p15 (cadr l) el))
        ((not (equal (car l) el))
         (cons (car l) (p15 (cdr l) el)))))

Answer 1

一种可能的解决方法是将树转化为列表结构，第一个元素为根，第二个元素为左子，第三个元素为右子，然后通过简单的搜索路径递归函数。

要以列表结构转换树，请参阅此问题的答案：。

查找路径的递归函数如下：

(defun path(tree el)
  (cond ((null tree) nil)
        ((eql (first tree) el) (list el))
        (t (let ((lpath (path (second tree) el)))
             (if lpath
               (cons (first tree) lpath)
               (let ((rpath (path (third tree) el)))
                 (when rpath
                   (cons (first tree) rpath))))))))

更新

以前的版本只适用于二叉树，n-ary 树的版本如下：

(defun path(tree el)
  (cond ((null tree) nil)
        ((eql (car tree) el) (list el))
        (t (loop for child in (rest tree)
              for child-path = (path child el)
              when child-path
              do (return-from path (cons (car tree) child-path))))))

(path '(a (b (c)) (d (e) (f)) (g (h) (i (j)))) 'j)  ;  =>  (A G I J)

从根到给定节点的路径 n-ary 树 lisp 没有 map/lambda/labels

Path from root to a given node n-ary tree lisp without map/lambda/labels

lisp

tree

common-lisp