1

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

(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，它以 list-of-lists 的形式提供了部分正确的答案：

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

然而，正确的答案是：

(2 3 + 7 8 - *)

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

放心，等基本的递归函数搞清楚后，我会把它变成一个尾递归函数。

感谢任何可以提供帮助的人！

4

4 回答 4

2

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

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

于 2015-12-21T01:13:06.330 回答
2

当这些对cons和append的调用发生时，考虑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 ，因为那样您会得到一个不正确的列表，如上图所示。您可能会发现方案中的点符号有助于理解其.含义。如您所见，稍后对append的调用将抱怨不正确的列表：

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

如果您自己没有实现append ，则append的参数具有您可能认为不寻常的要求。附加文档说：

句法：

追加 &rest 列表 ⇒ 结果

参数和值：

list——每个必须是一个正确的列表，除了最后一个，它可以是任何对象。

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

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

(append (bin-tree-postorder left)
        (bin-tree-postorder right)
        (list elmt))
于 2015-12-21T14:58:35.840 回答
1

如果您不想使用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)))))

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

于 2015-12-21T03:16:43.697 回答
-1

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

于 2015-12-21T02:55:50.397 回答