1

我正在尝试在不使用附加的情况下编写中序遍历，这是我的代码

 (define inorder
    (lambda (tree)
      (define inorder-iter
        (lambda (tree list)
          (if (empty-tree? tree)
               list
               (cons (inorder-iter (left-subtree tree) 
                     (root tree) 
                     (inorder-iter (right-subtree tree) list)))))

    (inorder-iter tree '() )))

  (define empty-tree? null?)

  (define root car)

  (define left-subtree cadr)

  (define right-subtree caddr)


 tree-1
(9
 (6 (5 () ()) ())
 (18 (11 () (13 () (17 () ()))) (65 (52 (41 (39 () ()) ()) ()) (99 () ()))))

当我调用 (inorder tree-1) 时，我得到 (((5 . 6) . 9) (11 13 17 . 18) (((39 . 41) . 52) . 65) 99) 这看起来非常糟糕。我想要得到的是'（5 6 9 11 13 17 18 39 41 52 65 99）。我到底做错了什么？谢谢！

4

1 回答 1

2

你的括号有几个问题。另请注意，您没有使用该list参数 - 更重要的是，它的名称很糟糕，因为它与内置过程发生冲突。

问题要求我们不使用内置append函数，但是简单的cons不行。这是一个可能的解决方案：

(define inorder
  (lambda (tree)
    (define inorder-iter
      (lambda (tree lst)
        (if (empty-tree? tree)
            lst
            (inorder-iter (left-subtree tree)
                          (cons (root tree)
                                (inorder-iter (right-subtree tree)
                                              lst))))))
    (inorder-iter tree '())))

它按预期工作：

(inorder tree-1)
=> '(5 6 9 11 13 17 18 39 41 52 65 99)
于 2013-11-03T05:41:13.757 回答