tree - 搜索一棵树，如果一个节点出现不止一次，则返回 true

Question

我有一个家庭作业，我需要做以下事情:

Function which takes a tree as its argument and returns a nil/non-nil value indicating whether the tree contains only unique nodes (ie: there are no duplicated nodes in the tree).

到目前为止，我已经编写了以下代码。我是一个 lisp 新手，我需要完成我的作业。 这是我尝试实现的第一个解决方案。但是当我编译它时，它给了我以下错误:函数位置必须包含符号或 lambda 表达式:(第一棵树)。

  (defun in (tree)
    (cond ((null tree)
           t)
          ((eq (first tree) (second tree))
           nil)
          ((listp (first tree))
           (or ((first tree) in  (second tree))
               ((first tree) in  (rest tree))))
          (t
           ((first tree) in (rest tree)))))

这是我的第二次尝试，也没有用:

(defun flatten (structure)
  (cond ((null structure) nil)
        ((atom structure) `(,structure))
        (t (mapcan #'flatten structure))))

(defun uniNodes (inList &optional (out t) (test 0))
  (cond ((null inList)
         out)
        ((zerop test)
         (uniNodes (flatten(cons (first inList) (rest inList))) out (+ test 1)))
        ((eq t (first out))
         (uniNodes (rest inList) (compare1 (first inList) (rest inList) (first out)) test))
        ((eq nil (first out))
         out)))

(defun compare1 (a list &optional (out t))
  (cond ((null list)
         out)
        ((equal a (first list))
         nil)
        (t
         (compare1 a (rest list) (first out)))))

你能给我一些见解吗？

Answer 1

我建议你递归遍历树，将节点收集在一个表中。

(defun find-dupes (tree)
  (let ((table (make-hash-table)))
    (labels ((check-node (node)
               (when (consp node)
                 (when (gethash node table)
                   (return-from find-dupes node)) ; return the dupe
                 (setf (gethash node table) node) ; memorize the node
                 (check-node (car node))
                 (check-node (cdr node)))))
      (check-node tree))))

您需要弄清楚如何更改上述代码以解决您的问题。

至于你的错误，

Function position must contain a symbol or lambda expression: (FIRST TREE)

意味着你需要修复你的函数调用

(A in B)

与

(in A B)

你没有解释你第二次尝试有什么问题，尽管它似乎是参数大小的二次方。