方案 - 二叉树迭代递归附加 () 作为一个空节点而不是什么都没有

Question

我正在尝试编写一个简单的代码，其中 returns 以 "pre-order" 方式列出树节点值。

(define pre-iter  (lambda (tree)
(if (not (pair? tree))
    (list tree)
    (append (list (car tree)) (pre-iter (cadr tree)) (pre-iter (caddr tree)))
)))

我无法找出为什么会发生以下情况：

  (iter-tree (quote (F (B A (D C E)) (G () (I H ())))) pre-iter): expected '(F B A D C E G I H), got '(F B A D C E G () I H ())

感谢您的帮助。

Answer 1

你只需要处理一个子树为空的额外情况。试试这个：

(define pre-iter
  (lambda (tree)
    (cond ((null? tree) '())
          ((not (pair? tree)) (list tree))
          (else
           (append (list (car tree))
                   (pre-iter (cadr  tree))
                   (pre-iter (caddr tree)))))))

它按要求工作：

(pre-iter '(F (B A (D C E)) (G () (I H ()))))
=> '(F B A D C E G I H)

方案 - 二叉树迭代递归附加 () 作为一个空节点而不是什么都没有

Scheme - binary tree iteration recursion appends () as an empty Node instead of nothing

recursion

scheme

append