HTML CSS JAVASCRIPT BOOTSTRAP JQUERY PHP SQL PYTHON PYTHON2 JAVA C C++ C# Linux AI 教程库 参考手册 测验 练习 HOWTO FAQ
❮ 上一节 下一节 ❯

LISP - 树结构

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

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

作为列表的列表的树

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

((1 2) (3 4) (5 6)).

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

树结构

LISP 中的树函数

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

除了所有列表函数之外，以下函数尤其适用于树结构 −

序号 函数及说明
1

copy-tree x & optional vecp

它返回 cons 单元 x 树的副本。 它递归地复制 cars 和 cdr 方向。 如果 x 不是 cons 单元格，则该函数将简单地返回 x 不变。 如果可选的 vecp 参数为 true，则该函数将复制向量（递归地）以及 cons 单元。
2

tree-equal x y & key :test :test-not :key

它比较两棵 cons 单元树。 如果 x 和 y 都是 cons 单元，则递归比较它们的 cars 和 cdrs。 如果 x 和 y 都不是 cons 单元格，则通过 eql 或根据指定的测试来比较它们。 :key 函数（如果指定）将应用于两棵树的元素。
3

subst new old tree & key :test :test-not :key

它用树中的新项目替换给定旧项目的出现，这是一棵cons单元树。
4

nsubst new old tree & key :test :test-not :key

它的工作方式与 subst 相同，但它会破坏原始树。
5

sublis alist tree & key :test :test-not :key

它的工作方式与 subst 类似，只是它需要一个新旧对的关联列表alist。 树的每个元素（在应用 :key 函数之后，如果有的话）与 alist 的 cars 进行比较； 如果匹配，则替换为相应的cdr。
6

nsublis alist tree & key :test :test-not :key

它的工作原理与 sublis 相同，但是是一个破坏性版本。

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))

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))
)

示例

本示例使用了上述功能 −

创建一个名为 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)))
❮ 上一节 下一节 ❯