0

我正在编写代码来测试 Scheme 中两棵树是否相等（在数据和结构中），并且我必须假设每个节点最多只有两个子节点。我的代码如下：

(define (make-tree value left right) 
  (list value left right))
(define (value tree)
  (car tree))  
(define (left tree) 
  (car (cdr tree)))
(define (right tree)
  (car (cdr (cdr tree))))

(define (tree-equal? T1 T2)
 (if (and (null? T1) (null? T2)) 
   #t
   (if (= (value T1) (value T2))
      (tree-equal? (left T1) (left T2))
      (tree-equal? (right T1) (right T2)))))

(tree-equal? '(1 2 3) '(1 2 3))

我得到的输出是汽车：

 car: contract violation
 expected: pair?
 given: 2

谁能向我解释我做错了什么？为什么（值 T1）会给出这个错误？我应该重写我的值函数来检查树是否为空吗？

4

1 回答 1

4

导致错误的问题

在您的代码中有几个地方，您最终可能会car使用不是 a 的东西进行调用pair（因此违反了car参数应该是 a的合同pair）。如错误消息所示，其中一件事是2. 特别是，在检查完之后(= 1 1)（因为1是(1 2 3)and的值(1 3 2)），你递归到树的左分支

(tree-equal? (left T1) (left T2))

现在，(left T1)生产2和(left T2)生产3。两者都不是null，因此您最终会使用2 == T1and进入下一行3 == T2。

(= (value T1) (value T2))

由于value定义为car，因此您尝试使用car调用2。

其他一些问题……</h3>

解决之后，您的比较功能仍然存在一些问题，其中一些只是风格上的，而其中一些实际上会导致问题。

(define (tree-equal? T1 T2)                   
 (if (and (null? T1) (null? T2))              
   #t                                         
   (if (= (value T1) (value T2))              
      (tree-equal? (left T1) (left T2))       
      (tree-equal? (right T1) (right T2)))))

你是对的，如果两棵树都是null?，那么它们是相同的。但是，如果其中一个是null?而另一个不是，会发生什么？您将继续调用valueon ()，这是不好的。如果另一个不是null?，但也不是列表，您将尝试调用value它，这也会失败。如果你得到两棵树，并且它们碰巧有相同的值，那么你检查它们的左侧，如果它们没有相同的值，你检查它们的右侧。（这就是if工作原理。）我希望您真的想检查它们是否具有相同的值并且具有相同的左侧和相同的右侧。

您实际上可以使用一些布尔逻辑来简化这一点（右侧的注释应该会有所帮助）。这使用了一个tree?您尚未定义的谓词，但这并不难，而且它使这段代码更容易阅读。

(define (tree-equal? T1 T2)                       ; T1 and T2 are tree-equal iff
  (or (eq? T1 T2)                                 ; 1. are the same (this covers both being null), OR
      (and (tree? T1) (tree? T2)                  ; 2. a. both are trees, AND
           (eq? (value T1) (value T2))            ;    b. values are eq, AND
           (tree-equal? (left T1) (left T2))      ;    c. lefts are tree-equal, AND
           (tree-equal? (right T1) (right T2))))) ;    d. rights are tree-equal

论Lips中“树”的传统含义

现在，我知道您使用的是在每个中间节点都有元素的二叉树，但我要指出，“树”通常在 Lisp 上下文中用于表示由 cons 单元（即对）构建的任意结构. 可以使用相同的方法来比较它们，但它更清晰一点：

(define (tree-eq?  t1 t2)
  (or (eq? t1 t2)
      (and (pair? t1) (pair? t2)
           (tree-eq? (car t1) (car t2))
           (tree-eq? (cdr t1) (cdr t2)))))

巧合的是，此比较功能也适用于您的树类型，因为您的一个节点具有以下形式

(value . (left . (right . ())))

因此递归调用最终仍将同时处理来自两棵树的值、左侧和右侧。当然，这也会识别出实际上不是合法树的等效树（在传统意义上）（就您的问题而言）。这就是为什么拥有相应的tree?功能很重要（pair?对于传统情况来说很好）。

于 2013-10-15T20:22:42.567 回答