tree - 如何获取n叉树中节点的路径？

Question

我在 gnu lisp 中工作，想要获取到某个节点的路径。 我已经设法解决了二叉树的问题，但如果树是 n 叉树，则找不到正确的递归规则。树表示为(根(子树 1)(子树 2)...)。 那么，如何使用 GNU Lisp 获取 n 叉树中节点的路径？

二进制代码:

;checks if element e is in l
(defun partof(l e)
    (cond
        ((null l) nil)
        ((equal l e) T)
        ((atom l) nil)
        (T (find T (mapcar (lambda (l) (partof l e)) l)))))

;get the path   
(defun path(l e)
    (cond
        ((null l) nil)
        ((equal (car l) e) (list (car l))) ;if the element is the root of subtree return it
        ((partof (cadr l) e) (cons (car l) (path (cadr l) e))) ;if it is in the first subtree, get the root and check in first subtree until you get to it
        ((partof (caddr l) e) (cons (car l) (path(caddr l) e))) ; get the root and parse the second subtree
        (T nil))) ;here i can't find the rule to check in the rest of the subtrees

我也对一种全新的方式感兴趣，而不仅仅是完成这个。 一棵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

Answer 1

从根到节点的路径(递归方法)

(defun find-path (tree node &optional path)
  (if (eq (car tree) node)
      (reverse (cons node path))
      (reduce (lambda (p x)
                (or p (find-path x
                                 node
                                 (cons (car tree) path))))
              (cdr tree)
              :initial-value nil)))

适用于 GNU CLISP 2.49:

CL-USER> (defparameter *tree* '(a (b (c) (d)) (e (f) (g)) (h (i) (j))))
*TREE*
CL-USER> (find-path *tree* 'd)
(A B D)

从一个任意节点到另一个节点的路径

OP 没有说他/她想要得到什么样的路径:从根到节点，或者两个任意节点之间。所以这个函数解决了更一般的任务，即在树的任意两个节点之间寻找路径。

(defun find-path* (tree x y)
  (labels ((till-d (a b i)
             (if (and (eq (car a) (car b))
                      a
                      b)
                 (till-d (cdr a) (cdr b) (1+ i))
                 i)))
    (let* ((x-path (find-path tree x))
           (y-path (find-path tree y))
           (pos (till-d x-path y-path 0)))
      (append (reverse (nthcdr (1- pos) x-path))
              (nthcdr pos y-path)))))

像这样工作:

CL-USER> (find-path* *tree* 'd 'c)
(D B C)
CL-USER> (find-path* *tree* 'd 'g)
(D B A E G)
CL-USER> (find-path* *tree* 'b 'h)
(B A H)
CL-USER> (find-path* *tree* 'd 'd)
(D)

现在许多任务也可以很容易地解决(节点之间的距离等)。