Lisp教學 » LISP - 樹

LISP - 樹

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

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

樹列表的列表

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

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

圖解，它可以表示為：

treestructure

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