Lisp - 后序二叉树的问题

Question

为了好玩而学习 lisp，到现在为止没有遇到太多困难，我正在上this site.的第三讲|我正在尝试完成练习“实现一个函数，该函数将创建一个包含后序给定二叉树成员的列表。”到目前为止，这是我的代码:

(defun bin-tree-postorder (b)
  "Create a list containing keys of b in postorder"
  (if (bin-tree-leaf-p b)
      (list (bin-tree-leaf-element b))
    (let
        ((elmt (bin-tree-node-element b))
         (left (bin-tree-node-left b))
         (right (bin-tree-node-right b)))
  (cons
        (append (bin-tree-postorder left)
                    (bin-tree-postorder right)) elmt))))

但是，它不会运行，因为我收到以下错误:

*** - APPEND: A proper list must not end with +

这是我的踪迹:

1. Trace: (BIN-TREE-POSTORDER '(* (+ (2) (3)) (- (7) (8))))
2. Trace: (BIN-TREE-POSTORDER '(+ (2) (3)))
3. Trace: (BIN-TREE-POSTORDER '(2))
3. Trace: BIN-TREE-POSTORDER ==> (2)
3. Trace: (BIN-TREE-POSTORDER '(3))
3. Trace: BIN-TREE-POSTORDER ==> (3)
2. Trace: BIN-TREE-POSTORDER ==> ((2 3) . +)
2. Trace: (BIN-TREE-POSTORDER '(- (7) (8)))
3. Trace: (BIN-TREE-POSTORDER '(7))
3. Trace: BIN-TREE-POSTORDER ==> (7)
3. Trace: (BIN-TREE-POSTORDER '(8))
3. Trace: BIN-TREE-POSTORDER ==> (8)
2. Trace: BIN-TREE-POSTORDER ==> ((7 8) . -)

我试过使用 list 而不是 cons，它以列表列表的形式提供了部分正确的答案:

(((2 3) + (7 8) -) *)

然而，正确答案是:

(2 3 + 7 8 - *)

任何回答的人都可以提供提示或指示，而不是修改代码，以便我更好地理解问题吗？我宁愿不看教程的答案，因为那不会帮助我了解我做错了什么。

放心，等基本递归函数搞定了，我就把它变成尾递归函数。

感谢任何能提供帮助的人!

Answer 1

当这些调用 cons 和 时，请考虑 left、right 和 elmt 的值追加 发生:

  (cons
        (append (bin-tree-postorder left)
                    (bin-tree-postorder right)) elmt))))

bin-tree-postorder 应该 返回一个列表，所以调用append 应该 没问题。 (我知道这实际上还不是真的，但我们正在假设递归调用正常。)所以现在函数将返回值:

(cons <appended-postorder-results> elmt)

现在，elmt 类似于符号 +。让我们使用 REPL 看看这样的调用会返回什么:

CL-USER> (cons '(2 3) '+)
((2 3) . +)

那不是你想要的。您想要列表 (2 3 +)。为此，您不想在 elmt 上使用 cons，因为那样您会得到一个不正确的列表，如上所示。您可能会找到 Dot notation in scheme 有助于理解 . 的含义。稍后调用 append 将提示不正确的列表，如您所见:

CL-USER> (append '((2 3) . +) '(4 5))
; Evaluation aborted on #<TYPE-ERROR expected-type: LIST datum: +>.

append 的参数有一些要求，如果您自己没有实现append，您可能会认为这些要求不寻常。 append 的文档说:

Syntax:

append &rest lists ⇒ result

Arguments and Values:

list—each must be a proper list except the last, which may be any object.

原因是 append 必须走到每个列表(列表除外)的末尾以构建一个新列表，该新列表最终由下一个列表(的副本)终止。这意味着用下一个列表“替换”最后的 nil。不正确的列表(例如 (1 . 2) 末尾没有 nil。

您可以做的最简单的事情就是简单地删除 cons，并向 append 添加一个参数，即包含 elmt 的列表:

(append (bin-tree-postorder left)
        (bin-tree-postorder right)
        (list elmt))