LISP - Pohon

Anda bisa membangun struktur data pohon dari sel kontra, sebagai daftar daftar.

Untuk mengimplementasikan struktur pohon, Anda harus mendesain fungsionalitas yang akan melintasi sel kontra, dalam urutan tertentu, misalnya, pre-order, in-order, dan post-order untuk pohon biner.

Pohon sebagai Daftar Daftar

Mari kita pertimbangkan struktur pohon yang terdiri dari sel kontra yang membentuk daftar daftar berikut -

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

Secara diagram, ini dapat dinyatakan sebagai -

Fungsi Pohon di LISP

Meskipun sebagian besar Anda perlu menulis fungsi pohon Anda sendiri sesuai dengan kebutuhan spesifik Anda, LISP menyediakan beberapa fungsi pohon yang dapat Anda gunakan.

Terlepas dari semua fungsi daftar, fungsi berikut bekerja terutama pada struktur pohon -

Sr.No.	Deskripsi fungsi
1	copy-tree x & vecp opsional Ini mengembalikan salinan pohon sel kontra x. Itu secara rekursif menyalin baik arah mobil dan cdr. Jika x bukan sel kontra, fungsinya hanya mengembalikan x tidak berubah. Jika argumen vecp opsional benar, fungsi ini menyalin vektor (secara rekursif) serta sel kontra.
2	tree-equal xy & key: test: test-not: key Ini membandingkan dua pohon sel kontra. Jika x dan y keduanya sel kontra, mobil dan cdr mereka akan dibandingkan secara rekursif. Jika x maupun y bukan sel kontra, mereka akan dibandingkan dengan persamaan, atau menurut pengujian yang ditentukan. Fungsi: key, jika ditentukan, diterapkan ke elemen dari kedua pohon.
3	subst pohon & kunci lama baru: test: test-not: key Ini menggantikan kemunculan item lama yang diberikan dengan item baru , dalam pohon , yang merupakan pohon sel kontra.
4	nsubst pohon & kunci lama baru: test: test-not: key Ia bekerja sama dengan subst, tetapi menghancurkan pohon aslinya.
5	sublis pohon alist & key: test: test-not: key Ia bekerja seperti subst, kecuali bahwa dibutuhkan sebuah asosiasi daftar alist pasangan tua-baru. Setiap elemen pohon (setelah menerapkan fungsi: key, jika ada), dibandingkan dengan mobil-mobil alist; jika cocok, itu diganti dengan cdr yang sesuai.
6	nsublis pohon alist & key: test: test-not: key Ia bekerja sama dengan sublis, tetapi versi yang merusak.

Contoh 1

Buat file kode sumber baru bernama main.lisp dan ketikkan kode berikut di dalamnya.

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

Saat Anda menjalankan kode, ia mengembalikan hasil berikut -

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

Contoh 2

Buat file kode sumber baru bernama main.lisp dan ketikkan kode berikut di dalamnya.

(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(write tr)
(setq trs (subst 7 1 tr))
(terpri)
(write trs)

Saat Anda menjalankan kode, ia mengembalikan hasil berikut -

((1 2 (3 4 5) ((7 8) (7 8 9))))
((7 2 (3 4 5) ((7 8) (7 8 9))))

Membangun Pohon Anda Sendiri

Mari kita coba membangun pohon kita sendiri, menggunakan fungsi daftar yang tersedia di LISP.

Pertama mari kita buat node baru yang berisi beberapa data

(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)

Selanjutnya mari kita tambahkan simpul anak ke dalam pohon - ini akan mengambil dua simpul pohon dan menambahkan pohon kedua sebagai anak dari yang pertama.

(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree)

Fungsi ini akan mengembalikan anak pertama dari pohon yang diberikan - ini akan mengambil simpul pohon dan mengembalikan anak pertama dari simpul itu, atau nihil, jika simpul ini tidak memiliki simpul anak.

(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)

Fungsi ini akan mengembalikan saudara berikutnya dari simpul yang diberikan - ini mengambil simpul pohon sebagai argumen, dan mengembalikan referensi ke simpul saudara berikutnya, atau nil, jika simpul tidak memilikinya.

(defun next-sibling (tree)
   (cdr tree)
)

Terakhir kita membutuhkan fungsi untuk mengembalikan informasi dalam sebuah node -

(defun data (tree)
   (car (car tree))
)

Contoh

Contoh ini menggunakan fungsi di atas -

Buat file kode sumber baru bernama main.lisp dan ketikkan kode berikut di dalamnya.

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

Saat Anda menjalankan kode, ia mengembalikan hasil berikut -

10
(2 (3 4 5) ((7 8) (7 8 9)))

((1 2 (3 4 5) ((7 8) (7 8 9)) (10)))