search - 在k-d树中搜索项目

我正在用Lisp开发一棵k-d树我正在编写一个函数，允许我搜索k-d树中的节点此函数定义如下：

(defmethod find-node ((kdt kdtree) target &key (key #'value) (test #'equal))
  (unless (null (root kdt))
    (find-node (root kdt) target :key key :test test)))

(defmethod find-node ((node kdnode) target &key (key #'value) (test #'equal))
  (format t "Testing node ~a~%" (value node))
  (format t "Result is ~a~%" (funcall test (funcall key node) target))
  (if (funcall test (funcall key node) target)
      node
      (progn
        (unless (null (left node))
          (find-node (left node) target :key key :test test))
        (unless (null (right node))
          (find-node (right node) target :key key :test test)))))

我用以下数据建立一棵树：'((2 3) (5 4) (9 6) (4 7) (8 1) (7 2))现在，我使用这个函数来查找节点。

(find-node kdt '(2 3))

使用'(2 3)语句，我得到以下输出：

Testing node (7 2)
Result is NIL
Testing node (5 4)
Result is NIL
Testing node (2 3)
Result is T
Testing node (4 7)
Result is NIL
Testing node (9 6)
Result is NIL
Testing node (8 1)
Result is NIL
NIL

因此，正如您所看到的，由于测试的结果是format，因此找到了节点，但是，搜索仍在继续，结果是T为什么这个函数不返回节点？

最佳答案

你可能想直接返回一个结果，当你发现什么。
使用以下示例改进代码：

(defun find-it (item list)
  (labels ((find-it-aux (item list)
             (when list
               (if (eql item (first list))
                   (return-from find-it (first list))
                 (find-it-aux item (rest list))))))
    (find-it-aux item list)))

CL-USER 89 > (find-it 1 '(2 3 1 5))
1

CL-USER 90 > (find-it 1 '(2 3 5))
NIL

或

(defun find-it (item list)
  (catch 'found-it
    (find-it-aux item list)))

(defun find-it-aux (item list)
  (when list
    (if (eql item (first list))
        (throw 'found-it (first list))
      (find-it-aux item (rest list)))))


CL-USER 91 > (find-it 1 '(2 3 1 5))
1

CL-USER 92 > (find-it 1 '(2 3 5))
NIL