2

编写一个名为 insert-list 的过程，它接受一个数字列表 L 和一个树 T，并返回通过将 L 中的所有数字插入到 T 中得到的树。

这是我的代码：

(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? L) T)
        ((null? T) (insert-list (cdr L) (make-tree (car L) '() '())))
        ((= (car L) (value T)) (insert-list (cdr L) T))
        ((< (car L) (value T)) (insert-list (cdr L) (make-tree (value T)(insert-list L (left T)) (right T))))
        ((> (car L) (value T)) (insert-list (cdr L) (make-tree (value T) (left T)  (insert-list L (right T)))))))

我不断收到错误：

car: contract violation
  expected: pair?
  given: 4

为什么我不断收到此错误？

4

1 回答 1

3

我认为您的代码是正确的，问题是测试用例。

Make tree 需要一个值和两个（可能为空的）列表。

(insert-list '(3 4 5) '())

给

(3 () (4 () (5 () ())))

我认为这是您想要的测试用例。

该错误是因为程序期望在树的第二和第三位置有一个列表，并尝试分解 4，从而导致您看到的错误。具体错误是在小于分支调用(right t)on时引起的'(3 4 5)，并将结果传递给4插入列表：

(insert-list (list 1 2 3 4) 4)

equals 子句是在调用 时引发错误的子句(value 4)，它会让您看到您所看到的错误：

> (car 4)
. . car: contract violation
  expected: pair?
  given: 4

如果它可以帮助您更好地理解，这些是我查看的测试用例得出的代码是正确的结论：

(require test-engine/racket-tests)
; Check tree generation
(check-expect (make-tree '() '() '()) '('() '() '()))
(check-expect (make-tree 3 '() '()) (list 3 '() '()))

; Null list case
(check-expect (insert-list '() '(1 '() '())) '(1 '() '()))
; Null tree case
(check-expect (insert-list (list 1) '()) '(1 '() '()))
; left case
(check-expect (insert-list '(2) (make-tree 3 '() '())) '(3 '(2) '())) 
; right case
(check-expect (insert-list '(4) (make-tree 3 '() '())) '(3 '() '(4)))
; nested left case
(check-expect (insert-list '(2 1) '(3 '() '())) '(3 '(2 '(1) ()) ()))
; nested right case
(check-expect (insert-list '(4 5) '(3 '() '())) '(4 '() '(5 '() '())))

(check-expect (insert-list (list 3 1 2 3 4 5) (make-tree 1 '() '())) 
    (1 () (3 (1 () (2 () (3 () (4 () (5 () ()))))) (4 () (5 () ())))))
于 2013-10-19T22:28:36.010 回答