LISP - 樹

可以從cons單元構建樹的數據結構，如清單列表。

爲了實現樹形結構，則必須設計功能，將遍歷cons 單元，在特定的順序，例如，前序，順序和後序的二進制樹。

樹列表的列表

讓我們考慮由cons單元的樹狀結構，形成列出的清單如下：

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

圖解，它可以表示爲：

LISP樹的功能

雖然多數時候仍需要根據其它特殊需求編寫自己的樹的功能，LISP提供了一些樹的功能，您可以使用。

除了所有列表函數，以下是工作在樹結構函數：

函數

描述

copy-tree x &optional vecp

它返回cons單元×樹的副本。它遞歸地拷貝兩款車和cdr方向。如果x不是一個cons單元，該函數只返回x不變。如果可選vecp參數爲true，這個函數將向量（遞歸），以及cons單元。

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

它比較兩棵樹的cons單元。如果x和y是兩個cons單元，他們的汽車和cdr是遞歸比較。如果x和y都不是一個cons單元，它們是由eql比較，或根據指定的測試。:key函數，如果指定，應用到這兩個目錄樹中的元素。

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

它可以代替出現給老項與新項，在樹，這是cons單元的一棵樹。

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

它的工作原理與subst相同，但它破壞了原來的樹。

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

它的工作原理就像subst，只不過它採用的新舊對關聯表alist。樹（應用後:key函數，如果有的話）中的每個元素，與alist的車相比;如果它匹配，它被替換爲相應的cdr。

nsublis alist tree &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)))