Lisp - 树

您可以使用 cons 单元格（作为列表的列表）构建树数据结构。

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

树作为列表的列表

让我们考虑一个由构成以下列表的列表的 cons 单元格组成的树结构：

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

图示表示如下：

LISP 中的树函数

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

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

序号	函数 & 描述
1	copy-tree x & 可选参数 vecp 它返回 cons 单元格树 x 的副本。它递归地复制 car 和 cdr 方向。如果 x 不是 cons 单元格，则函数只是返回未更改的 x。如果可选参数 vecp 为真，则此函数也会递归地复制向量以及 cons 单元格。
2	tree-equal x y & key :test :test-not :key 它比较两个 cons 单元格树。如果 x 和 y 都是 cons 单元格，则它们的 car 和 cdr 会被递归地比较。如果 x 和 y 都不是 cons 单元格，则它们将通过 eql 进行比较，或根据指定的测试进行比较。如果指定了 :key 函数，则将其应用于两棵树的元素。
3	subst new old tree & key :test :test-not :key 它用new项替换tree中给定old项的出现，其中tree是 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 的 car 进行比较；如果匹配，则将其替换为相应的 cdr。
6	nsublis alist tree & key :test :test-not :key 它的作用与 sublis 相同，但它是破坏性的版本。

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

main.lisp

; create and set a list to lst 
(setq lst (list '(1 2) '(3 4) '(5 6)))
; copy and set a list to mylst
(setq mylst (copy-list lst))
; copy tree and set to tr
(setq tr (copy-tree lst))
; print the first list
(write lst)
; terminate printing
(terpri)
; print the second list
(write mylst)
; terminate printing
(terpri)
; print tree
(write tr)

输出

执行代码时，它会返回以下结果：

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

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

main.lisp

; set a tree to tr
(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
; print tree
(write tr)
; set trs as subtree
(setq trs (subst 7 1 tr))
; terminate printing
(terpri)
; print tree
(write trs)

输出

执行代码时，它会返回以下结果：

((1 2 (3 4 5) ((7 8) (7 8 9))))
((7 2 (3 4 5) ((7 8) (7 8 9))))

构建您自己的树

让我们尝试使用 LISP 中可用的列表函数来构建我们自己的树。

首先让我们创建一个包含一些数据的新节点

; define a function to create a tree node with an item
(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)

接下来让我们向树中添加一个子节点 - 它将获取两个树节点并将第二个树作为第一个树的子节点添加。

; define a function to add a tree node to the tree
(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree)

此函数将返回给定树的第一个子节点 - 它将获取一个树节点并返回该节点的第一个子节点，或者如果该节点没有任何子节点则返回 nil。

; define a function to get first child of the tree
(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)

此函数将返回给定节点的下一个兄弟节点 - 它将树节点作为参数，并返回对下一个兄弟节点的引用，或者如果该节点没有任何兄弟节点则返回 nil。

; define a function to get sibling of the tree
(defun next-sibling (tree)
   (cdr tree)
)

最后，我们需要一个函数来返回节点中的信息：

; define a function to get the data of a tree node
(defun data (tree)
   (car (car tree))
)

示例

此示例使用上述功能：

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

main.lisp

; define a function to create a tree
(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)
; create a function first child of a tree
(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)
; define a function to get sibling of a tree node
(defun next-sibling (tree)
   (cdr tree)
)
; define a function to get details from a tree node
(defun data (tree)
   (car (car tree))
)
; define a function to add a child to a tree node
(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree
)
; set a tree
(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
; create a tree and assign to mytree
(setq mytree (make-tree 10))

; print detail stored in a tree node
(write (data mytree))
; terminate printing
(terpri)
; print first child of tree
(write (first-child tr))
; terminate printing
(terpri)
; add a child to tree
(setq newtree (add-child tr mytree))
; terminate printing
(terpri)
; print tree
(write newtree)

输出

执行代码时，它会返回以下结果：

10
(2 (3 4 5) ((7 8) (7 8 9)))

((1 2 (3 4 5) ((7 8) (7 8 9)) (10)))

打印页面