LISP - 树(Tree)

您可以从cons单元构建树数据结构，作为列表列表，如，二叉树的预顺序，顺序和后顺序。

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

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

以图表形式，它可以表示为-

Tree函数

尽管大多数情况下，您将需要根据特定需要编写自己的树函数，但是LISP提供了一些可以使用的树函数。

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

Tree - 示例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))

Tree - 示例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))))

创建Tree树

让我们尝试使用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))
)

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