Lisp

Question

为了好玩而学习 lisp，到现在为止还没有遇到太多困难，而且我正在 this site. 的第三讲，我正在努力完成练习 "Implement a function that will create a list containing members of a given binary tree in postorder." 到目前为止，这是我的代码：

(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

append 将列表组合在一起；树的 element 不是列表。所以要么你不能使用 append，要么你必须从 element.

中创建一个列表

因此，第二种情况可以写成(append (bin-tree-postorder left) (bin-tree-postorder right) (list elmt)).

Answer 2

push 是您正在寻找的——将新元素推到列表的末尾。 reverse 如有必要，完成后。

Answer 3

如果您不想使用append，您可以使用累加器反向构建列表。这是执行此操作的代码。

(defun bin-tree-postorder (b &optional accumulator)
  (if (bin-tree-leaf-p b)
      (cons (bin-tree-leaf-element b) accumulator)
      (bin-tree-postorder (bin-tree-node-left b)
                          (bin-tree-postorder (bin-tree-node-right b)
                                              (cons (bin-tree-node-element b)
                                                    accumulator)))))

该函数所做的是将 post 排序树的结果附加到累加器。它递归地工作，首先将当前元素添加到累加器，将右子树的 post 顺序附加到累加器，然后将左子树的 post 顺序附加到累加器。

Answer 4

考虑 left、right 和 elmt 的值=37=]cons 和 append 发生：

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

bin-tree-postorder 应该 return一个列表，所以调用append 应该就可以了。（我知道这实际上还不是真的，但我们正在假设递归调用正常。）所以现在函数将 return 的值：

(cons <appended-postorder-results> elmt)

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

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 必须走到每个列表的末尾（列表除外）以构建一个新列表，该列表最终由（的副本终止） ) 下一个列表。这意味着 "replacing" 最后的 nil 与下一个列表。不正确的列表（如 (1 . 2) 末尾没有 nil。

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

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

Lisp - 后序二叉树的问题

Lisp - Problems with postordering a binary tree

common-lisp

binary-tree

postorder

Syntax:

Arguments and Values: