LISP-ツリー

リストのリストとして、consセルからツリーデータ構造を構築できます。

ツリー構造を実装するには、consセルを特定の順序でトラバースする機能を設計する必要があります。たとえば、バイナリツリーの場合は、事前順序、順序どおり、事後順序です。

リストのリストとしてのツリー

次のリストのリストを形成するconsセルで構成されるツリー構造を考えてみましょう-

（（1 2）（3 4）（5 6））。

概略的には、次のように表すことができます。

LISPのツリー関数

ほとんどの場合、特定のニーズに応じて独自のツリー関数を作成する必要がありますが、LISPには使用できるツリー関数がいくつか用意されています。

すべてのリスト関数とは別に、次の関数は特にツリー構造で機能します-

シニア番号	機能と説明
1	copy-tree x＆オプションのvecp consセルxのツリーのコピーを返します。車とcdrの両方の方向を再帰的にコピーします。xがconsセルでない場合、関数は単にxを変更せずに返します。オプションのvecp引数がtrueの場合、この関数はベクトルとconsセルを（再帰的に）コピーします。
2	tree-equal xy＆key：test：test-not：key consセルの2つのツリーを比較します。xとyが両方ともconsセルである場合、それらの車とcdrは再帰的に比較されます。xもyもconsセルでない場合、それらはeqlによって、または指定されたテストに従って比較されます。：key関数は、指定されている場合、両方のツリーの要素に適用されます。
3	subst 新しい古いツリーとキー：test：test-not：key これは、と与えられた古いアイテムの出現に代入新アイテム、ツリーコンスセルの木があり、。
4	nsubst 新しい古いツリーとキー：test：test-not：key substと同じように機能しますが、元のツリーを破壊します。
5	sublis alist tree＆key：test：test-not：key これは、新旧のペアの関連付けリストリストを取得することを除いて、substのように機能します。ツリーの各要素（存在する場合は：key関数を適用した後）は、リストの車と比較されます。一致する場合は、対応するcdrに置き換えられます。
6	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)
)

次に、子ノードをツリーに追加しましょう。2つのツリーノードを取り、2番目のツリーを最初のツリーの子として追加します。

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