LISP - 树

您可以从 cons 单元构建树数据结构，作为列表的列表。

要实现树结构，您必须设计按特定顺序遍历 cons 单元的功能，例如二叉树的前序、中序和后序。

作为列表的列表的树

让我们考虑一个由 cons 单元组成的树结构，这些单元形成以下列表列表 -

（（1 2）（3 4）（5 6））。

从图表上看，它可以表示为 -

LISP 中的树函数

虽然大多数情况下您需要根据您的具体需要编写自己的树功能，但 LISP 提供了一些您可以使用的树功能。

除了所有列表函数之外，以下函数特别适用于树结构 -

先生。	功能说明
1	复制树x 和可选的 vecp 它返回 cons cells x 树的副本。它递归地复制汽车和 cdr 方向。如果 x 不是 cons 单元格，则该函数将简单地返回 x 不变。如果可选的 vecp 参数为 true，则该函数将复制向量（递归地）以及 cons 单元。
2	树等于xy & key :test :test-not :key 它比较两棵 cons 单元树。如果 x 和 y 都是 cons 单元，则递归比较它们的 cars 和 cdrs。如果 x 和 y 都不是 cons 单元格，则通过 eql 或根据指定的测试来比较它们。:key 函数（如果指定）将应用于两棵树的元素。
3	替换新旧树和密钥：测试：测试-不是：密钥它用新项目替换给定旧项目的出现，在树中，这是一个 cons 单元树。
4	nsubst新旧树 & key :test :test-not :key 它的工作原理与 subst 相同，但它破坏了原始树。
5	sublis alist 树 & key :test :test-not :key 它的工作方式与 subst 类似，只是它需要一个新旧对的关联列表alist 。树的每个元素（在应用 :key 函数之后，如果有的话）与 alist 的汽车进行比较；如果匹配，则替换为相应的cdr。
6	nsublis alist 树 & key :test :test-not :key 它的工作原理与 sublis 相同，但是是一个破坏性版本。

实施例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

创建一个名为 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))
)

例子

此示例使用上述功能 -

创建一个名为 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)))