Jis*_*Yoo 4 lisp tree common-lisp
来自 Common Lisp HyperSpec 词汇表：
树ñ。1. 由 conses 和 atom 组成的二进制递归数据结构：conses 本身也是树（有时称为“子树”或“分支”），而原子是终端节点（有时称为叶子）。通常，叶子代表数据，而分支在这些数据之间建立某种关系。2. 一般来说，任何具有“分支”和叶子概念的递归数据结构。
树形结构ñ。（一棵树的）构成这棵树的一组 conses。请注意，虽然每个这样的 cons 的 car[1b] 组件是树结构的一部分，但作为树中每个 cons 的汽车的对象本身并不是其树结构的一部分，除非它们也是 conses。
树结构定义中的最后一句提出了一个问题，那就是，cdrs 也可以这样说吗？
在“树”的定义中使用二进制一词似乎表明就树而言，汽车与 cdr 之间没有区别，但是“树结构”的定义似乎对汽车特殊对待，所以我很困惑。
树结构定义中的最后一句提出了一个问题，那就是，cdrs 也可以这样说吗？
我想答案是肯定的。列表结构有类似的定义，措辞几乎相同。在列表结构中，关于 cons 的 car 的值是否是列表结构的一部分，更容易混淆，因为可能会出现以下问题，例如“替换列表中的 X 意味着什么 (X (X)是）？” cdr 问题不大，因为 cdr 是列表的其余部分；它显然是列表结构的一部分。
对于tree structure，我认为有较少的歧义；汽车或 cdr 中的缺点是子树。树结构和列表结构的定义在某些地方几乎相同，如果有人编写了列表结构的定义，然后将其复制到树结构，从而使必要的更改次数最少，我也不会感到惊讶。即使它回答的问题在实践中可能不会出现，也会留下一些关于汽车的内容。
我们看一下列表结构的定义并比较：
表结构ñ。（列表的）构成列表的一组 conses。请注意，虽然每个这样的 cons 的 car 组件是列表结构的一部分，但作为列表元素的对象（即，作为列表中每个 cons 的汽车的对象）本身并不是其列表结构的一部分，即使它们是 conses，除非在（循环）情况下列表实际上包含其尾部之一作为元素。（列表的列表结构有时被多余地称为“顶级列表结构”，以强调不涉及作为列表元素的任何 conses。）
请注意这些不同的具体地方：
（列表结构）请注意，虽然每个这样的 cons 的 car 组件是列表结构的一部分，但作为列表元素的对象（即作为列表中每个 cons 的汽车的对象）本身不是列表结构的一部分它的列表结构，即使它们是 conses。
（树结构）请注意，虽然每个这样的 cons 的 car 组件是树结构的一部分，但作为树中每个 cons 的汽车的对象本身并不是其树结构的一部分，除非它们也是 conses。
这意味着在
(1 (2) 3) == (cons 1 (cons (cons 2 nil) (cons 3 nil)))
列表结构中有三个cons 单元，树结构中有四个cons 单元。
这实际上在哪里重要？精确定义这些术语变得很重要，以便规范可以轻松定义特定函数遍历或修改列表或树的哪些部分。
例如，函数nsubst和friends，其文档说明：
nsubst、nsubst-if 和 nsubst-if-not 可能会改变树的树结构。
树结构的特定定义使我们能够了解nsubst可以更改和不可以更改哪些内容。
树形结构ñ。（树的）构成树的一组 conses。请注意，虽然每个这样的 cons 的 car 组件是树结构的一部分，但作为树中每个 cons 的汽车的对象本身并不是其树结构的一部分，除非它们也是 conses。
所以，这告诉我们的是，对于树中的任何 cons 单元x，nsubst可能会执行(setf (car x) ...)，因此(car x)稍后可能会有所不同，但不会修改(car x)返回的实际对象（当然，除非它是一个缺点）。在(car x)的值是一个内部可能有树的对象的情况下，这可能很重要。因此，例如，nsubst不会下降到向量，但它会替换向量：
(let* ((l (list 1 2 3)) ; a list
(v (vector 0 l 4)) ; a vector that contains the list (and other elements)
(tree (cons l v))) ; a tree containing the list and the vector
(nsubst 'x l tree)) ; replace the list in the tree with X
;=> (X . #(0 (1 2 3) 4)) ; nsubst doesn't descend into the vector, because it's
; not tree structure
另一方面，删除重复只会修改列表结构：
当序列是一个列表时，delete-duplicates 被允许设置该序列中顶级列表结构的任何部分，car 或 cdr。当序列是一个向量时，允许删除重复来改变向量的维度并将其元素滑入新位置，而不用排列它们来产生结果向量。