显示二叉树的中序遍历

Question

我想制作一个显示二叉树中序遍历的列表。这是我的代码：

 (define btree 
 '(1 (2 (4 (7 #f #f) #f) (5 #f #f)) (3 (6 (8 #f #f) (9 #f #f)) #f)))

(define res '())

(define (inorder tree)
  (let loop ([t tree])
    (cond (t (loop (cadr t)) (cons (car t) res) (loop (caddr t)))
      (else res))))

(inorder btree '())
res

返回的列表是'()，不知道为什么。如果我写

    (cond (t (loop (cadr t)) (printf "~s " (car t)) (loop (caddr t)))

它打印出正确的结果。编辑：访问实际上是 res.

Answer 1

您的代码不起作用（什么是 visit？inorder 只接受一个参数），您在 SO 上发帖时真的应该更加小心。此外，您应该包括一个示例调用和所需的结果。

尽管如此，你已经很接近了。您的主要问题是您将 res 设为全局变量，而全局变量很少可以很好地处理递归。此外，可能由于这个原因，returning res 没有得到妥善管理。假设您的第二个实现 display 的结果是正确的，这是正确的代码：

(define (inorder tree)
  (let loop ((t tree) (res '()))
    (if t
        (loop (cadr t) (cons (car t) (loop (caddr t) res)))
        res)))

如你所见

首先我们执行(loop (caddr t) res)
使用这个调用的结果作为新的res，我们执行(cons (car t) <new-res>)
最后，再次使用之前的结果作为新的 res 我们做 (loop (cadr t) <even newer res>)

当然，如果 t 为假，我们只是 return res 让前面的逻辑起作用。

我冒昧地使用 if 而不是 cond，当然 cond 也可以。

测试：

> (inorder '(1 (2 (4 (7 #f #f) #f) (5 #f #f)) (3 (6 (8 #f #f) (9 #f #f)) #f)))
'(7 4 2 5 1 8 6 9 3)

显示二叉树的中序遍历

Show inorder traversal of binary tree

scheme

racket