Lisp-tree

LISP-ツリー

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

ツリー構造を実装するには、コンスセルを特定の順序（たとえば、バイナリツリーの事前順序、順序、および順序）を横断する機能を設計する必要があります。

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

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

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

概略的に、それは次のように表現できます-

ツリー構造

LISPのツリー関数

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

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

Sr.No.	Function & Description
1	copy-tree *x & optional vecp コンスセルxのツリーのコピーを返します。 車とcdrの両方の方向を再帰的にコピーします。 xがコンスセルでない場合、関数は単にxを変更せずに返します。 オプションのvecp引数がtrueの場合、この関数はコンスセルと同様にベクトルを（再帰的に）コピーします。
2	tree-equal *x y & key :test :test-not :key コンスセルの2つのツリーを比較します。 xとyが両方ともコンスセルの場合、車とCDRが再帰的に比較されます。 xもyもコンスセルでない場合、それらはeqlによって、または指定されたテストに従って比較されます。 ：key関数が指定されている場合、両方のツリーの要素に適用されます。
3	subst *new old tree & key :test :test-not :key 指定された古いアイテムのオカレンスを、コンスセルのツリーである_tree_の_new_アイテムに置き換えます。
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と同じように機能しますが、破壊的なバージョンです。

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