Lisp程序来检查二进制树是否是二进制搜索树

Question

编写一个Lisp程序来检查二进制树是否是二进制搜索树。

节点的左侧子树的键小于或等于其父节点的键。节点的右侧子树的键大于其父节点的键。

列表可用于表示二叉树的结构，如下所示：'(8 (3 (1 () ()) (6 (4 () ())( 7 () ()))) (10 (()) (14 (13) ())))，其中这将返回true。

我正在尝试编写一种二进制递归方法，但我是一个初学者，不知道从这里开始该怎么做。

(defun isBST (L)
(cond 
((null (first L)) t)
((and (not (null (caadr L)) ) (< (first L) (caadr L)) )  nil)
((and (not (null (caaddr L))) (> (car L) (caaddr L)))  nil)
((and (not (isBST (cadr L))) (not (isBST (caddr L)))) ))
)

Answer 1

您可以用代码表达您的定义，使您的生活更轻松。

一个节点表示为三个元素的列表：一个键、一个左子树和一个右子树。

(defun node-key (node)
(first node))
(defun node-left-subtree (node)
(second node))
(defun node-right-subtree (node)
(third node))

要使树成为二进制搜索树，必须满足四个条件，除非两个子树都为空：

• 左子树必须是二进制搜索树
• 右侧子树必须是二进制搜索树
• 左子树的最大关键字(如果存在(必须小于根关键字
• 右子树的最小键(如果存在(必须大于根键

注意：Lisp中的命名约定是用小写写所有内容，用破折号分隔单词部分。谓词，即用于获取真值的函数，以p结尾。二进制搜索树的谓词可以命名为bst-p或binary-search-tree-p。获取bst最大密钥的函数可以称为bst-largest-key。

为了获得BST的最大(最小(键，您只需要在右(左(子树上递归。

Answer 2

下面是一个可能对您有所帮助的scheme过程。

(define (is-bst l)
(define (loop node proc)
(if (null? node)
#t
(and (proc (car node))
(loop (cadr node)
(curry > (car node)))
(loop (caddr node)
(curry < (car node))))))
(loop l (const #t)))

当您的输入数据是错误的来源时，修复程序可能会令人沮丧。我不得不修理你的(())和(13)。使用多条线和自动压头可以很容易地发现错误。

(is-bst '(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(14 (13 () ())
()))))
;; #t

使其中一个节点无效，以确保is-bst检测到非bst。

(is-bst '(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(2 (13 () ()) ;; 14 changed to 2; invalid tree
()))))
;; #f

为了稍微改进一下，请注意，我们在上面的过程中调用了(car node)三次。应通过使用let来避免这种情况。

(define (is-bst l)
(define (loop node proc)
(if (null? node)
#t
(let ((value (car node)))
(and (proc value)
(loop (cadr node)
(curry > value))
(loop (caddr node)
(curry < value))))))
(loop l (const #t)))

---

另一种有趣的方法是使用流，它可以使用基本过程轻松实现。我们可以编写一个通用的traverse过程来遍历我们的树。

(define (traverse bst)
(if (null? bst)
empty-stream
(stream-append (traverse (cadr bst))
(stream (car bst))
(traverse (caddr bst)))))
(define tree
'(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(14 (13 () ())
()))))
(stream->list (traverse tree))
;; '(1 3 4 6 7 8 10 13 14)

现在我们编写is-bst来简单地检查这些值是否以升序出现。

(define (is-bst l)
(define (loop x s)
(if (stream-empty? s)
#t
(let ((y (stream-first s)))
(and (< x y)
(loop y (stream-rest s))))))
(loop -inf.0
(traverse l)))

(is-bst tree)
; #t
(is-bst '(1 (2 () ())
(3 () ())))
; #f

因为使用了流，所以值会懒散地出现。如果发现早期的#f，则停止流的迭代并完成计算。