Scheme二叉搜索树中序遍历遇car契约违反错误求助

你遇到的car: contract violation错误，核心原因是代码处理到(a . b)这类pair节点时，执行了(car (cdr lst))——也就是(car b)，但b不是pair，违反了car仅能作用于pair的规则。你的代码默认所有pair类型的节点，其cdr部分也必须是pair，但你的树结构中存在cdr为单个值的pair，导致触发错误。

修复方案一：修正树的结构（推荐） #

确保每个内部节点遵循(左子树 . (节点值 . 右子树))的结构（等价于更直观的列表形式(左子树 节点值 右子树)），这样每个pair的cdr都是pair，原代码即可正常运行。修改tree-a的定义：

; 点对形式
(define tree-a '((a . (b . ())) . (c . ((d . (e . ())) . ()))))
; 或列表形式（更易读）
; (define tree-a '((a b ()) c (d e ())))

此时运行原代码，会得到正确的中序遍历结果：(a b c d e)。

修复方案二：修改代码适配现有树结构 #

如果不想调整树的结构，可以给代码增加对cdr是否为pair的判断，专门处理cdr是单个值的情况。假设这种情况下，pair的car是左子树，cdr是节点值，右子树为空：

(define (inorder lst)
  (cond
    ((null? lst)
     '())
    ((not (pair? lst))
     (list lst))
    ((not (pair? (cdr lst)))
     (append (inorder (car lst))
             (list (cdr lst))
             '()))
    (else 
     (append (inorder (car lst))
             (list (car (cdr lst)))
             (inorder (cdr (cdr lst)))))))

(define tree-a '((a . b) . (c . (d . e))))
(inorder tree-a) ; 输出: (a b c d e)

内容的提问来源于stack exchange，提问作者Dave Filoni