在Scheme中插入二叉树

我想知道如何将列表中的元素插入二叉搜索树。我想知道为什么下面的代码不能按我的预期工作。输出是'((4 1 5 13 6) () ())我的下一个问题是对列表中的元素进行排序，但现在我只想插入它们。

我的输出对于我所说的问题是否正确？我的代码如下：

( define ( make-tree value left right ) 
( list value left right ))
( define ( value tree ) ( car tree ))
( define ( left tree ) ( cadr tree ))
( define ( right tree ) ( caddr tree ))

(define (insert-list L T)
 (cond ((null? T) (make-tree L '() '()))
    ((= (car L) (value T)) T)
    ((< (car L) (value T)) (make-tree (value T)
                                      (insert-list (car L) (left T))
                                      (right T)))
    ((> (car L) (value T)) (make-tree (value T)
                                      (left T)
                                      (insert-list (car L) (right T))))))

这段代码的问题

在编写递归代码时，通常最好考虑函数应该采用什么作为参数，应该返回什么，以及基本情况是什么。

(define (insert-list L T)
 (cond
    ((null? T) (make-tree L '() '()))                                     ; case 1
    ((= (car L) (value T)) T)                                             ; case 2
    ((< (car L) (value T)) (make-tree (value T)                           ; case 3
                                      (insert-list (car L) (left T))
                                      (right T)))
    ((> (car L) (value T)) (make-tree (value T)                           ; case 4
                                      (left T)
                                      (insert-list (car L) (right T))))))

根据你的描述，insert-list应该获取一个元素列表和一棵树，并返回通过将这些元素一个接一个地插入到树中而获得的树。这段代码真的能做到这一点吗？有以下几种情况：

1. 当树为空时，您确实需要创建一个包含某些元素的新树，但您的第一个情况创建一个包含以下元素的树：wholelist 作为其元素，并返回 this。这就是为什么你会得到这样的结果((4 1 5 13 6) () ())。你到达了这个基本情况并返回了结果(make-tree L '() '())).
2. 当。。。的时候first列表的元素是树的值，那么您返回树是正确的，因为您不需要执行任何其他操作来插入该树first列表的元素。但随后您无需对其余元素执行任何其他操作。这没有任何好处。如果你有一个像这样的测试用例(insert-list '(2 3 4) '(2 () ()))，你会看到返回值是(2 () ()).
3. （和 4.）在这些情况下，您可以进行递归调用，例如(insert-list (car L) (left T))，但这没有意义，因为第一个参数insert-list应该是一个元素列表，你用它来调用它(car L)这是一个单一的元素。不过，你认识到这一点是对的(car L)需要插入到树的左子树中，并且只要您调用，您就可以正确构建它(insert-element (car L) (left T))， 反而。但是，您仍然没有对rest之后的元素。

折叠来救援！

如果您尝试获取数字列表并插入first将一个数字放入一棵树中以获得一棵新树，然后将第二个数字插入该树中，依此类推，您正在寻找类似以下伪代码的内容：

tree = initial-tree
for element in list 
  tree = insert(element,tree)
return tree

这种操作通常用功能表示fold。我在回答中详细描述了折叠展平列表列表 https://stackoverflow.com/q/19229444/1281433，并且有很多关于它们的信息。这个想法是你想把类似的东西变成

(insert-list '(4 1 5 13 6) '())

into

(tree-insert (tree-insert (tree-insert (tree-insert (tree-insert '() 4) 1) 5) 13) 6)

那是一个左结合折叠。让我们使用这个定义foldl:

(define (foldl fn init list)
  (if (null? list)
      init
      (foldl fn (fn init (car list)) (cdr list))))

在这种特殊情况下，您需要实施正常的tree-insert接受一棵树和一个元素 a 的函数返回一棵新树，然后是要插入的函数all列表中的元素很简单

(lambda (tree elements)
  (foldl tree-insert tree elements))

例如，

> (foldl tree-insert '() '(3 5 8 1 9))
(3 (1 () ()) (5 () (8 () (9 () ()))))
> (foldl tree-insert '() '(5 8 2 3 1 6 9))
(5 (2 (1 () ()) (3 () ())) (8 (6 () ()) (9 () ())))
> (foldl tree-insert '() '(4 1 5 13 6))             ; the test from the question
(4 (1 () ()) (5 () (13 (6 () ()) ())))