我必须创建一个能够检查二进制搜索树是否实际上是BST.的lisp程序
这就是我所做的：
(defun BST (lst)
(if (null lst) nil
(let ((curr (car lst)) (left (car (cdr lst))) (right (cdr (cdr lst))))
(cond
((and (null left) (null right)) t)
((and (numberp (car left)) (> (car left) curr)) nil)
((and (numberp (car right)) (<= (car right) curr)) nil)
((null right) (BST left))
((null left) (BST right))
(t (and (BST right) (BST left)))))))
(print (BST '(8 (3 (1 () ()) (6 (4 () ())(7 () ()))) (10 () (14 (13) ())))))
结果是t，但是如果我将10编辑为低于8的值，结果仍然是真的。事实上，我的函数似乎完全忽略了树的右侧，只对8->3->1路径的变化做出反应。任何帮助都将不胜感激，谢谢。
您的问题在于抽象。没有。
从let的破坏来看，我猜一个节点是这样做的：
(defun node (value &optional left right)
(list* value left right))
(node 1 (node 2) (node 4))
; ==> (1 (2 nil) 4 nil)
然而，你经过的树似乎是用这个制作的：
(defun node (value &optional left right)
(list value left right))
(node 1 (node 2) (node 4))
; ==> (1 (2 nil nil) (4 nil nil))
如何对二叉树建模其实并不重要。重要的是，所有代码都使用相同的模型，而不是不同的模型。这可以通过创建构造函数和getter来实现。
首先，总是在consy结构上定义抽象，除非您明确谈论的是consy结构这真的很重要。
在BST的情况下，您希望函数生成一个节点，然后生成一些访问器。访问者可以是完全通用的。
(defgeneric make-bst-node-for-node (node value left right)
;; Make a node to serve as a child of NODE
)
(defgeneric bst-node-value (node))
(defmethod bst-node-value ((node cons))
(car node))
(defgeneric bst-node-left (node))
(defgeneric (setf bst-node-left) (new node))
(defgeneric bst-node-right (node))
(defgeneric (setf bst-node-right) (new node))
(defgeneric plausible-bst-node-p (maybe-node)
;; Is MAYBE-NODE basically plausible?
(:method (maybe-node)
(declare (ignorable maybe-node))
nil))
(defgeneric bst-node-components (node)
;; Return the components of a node as multiple values
(:method (node)
(values (bst-node-value node)
(bst-node-left node)
(bst-node-right node))))
;;; Consy BST nodes
;;;
(defun make-consy-bst-node (value left right)
;; A consy BST looks like (val . (left . right)), where left & right
;; are either BSTs or null.
`(,value . (,left . ,right)))
(defmethod make-bst-node-for-node ((node cons) value left right)
(make-consy-bst-node value left right))
(defmethod bst-node-left ((node cons))
(car (cdr node)))
(defmethod (setf bst-node-left) (new (node cons))
(setf (car (cdr node)) new))
(defmethod bst-node-right ((node cons))
(cdr (cdr node)))
(defmethod (setf bst-node-right) (new (node cons))
(setf (cdr (cdr node)) new))
(defmethod plausible-bst-node-p ((maybe-node cons))
(consp (cdr maybe-node)))
(defmethod bst-node-components ((node cons))
;; Efficiency hack (probably not worth it)
(let ((lr (cdr node)))
(values (car node) (car lr) (cdr lr))))
请注意，没有办法更改节点的值，因为我认为您永远不需要这样做。
有了这样的抽象，任何真正行走于BST的东西都可以用它们来完成，而不是像我们都必须经历的所有令人震惊的20世纪60年代Lisp代码那样，它完全由(CAR (CDDR (CAR (CDAADR ...))))组成，其中大部分是在过去20年中编写的。
此外，构建BST的大多数代码不需要知道它们的重新表示：一旦你创建了一个根节点，你就可以使用make-bst-node-for-node为它创建子节点。
我认为，正是因为你没有定义抽象，因此也没有理清结构的真正含义，所以你遇到了麻烦：你的代码隐式地使用了一个与上面类似的表示，但你给它提供的树隐式地采用了一个(value left right)的结构：一个不同的表示。
为了让生活更轻松，我将定义两个函数，它们采用(value left right)表示法，可读性更强，但效率稍低，并将其转换为(value . (left . right))表示法(请注意，这不使用make-bst-node-for-node，因为它早于它，而且我很懒)：
(defun make-consy-bst (value lb rb)
;; LB and RB are either null or are recursively processed
(make-consy-bst-node value
(if lb
(make-consy-bst (first lb) (second lb) (third lb))
nil)
(if rb
(make-consy-bst (first rb) (second rb) (third rb))
nil)))
(defun make-consy-bst* (thing)
(apply #'make-consy-bst thing))
现在你想要的是一个函数，给定一个声称是BST的东西，它会检查它是不是。注意，这个函数本身使用了上面的抽象：这里没有明确的car/cdr追逐。这意味着它将适用于任何类型的BST。还要注意的是，这个函数的实现有点狡猾：它使用了递归函数的一个略显肮脏的技巧，如果它发现了不好的东西，就会直接从其父函数返回。
最后还要注意，这个函数对值是什么是不可知的：你可以给它一个谓词，这个谓词告诉你值是否合法，还有一个排序谓词。
(defun bst-p (maybe-bst &key
(value-predicate #'realp)
(comparison-predicate #'<))
;; Return two values: either T and the BST, or NIL and the first
;; object which failed to be a BST.
(labels ((maybe-bst-value (thing)
;; Return the value of THING if it is a good BST.
;; If it's not give up at once
(unless (plausible-bst-node-p thing)
;; It not even slightly plausible
(return-from bst-p (values nil thing)))
(multiple-value-bind (value left right)
(bst-node-components thing)
(unless (funcall value-predicate value)
;; Value is not legal
(return-from bst-p (values nil thing)))
;; check the ordering if the children are not null,
;; giving up promptly if they are not
(when (not (null left))
(unless (funcall comparison-predicate
(maybe-bst-value left)
value)
(return-from bst-p (values nil thing))))
(when (not (null right))
(unless (funcall comparison-predicate
value
(maybe-bst-value right))
(return-from bst-p (values nil thing))))
value)))
;; It is slightly odd that the value is not used, but there is
;; nothing that says the value is not NIL
(maybe-bst-value maybe-bst)
(values t maybe-bst)))
我们可以试试这个：
> (bst-p (make-consy-bst* '(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(14 (13 () ())
())))))
t
(8 (3 (1 nil) 6 (4 nil) 7 nil) 10 nil 14 (13 nil))
> (bst-p (make-consy-bst* '(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(14 (13 () ())
(12 () ()))))))
nil
(14 (13 nil) 12 nil)
在第二种情况下，您可以看到它失败了，因为14节点的两个子节点没有排序。
注意这段代码根本没有经过测试——我只是输入了大部分内容：可能有错误。
还要注意的是，在这个的第一个版本中，我实际上实现了一个与我所谈论的不同的表示。
我认为问题出在(let ((right (cdr (cdr lst)) ...)上。与car不同，正确列表的cdr保证返回列表。它返回cons的第二个单元格，而不是列表的第二项。要只使用car和cdr，您需要将其更改为(let ((right (car (cdr (cdr lst))))) ...)(用纯文本框编写，不确定括号是否匹配)。最好使用first、second和third，重写如下：CCD_ 18。
我确实认为有更好的方法来编写关于BST的代码，通过生成更合理的实用函数。
请研究此代码：
(defun binary-search-tree-p (tree)
(if (null tree)
t
(destructuring-bind (value &optional left right) tree
(let ((left-val (car left))
(right-val (car right)))
(and (binary-search-tree-p left)
(binary-search-tree-p right)
(numberp value)
(or (null left)
(<= left-val value))
(or (null right)
(< value right-val)))))))
命名：函数的名称很清楚，使用
-p约定来表明它是一个谓词：一个参数布尔值来测试一些真理。参数是tree，而不是list。顺便说一句，在Common Lisp中，list是一个有效的变量名，它不影响list函数。null大小写是
T而不是NIL。我们应该声明一个空的BST是有效的，而不是无效的。如果一个空的BST是无效的，那么如果我们希望一个节点BST(42 nil nil)是有效的，那么我们必须添加丑陋的任意规则，比如如果一个BST有空的子节点(它们本身是无效的！)，那么它本身就是有效的。CCD_ 27与CCD_。
我们首先验证了儿童是
binary-search-tree-p。下一个检查是(numberp value)。因此，如果一个树为null，它是有效的，但如果它不为null，那么它必须有一个数值。在解决了上面(4)中的一些重要问题后，我们不必再次使用
numberp。如果我们知道left是一个有效的BST，那么如果left不为null，那么(numberp left)必须为true，因为这是递归检查的！我们在剩下的两个测试中利用了这一点：(or (null left) (<= (car left) value)):"要么左边的树是空的，要么我们可以相信左边树的值是数字，而且这个数字不能超过这个节点的值">，右边也是如此。如果
left是nil，则(car left)是安全的；然而，重要的是要承认，由于访问(car "abc")，我们的代码将在像(42 "abc")这样的树节点上爆炸。如果要求它对这种情况具有鲁棒性，则需要一些额外的逻辑。我假设，由于您使用的是
<=，因此树中显然允许重复值。我进一步假设重复的值向左运行。也就是说，在二进制搜索中，当遇到最上面的重复值时，该值的剩余重复都在左子树中。这很容易调整，以便在需要时使副本朝另一个方向落下。然而，请注意，在任何一种选择下，我们的测试都是不必要的严格。也就是说，这实际上是一个有重复的有效二进制搜索树，它被拒绝了，因为(< 5 5)在右侧失败：5 5 5 4 5 7 6 8合适的条件应该是：
... (or (null left) (<= left-val value)) (or (null right) (<= value right-val))