list - 如何编写一个检查项目是否在树中的函数？

Question

我必须编写一个函数来检查一个项目是否在树中。

例如：

(defun find-in-tree (item tree)
  ...)

(find-in-tree 2 '(1 (3 4 (2))) 2) ;; should give T
(find-in-tree 2 '(1 (3 4))) ;; should give NIL

Answer 1

引用Lisp：

最后，考虑rfind-if一个递归版本，find-if它适用于树以及平面列表：

(defun rfind-if (fn tree)
  (if (atom tree)
      (and (funcall fn tree) tree)
      (or (rfind-if fn (car tree))
          (if (cdr tree) (rfind-if fn (cdr tree))))))

几个例子：

CL-USER> (find-if #'(lambda (x) (eq x 2)) '(1 (3 4 (2)))) ;; FIND-IF is the standard function
NIL
CL-USER> (rfind-if #'(lambda (x) (eq x 2)) '(1 (3 4 (2))))
2
CL-USER> (rfind-if #'(lambda (x) (eq x 2)) '((1 (2) 3) (3 4)))
2
CL-USER> (rfind-if #'(lambda (x) (eq x 2)) '((1 3) (3 4)))
NIL
CL-USER> (rfind-if (fint #'numberp #'oddp) '(2 (3 4) 5))
3

现在，递归版本find：

(defun find/tree (item tree &optional (test #'eq))
  (rfind-if #'(lambda (el) (funcall test el item)) tree))

用法：

CL-USER> (find 2 '((1 (2) 3) (3 4))) ;; FIND is the standard function, again
NIL
CL-USER> (find/tree 2 '((1 (2) 3) (3 4)))
2
CL-USER> (find/tree "2" '((1 ("2") 3) (3 4)))
NIL
CL-USER> (find/tree "2" '((1 ("2") 3) (3 4)) #'equal)
"2"

您可以在SICP、On Lisp和PAIP中找到有关列表、树、递归函数和递归搜索的更多信息。

---

还有一个问题是这些函数是否是尾递归的。这些问题也在列出的书籍中进行了讨论。