SCHEME Preorder/Postorder/Inorder 二叉搜索树的遍历

Question

试图遍历方案中的树，但当我尝试实际 call/run 函数时，我一直收到错误消息。

(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 contradiction 错误。执行这些功能的正确方法是什么？

Answer 1

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

所以，像这样重写 make-tree：

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

另请参阅 this question 示例树以及调用和结果示例。

SCHEME Preorder/Postorder/Inorder 二叉搜索树的遍历

SCHEME Preorder/Postorder/Inorder Traversal of a binary search tree

tree

scheme

racket