LISP - Tree
您可以从cons单元构建树数据结构，作为列表列表。
要实现树结构，您必须按特定顺序设计将遍历cons单元的功能，例如，二叉树的预订，有序和后订单。
树作为列表列表
让我们考虑由cons单元组成的树结构，它构成以下列表列表 -
（（1 2）（3 4）（5 6））。
从图中可以看出，它可以表示为 -
LISP中的树函数
虽然大多数情况下您需要根据您的具体需要编写自己的树功能，但LISP提供了一些您可以使用的树功能。
除了所有列表函数之外，以下函数特别适用于树结构 -
| Sr.No. | 功能说明 |
|---|---|
| 1 | copy-tree x和可选的vecp 它返回cons单元格x的副本。 它以递归方式复制汽车和cdr方向。 如果x不是cons单元格，则该函数只返回x不变。 如果可选的vecp参数为true，则此函数复制向量（递归）以及cons单元格。 |
| 2 | tree-equal xy＆key:test:test-not:key 它比较两个cons细胞树。 如果x和y都是cons单元格，则递归地比较它们的汽车和cdrs。 如果x和y都不是cons单元格，则通过eql或根据指定的测试对它们进行比较。 :key函数（如果已指定）将应用于两个树的元素。 |
| 3 | subst new old tree＆key:test:test-not:key 它用tree new项替换给定旧项的出现，这是一个缺点单元格的树。 |
| 4 | nsubst new old tree＆key:test:test-not:key 它与subst相同，但它会破坏原始树。 |
| 5 | sublis alist tree＆key:test:test-not:key 它像subst一样工作，除了它需要一个新旧对的关联列表。 树的每个元素（在应用:key函数之后，如果有的话）与alist的汽车进行比较; 如果匹配，则由相应的cdr替换。 |
| 6 | nsublis alist tree＆key:test:test-not:key 它与sublis相同，但是具有破坏性版本。 |
例子1 (Example 1)
创建一个名为main.lisp的新源代码文件，并在其中键入以下代码。
(setq lst (list '(1 2) '(3 4) '(5 6)))
(setq mylst (copy-list lst))
(setq tr (copy-tree lst))
(write lst)
(terpri)
(write mylst)
(terpri)
(write tr)
执行代码时，它返回以下结果 -
((1 2) (3 4) (5 6))
((1 2) (3 4) (5 6))
((1 2) (3 4) (5 6))
例子2 (Example 2)
创建一个名为main.lisp的新源代码文件，并在其中键入以下代码。
(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(write tr)
(setq trs (subst 7 1 tr))
(terpri)
(write trs)
执行代码时，它返回以下结果 -
((1 2 (3 4 5) ((7 8) (7 8 9))))
((7 2 (3 4 5) ((7 8) (7 8 9))))
建立自己的树
让我们尝试使用LISP中提供的列表函数构建我们自己的树。
首先让我们创建一个包含一些数据的新节点
(defun make-tree (item)
"it creates a new node with item."
(cons (cons item nil) nil)
)
接下来让我们将一个子节点添加到树中 - 它将需要两个树节点并将第二个树添加为第一个树的子节点。
(defun add-child (tree child)
(setf (car tree) (append (car tree) child))
tree)
此函数将返回给定树的第一个子节点 - 它将采用树节点并返回该节点的第一个子节点，如果此节点没有任何子节点，则返回nil。
(defun first-child (tree)
(if (null tree)
nil
(cdr (car tree))
)
)
此函数将返回给定节点的下一个兄弟节点 - 它将树节点作为参数，并返回对下一个兄弟节点的引用，如果节点没有，则返回nil。
(defun next-sibling (tree)
(cdr tree)
)
最后，我们需要一个函数来返回节点中的信息 -
(defun data (tree)
(car (car tree))
)
例子 (Example)
此示例使用上述功能 -
创建一个名为main.lisp的新源代码文件，并在其中键入以下代码。
(defun make-tree (item)
"it creates a new node with item."
(cons (cons item nil) nil)
)
(defun first-child (tree)
(if (null tree)
nil
(cdr (car tree))
)
)
(defun next-sibling (tree)
(cdr tree)
)
(defun data (tree)
(car (car tree))
)
(defun add-child (tree child)
(setf (car tree) (append (car tree) child))
tree
)
(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(setq mytree (make-tree 10))
(write (data mytree))
(terpri)
(write (first-child tr))
(terpri)
(setq newtree (add-child tr mytree))
(terpri)
(write newtree)
执行代码时，它返回以下结果 -
10
(2 (3 4 5) ((7 8) (7 8 9)))
((1 2 (3 4 5) ((7 8) (7 8 9)) (10)))
