显示二叉树的遍历

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))) 

它打印正确的结果。编辑：访问实际上是水库。

Answer 1

您的代码不起作用（visit？inorder只有一个参数），在SO上发布问题时应该更仔细。此外，您应该包含一个示例调用和期望的结果。

尽管如此，你是非常接近。你主要的问题是你制作了一个全局变量res，而全局变量很少用和递归配合。此外，也可能是因为这个原因，返回res未正确管理。通过你的第二个实施假设结果display ED是正确的，这是正确的代码：

(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是错误的，我们只需返回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)