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

列印頁面