我正在自学Lisp，并认为一个不错的非平凡程序是编写一组标准的树插入和操作例程。 我认为可以用缺点来完成，但想尝试用结构来完成。
我整理了一个有效的版本：
(defstruct treenode data left right)
(defun tree-insert ( value tree )
"Insert data into tree"
(if tree
(if (< value (treenode-data tree))
(setf (treenode-left tree) (tree-insert value (treenode-left tree)))
(setf (treenode-right tree) (tree-insert value (treenode-right tree))))
(setf tree (make-treenode :data value)))
tree)
在每一步都重建了树，这在计算上似乎效率低下。 低效的意思是每次我做另一个级别的递归时我都必须使用 setf。所以我想尝试一种通过引用而不是值传递树的方案，这样我就可以在插入到树中的子例程中进行赋值。
我将以下内容拼凑在一起，这不起作用(但请感谢我的评论)：
(defstruct treenode data left right)
(defun tree-insert ( value tree )
"Insert data value into tree, using pass by reference.
value A datum to insert, in this version has to be a number.
tree The tree passed as a symbol."
(setq tval (symbol-value tree))
(if (eq tval nil)
(set tree (make-treenode :data value)) ; Empty tree. Place data here.
(if (< value (treenode-data tval)) ; Non-empty node. Decide which subtree for insert.
(tree-insert value (treenode-left tval)) ; Left side
(tree-insert value (treenode-right tval)))) ; Right side. This is a stable sort.
nil)
? (setf tr nil)
NIL
? (tree-insert 10 'tr)
NIL
? tr
#S(TREENODE :DATA 10 :LEFT NIL :RIGHT NIL)
?
初始插入工作正常。 传递符号(设置树...)正确插入结构，左右孔为零。
当然，随之而来的问题是，在对树插入的递归调用中，我没有传递符号。
这就是挂断。 我还没有找到一种方法将结构槽引用为一个符号，然后我可以传递给树插入。
我已经环顾四周几天，发现了关于 defstruct 宏的有趣评论："defstruct 不仅为每个插槽定义了一个访问函数，而且还安排 setf 在此类访问函数上正常工作，定义了一个名为 name-p 的谓词，定义了一个名为 make-name 的构造函数，并定义了一个名为 copy-name 的复制器函数。自动创建的函数的所有名称都驻留在处理 defstruct 表单时当前的任何包中(请参阅包)。此外，所有此类函数都可以由实现自行决定内联声明，以提高效率;如果您不希望某些函数以内联方式声明，请遵循带有 notinline 声明的 defstruct 窗体以覆盖任何自动内联声明。
那么，我能做些什么来施展 setf 的魔力呢？我知道我可以使用 setf 为插槽进行分配，但由于词法范围规则，我还没有让 setf 在函数中工作。 也许喜欢添加自动函数以允许符号生成，例如(树节点数据符号tr)？
当然，Lisp 程序员在我的第一个 PDP-8/L 之前就已经处理过二叉树了。口齿不清的方法是什么？
这是一个经过编辑的问题。 用户Rainer Joswig给出了非常快速和简洁的回应。 我从他举的例子中学到了很多东西。我对直接修改树而不是使用函数的返回值的问题感兴趣。
从我在这里看到的评论，以及 Rainer Joswig 的一个答案，我是否应该得出结论，即指针操作的计算成本很低，最好的 lisp 方法是使用返回树的函数，而不是依赖于修改参数的方法？
简单的版本，供您启发：
(defstruct node a b v)
(defun insert-tree (tree value)
(cond ((null tree)
(setf tree (make-node :v value)))
((> (node-v tree)
value)
(setf (node-a tree)
(insert-tree (node-a tree) value)))
(t
(setf (node-b tree)
(insert-tree (node-b tree) value))))
tree)
使用它：
CL-USER 171 > (let ((tree nil))
(loop for i in '(4 7 3 5 9 10 11 8)
do (setf tree (insert-tree tree i)))
(pprint tree)
(values))
#S(NODE :A #S(NODE :A NIL :B NIL :V 3)
:B #S(NODE :A #S(NODE :A NIL :B NIL :V 5)
:B #S(NODE :A #S(NODE :A NIL :B NIL :V 8)
:B #S(NODE :A NIL
:B #S(NODE :A NIL
:B NIL
:V 11)
:V 10)
:V 9)
:V 7)
:V 4)
现在，如果想做更少的setf操作，我们可以检查返回的子树是否与我们传递的子树相同。只有当我们创建新节点时，情况并非如此。
(defun insert-tree (tree value)
(cond ((null tree)
(setf tree (make-node :v value)))
((> (node-v tree)
value)
(let ((new-tree (insert-tree (node-a tree) value)))
(unless (eql new-tree (node-a tree))
(setf (node-a tree) new-tree))))
(t
(setf (node-b tree)
(insert-tree (node-b tree) value))))
tree)
或者使用本地宏隐藏部分代码：
(defun insert-tree (tree value)
(macrolet ((insert (place call &aux (new-value-sym (gensym "new-value")))
`(let ((,new-value-sym ,call))
(unless (eql ,place ,new-value-sym)
(setf ,place ,new-value-sym)))))
(cond ((null tree)
(setf tree (make-node :v value)))
((> (node-v tree)
value)
(insert (node-a tree) (insert-tree (node-a tree) value)))
(t
(insert (node-b tree) (insert-tree (node-b tree) value))))
tree))
尝试从另一个角度添加答案。
在标准的Common Lisp中，结构有很多限制，使它们是低级的和高效的使用。在这些限制中：
-
未定义通过插槽名称访问结构槽。有些实现可以这样做，有些则不然。
-
重新定义结构定义会产生未定义的后果。这意味着在某些情况下，最好重新启动 Lisp 来做到这一点......
这背后的想法是：对结构的所有操作都应该能够内联，并且执行程序不需要有关结构槽的任何进一步信息(它们的名称，它们的内存位置，...)。运行时不会有动态查找。
那么 Common Lisp 通常有这个进一步的限制：它没有第一类指针。没有机制可以提供仅直接指向结构插槽的指针。在一些较旧的 Lisp 方言中，这可以通过定位词的概念来实现 - 这些语言中的指针。Common Lisp 不支持这一点。
这实际上意味着：要更新结构的插槽，需要访问结构和二传手操作。
如何更新结构的插槽？
我可以想到两种简单的方法：
- 传递结构、新值和指标要更新的内容 ->然后调度指标并调用正确的更新程序
例
(defun update (s indicator value)
(case indicator
(:a (setf (node-a s) value))
(:b (setf (node-b s) value))))
(update tree :a (make-node :v 100))
- 传递一个闭包，该闭包执行更新
例：
(let ((tree ...))
(flet ((do-something (updater)
(funcall updater (make-node :v 100))))
(do-something (lambda (value) (setf (node-a tree) value) ...)))
非常感谢 Rainer 和 Will，我现在更了解 Common Lisp。 关于没有一流指针的要点是巨大的。我不必再继续寻找它了，尽管我确实看到了一个在我的搜索中实现 refs 的包。
我的方法中的关键问题是我将一棵空树定义为 nil。 由于传递 nil 不允许对参数进行任何操作，nil 是不可变的，因此算法注定会失败。
将空树重新定义为'(nil)允许程序工作。
;; Make list of 5 random numbers.
(setf r5 (loop for i from 1 to 5 collect (random 100)))
;; Initialize tr to empty tree.
;; Empty tree is '(nil). Tree with data is '(data left right),
;; where left and right are either empty tree or tree with data.
(setf tr '(nil))
(defun tree-insert ( value tree )
"Insert data into tree. tree is modified with an insertion."
(if (equal tree '(nil))
(progn ; Empty (sub)tree. Insert value.
(setf (car tree) value)
(setf (cdr tree) (list (list nil)(list nil))))
(progn ; Non-empty subtree.
(if (< value (car tree))
(tree-insert value (second tree)) ; Insert on left.
(tree-insert value (third tree))))) ; Insert on right.
nil)
;; Load tree with the list of random numbers defined above.
(mapc (lambda (val) (tree-insert val tr)) r5)
(defun tree-walk (tree)
"Retrieve keys in sorted order."
(if (car tree)
(progn
(tree-walk (second tree)) ; Left subtree.
(format t " ~d" (car tree))
(tree-walk (third tree))))) ; Right subtree.
;; Walk the tree.
(tree-walk tr)
使用中的示例：
? (setf r5 (loop for i from 1 to 5 collect (random 100)))
(22 50 76 20 49)
? (setf tr '(nil))
(NIL)
? (mapc (lambda (val) (tree-insert val tr)) r5)
;Compiler warnings :
; In an anonymous lambda form at position 37: Undeclared free variable TR
(22 50 76 20 49)
? tr
(22 (20 (NIL) (NIL)) (50 (49 (NIL) (NIL)) (76 (NIL) (NIL))))
? (tree-walk tr)
20 22 49 50 76
NIL
?
因此，有几件事可以使这项工作。必须将可变对象传递给过程。 在这种情况下，我将结构重新设计为列表，'(nil)表示空，或"(数据左右)，其中左和右是'(nil)或'(数据左右)。可以操作包含 nil 的列表。但是，我不得不使用 car 和 cdr 来访问结构，以便保留传递给过程的 Lisp 指针。
我必须做的另一件事是不在函子定义中使用列表常量。 我相信知识渊博的人会知道这一点，并在理解问题之前对随后的不透明错误进行一些了解，但是如果我在树插入中使用"((nil)(nil))而不是(列表(列表nil)(list nil))它将不起作用。 看起来 Lisp 编译列表速记符号到一个指向内存中 abject 的指针，该指针用于该函数的所有后续调用。
哦，树插入中有一个剩余的 progn 函数调用。 那是从我用 progn 包装所有内容以让我在调试期间添加打印语句开始的。
函数的运行计时很有趣。 太快了！我将运行一些时序比较，以比较功能重新分配方法与搜索和插入算法。
再次感谢专家的评论。 自从上次贡献以来，我已经了解了一些关于map，循环/收集的知识，以及当let不在函数定义中使用时，变量会从函数泄漏到全局空间中。还包装了一个具有大量输出的功能(progn ...nil) 在使用大型数据结构后节省屏幕空间。通过这个练习，我学到了很多东西。