检查二叉树是否为二叉搜索树的Lisp程序

Question

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

我正在尝试编写一个二进制递归方法，但我是一个初学者，我不知道从这里去哪里。

(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))

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

null

注意：Lisp中的命名惯例是所有的东西都用小写，单词部分用破折号隔开。谓词，i。e.用于获得真值的函数，以p结尾。二进制搜索树的谓词可以命名为bst-p或binary-search-tree-p。获取bst的最大键的函数可以称为bst-maxing-key。

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