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

Question

Write a Lisp program to check whether a binary tree is a Binary Search Tree.

The left sub-tree of a node has a key less than or equal to its parent node's key. The right sub-tree of a node has a key greater than to its parent node's key.

列表可以用来表示二叉树的结构如下:'(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))

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

• 左子树必须是二叉搜索树
• 右子树必须是二叉搜索树
• 左子树的最大键(如果存在)必须小于根键
• 右子树的最小键(如果存在)必须大于根键

Note: the naming convention in Lisp is to write everything in lower case, with word parts separated by dashes. A predicate, i. e. a function that is used to obtain a truth value, ends with p. The predicate for a binary search tree might be named bst-p or binary-search-tree-p. The function to obtain the largest key of a bst might be called bst-largest-key.

为了得到BST的最大(最小)键，只需要在右(左)子树上递归即可。