SCHEME二叉搜索树的预序/后序/序遍历

Question

尝试遍历方案中的树，当我尝试实际调用/运行函数时，我一直得到一个错误。

(define (make-tree value left right)
(list left value right))
(define (root tree)
(car tree))
(define (left tree)
(car (cdr tree)))
(define (right tree)
(car (cdr (cdr tree))))
(define (preorder tree)
(if (null? tree)
'()
(append (list (root tree))
(preorder (left tree))
(preorder (right tree)))))
(define (inorder tree)
(if (null? tree)
'()
(append (inorder (left tree))
(list (root tree))
(inorder (right tree)))))

(define (postorder tree)  
(if (null? tree)
'()
(append (postorder (left tree))
(postorder (right tree))
(list (root tree)))))

当我调用函数时，我得到一个car或cdr矛盾错误。执行这些函数的正确方法是什么?

Answer 1

函数make-tree和访问器root-left-right不匹配:当您使用make-tree创建树时，根值将在中间，但您的root函数访问列表的car。

那么，重写make-tree如下:

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

参见这个问题的示例树和示例调用和结果。