2

我想知道如何将列表中的元素插入二叉搜索树。我想知道为什么下面的代码不能按我的预期工作。输出是'((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))))))
4

1 回答 1

2

这段代码的问题

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

(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. 当树为空时，您确实需要创建一个包含某个元素的新树，但您的第一个案例创建了一个将整个列表作为其元素的树，并返回它。这就是为什么你会得到这样的结果 ((4 1 5 13 6) () ())。你得到了这个基本情况并返回了(make-tree L '() '())).
  2. 当列表的第一个元素是树的值时，返回树是正确的，因为您不需要做任何其他事情来插入列表的第一个元素。但是你不会对其余元素做任何其他事情。那没有任何好处。如果你有一个类似的测试用例(insert-list '(2 3 4) '(2 () ()))，你会看到返回值是(2 () ()).
  3. （和 4.）在这些情况下，您可以像 一样进行递归调用(insert-list (car L) (left T))，但这没有意义，因为 to 的第一个参数insert-list应该是元素列表，而您调用它时使用(car L)的是单个元素。但是，您是对的，认识到(car L)需要将其插入到树的左子树中，并且您正在正确地构造它，只要您调用(insert-element (car L) (left T)), 即可。但是，之后您仍然没有对其余元素做任何事情。

折叠救援！

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

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

这种操作通常在功能上由 a 表示fold。我已经在对Flattening a List of Lists的回答中详细描述了折叠，并且那里有很多关于它们的信息。这个想法是你想把像

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

进入

(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 返回一棵新树，然后从列表中插入所有元素的函数很简单

(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 () ()) ())))
于 2013-10-15T21:12:33.933 回答