Common Lisp 二叉树

Question

我正在尝试使用 GNU ClISP 在 Common Lisp 中编写一个程序来编译它。我想输入一个列表，例如 (A(B (C) ()) (D (E) (F (G) ()))) 并根据第一个单词打印出前序、中序或后序遍历。示例：

(pre '(A(B (C)... etc))

我无法将我的逻辑转化为 Clip 表示法。我目前有以下代码：

(defun leftchild (L)(cadr L))

(defun rightchild (L)(caddr L))

(defun data (L)(car L))

(defun pre (L)(if (null L) '()((data L)(pre(leftchild L))(pre(rightchild L)))))

... similar in and post functions

我收到编译错误，指出我应该在 pre 函数中使用 lambda。我认为这是由于数据前面的双 (( 因为它需要一个命令，但我不确定应该放在那里什么。我认为 cond 不起作用，因为这会阻碍递归循环。另外， data L 会按现在的样子打印吗？编译器无法识别(print (data L))。

我已经研究这个代码一个多星期了，试图自己排除故障，但我如果有人我会很感激。可以解释我做错了什么。

我的另一个问题是如何让程序提示用户输入 (pre '(A... etc)) ，以便当我运行编译的文件时该程序会运行而不是给出 funcall 错误吗？

谢谢您的时间。

Answer 1

简短回答：如果您想使用 if，请注意，您需要一个 progn 以便在后续和替代情况下拥有多个形式。

---

长答案 - 还解释了如何遍历累积列表中的访问节点：

我想这是家庭作业，所以我不会给你一个完整的解决方案，但你的问题表明你基本上有正确的想法，所以我会展示你可以用一种简单、惯用的方式来做到这一点。

首先，你是对的：不带引号的形式的 car 应该是一个函数，所以基本上像 (foo ...) 这样的东西，其中 foo 不是一个函数（或宏，特殊形式...），并且整个事情都要被评估，将是一个错误。请注意，这不适用于特殊形式和宏（例如 cond）。这些可以改变评估规则，并且并非所有看起来像 (foo bar) 的东西都必须是由正常评估规则评估的形式。最简单的例子是 quote，它只是返回未计算的参数，因此 (quote (foo bar)) 将不会成为错误。

现在，关于您的问题：

一个简单的解决方案是拥有一个累加器和一个遍历树的递归辅助函数，并将值推送到累加器中。像这样的：

(defun pre (node)
  (let ((result (list)))
    (labels ((rec (node)
               (cond (...
                      ...
                      ...))))
      (rec node)
      (nreverse result))))

labels 只是引入了一个本地辅助函数，它将执行实际的递归，而外部的 let 为您提供了一个累加器来收集节点值。该解决方案将以列表形式返回结果。如果您只想打印每个节点的值，则不需要累加器或辅助函数。只需打印而不是推送，并使助手成为您的顶级功能。

请记住，您需要一个递归停止的基本情况。您应该在 cond 中检查这一点。然后，您需要每个子树的递归步骤，并且需要将节点的值推送到结果。执行这些步骤的顺序决定了您是进行前序遍历、中序遍历还是后序遍历。你的代码表明你已经理解了这个原理，所以你只需要让它在 Lisp 代码中工作即可。您可以使用 push 将值推送到 result，并使用 consp 检查节点是否为非空列表。由于对空列表没有任何作用，因此您基本上只需要在 cond 中进行一次测试，但您也可以显式检查节点是否为 null，就像您所做的那样在你的代码中。