Scheme 中的二叉搜索树

Question

我有一个方案函数，其中有一个列表，我试图将数字一个一个地放入二叉搜索树中。但是，我不断收到 "unspecified return value"

(define (insertB L)
   (if (not (null? L))
   (begin (let() BST (insert (car L) BST))
   (insertB (cdr L))
   )
   )
)

我知道我的插入功能适用于单个数字。但我需要让 insertB 为列表工作。

Answer 1

你能像这样概括 BST 参数吗？

(define (insertB L BST)
  (if (not (null? L))
    (insertB (cdr L) (insert (car L) BST))
    BST
  )
)

或等价物：

(define (insertB L BST)
  (if (null? L)
    BST
    (insertB (cdr L) (insert (car L) BST))
  )
)

我觉得比较容易理解。也比较通用。

Answer 2

试试这个：

(define (insertB BST L)
  (if (null? L)
      BST
      (insertB (insert (car L) BST)
               (cdr L))))

最好将 BST 作为参数传递，而不是使用全局定义。除此之外，您必须确保在我们完成遍历列表（基本情况）时返回修改后的树。还要注意在每次递归调用中我们如何 insert 树中的当前元素并将其传递，同时我们转到列表中的下一个元素。如果允许高阶过程，我们可以写一个更简单的等效解决方案：

(define (insertB BST L)
  (foldr insert BST L))

Binary Search tree in Scheme