上一节:
下一节:

  LISP - 树（Tree）

  • 简述

    您可以从 cons 单元构建树数据结构，作为列表的列表。
    要实现树结构，您必须设计以特定顺序遍历 cons 单元的功能，例如，二叉树的前序、中序和后序。

  • 树作为列表的列表

    让我们考虑一个由构成以下列表列表的 cons 单元组成的树结构 -
    ((1 2) (3 4) (5 6)).
    在图表上，它可以表示为 -
    树结构

  • LISP 中的树函数

    虽然大多数情况下您需要根据您的特定需要编写自己的树函数，但 LISP 提供了一些您可以使用的树函数。
    除了所有列表函数外，以下函数特别适用于树结构 -
    序号 功能说明
    1
    copy-treex 和可选的 vecp
    它返回 cons 单元树 x 的副本。它递归地复制汽车和 cdr 方向。如果 x 不是一个 cons 单元格，函数简单地返回 x 不变。如果可选的 vecp 参数为 true，则此函数会（递归地）复制向量以及 cons 单元格。
    2
    tree-equalxy & key :test :test-not :key
    它比较了两棵 cons 单元树。如果 x 和 y 都是 cons 单元，则递归比较它们的 cars 和 cdrs。如果 x 和 y 都不是 cons 单元格，则它们通过 eql 进行比较，或根据指定的测试进行比较。:key 函数（如果指定）将应用于两棵树的元素。
    3
    subst新旧树 & 键 :test :test-not :key
    它用新项目替换给定旧项目的出现，在tree中，这是一棵 cons 单元树。
    4
    nsubst新旧树 & 键 :test :test-not :key
    它的工作原理与 subst 相同，但它会破坏原始树。
    5
    sublisalist 树 & key :test :test-not :key
    它像 subst 一样工作，除了它接受一个 新旧对的关联列表。树的每个元素（在应用 :key 函数之后，如果有的话）都与列表中的汽车进行比较；如果匹配，则替换为相应的 cdr。
    6
    nsublisalist 树 & 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)))
上一节:
下一节: