0

我正在尝试在球拍中实现 bst（二叉搜索树）。bst 是一个递归列表（列表 x leftChild rightChild），其中 leftChild 和 rightChild 本身就是列表 我写了以下代码

(define (insert bst x)(
     (cond 
       [(null? bst) (append bst (list x '() '()))]
       [(<= x (car bst)) (insert (cadr bst) x)]
       [else (insert (caddr bst) x)]  
     )))

当我写

(insert (insert null 8) 9)

它给出了一个错误：函数调用：期望在左括号后有一个函数，但收到了（列表 8 为空） 有人可以解释一下吗？

4

1 回答 1

1

报告的错误是因为表达式()周围有一对错误的cond，这使得 Scheme 在没有过程时尝试执行过程。但是除此之外还有几个逻辑问题，当插入一个元素时，您实际上并没有构建一个列表，并且缺少一个案例 - 如果该元素已经存在于树中会发生什么？这应该有效：

(define (insert bst x)
  (cond 
    [(null? bst)
     (list x '() '())] ; this is the correct way to handle the base case
    [(= x (car bst))   ; this case was missing
     bst]              ; simply leave the tree as it is
    [(< x (car bst))   ; if this happens, recursively build a list
     (list (car bst) (insert (cadr bst) x) (caddr bst))] 
    [else              ; if this happens, recursively build a list
     (list (car bst) (cadr bst) (insert (caddr bst) x))]))

这是您使用该过程的方式：

(insert (insert (insert (insert null
                                10)
                        5)
                16)
        13)

=> '(10 (5 () ()) (16 (13 () ()) ()))
于 2013-11-08T15:23:25.283 回答