LISP - Ağaç

Ağaç veri yapılarını, liste listeleri olarak eksiler hücrelerinden oluşturabilirsiniz.

Ağaç yapılarını uygulamak için, ikili ağaçlar için ön sipariş, sırayla ve son sipariş gibi belirli bir sırayla eksiler hücrelerinden geçecek işlevler tasarlamanız gerekecektir.

Liste Listesi Olarak Ağaç

Aşağıdaki liste listesini oluşturan eksiler hücresinden oluşan bir ağaç yapısını düşünelim:

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

Şematik olarak şu şekilde ifade edilebilir:

LISP'de Ağaç İşlevleri

Çoğunlukla kendi özel ihtiyaçlarınıza göre kendi ağaç işlevlerinizi yazmanız gerekecek olsa da, LISP kullanabileceğiniz bazı ağaç işlevleri sağlar.

Tüm liste işlevlerinin yanı sıra, aşağıdaki işlevler özellikle ağaç yapılarında çalışır -

Sr.No.	İşlev ve Açıklama
1	copy-tree x ve isteğe bağlı vecp Eksi hücresi ağacının bir kopyasını döndürür x. Hem araba hem de cdr yönlerini özyinelemeli olarak kopyalar. X bir eksiler hücresi değilse, işlev yalnızca x'i değiştirmeden döndürür. İsteğe bağlı vecp argümanı doğruysa, bu işlev vektörleri (özyinelemeli olarak) ve eksi hücreleri kopyalar.
2	tree-equal xy & key: test: test-not: anahtar İki hücre hücresini karşılaştırır. X ve y her ikisi de eks hücreleriyse, arabaları ve cdr'leri özyinelemeli olarak karşılaştırılır. Ne x ne de y bir eksper hücresi değilse, eql ile veya belirtilen teste göre karşılaştırılırlar. : Key işlevi, belirtilirse, her iki ağacın öğelerine de uygulanır.
3	subst yeni eski ağaç ve anahtar: test: test-not: anahtar Bu verilen eski öğenin oluşumlarını yerine yeni öğenin, ağacın eksileri hücrelerin bir ağaç.
4	nsubst yeni eski ağaç ve anahtar: test: test-not: anahtar Subst ile aynı şekilde çalışır, ancak orijinal ağacı yok eder.
5	sublis alist ağacı ve anahtar: test: test-not: anahtar O bir dernek liste alır dışında subst gibi çalışır alist eski yeni çiftlerinin. Ağacın her bir öğesi (varsa: anahtar işlevini uyguladıktan sonra) alist arabaları ile karşılaştırılır; eşleşirse, karşılık gelen cdr ile değiştirilir.
6	nsublis alist ağacı ve anahtar: test: test-not: anahtar Sublis ile aynı şekilde çalışır, ancak yıkıcı bir versiyondur.

örnek 1

Main.lisp adlı yeni bir kaynak kod dosyası oluşturun ve içine aşağıdaki kodu yazın.

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

Kodu çalıştırdığınızda, aşağıdaki sonucu döndürür -

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

Örnek 2

Main.lisp adlı yeni bir kaynak kod dosyası oluşturun ve içine aşağıdaki kodu yazın.

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

Kodu çalıştırdığınızda, aşağıdaki sonucu döndürür -

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

Kendi Ağacınızı Oluşturmak

LISP'de bulunan liste işlevlerini kullanarak kendi ağacımızı oluşturmaya çalışalım.

Önce bazı verileri içeren yeni bir düğüm oluşturalım

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

Sonra ağaca bir çocuk düğüm ekleyelim - bu iki ağaç düğümü alacak ve ikinci ağacı ilkinin çocuğu olarak ekleyecektir.

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

Bu işlev, belirli bir ağacın ilk çocuğunu döndürür - bir ağaç düğümünü alır ve bu düğümün herhangi bir alt düğümü yoksa, bu düğümün ilk çocuğunu veya nil'i döndürür.

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

Bu işlev, belirli bir düğümün sonraki kardeşini döndürecektir - argüman olarak bir ağaç düğümünü alır ve düğümde hiç yoksa sonraki kardeş düğüme veya nil'e bir başvuru döndürür.

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

Son olarak, bilgiyi bir düğümde döndürmek için bir işleve ihtiyacımız var -

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

Misal

Bu örnek, yukarıdaki işlevleri kullanır -

Main.lisp adlı yeni bir kaynak kod dosyası oluşturun ve içine aşağıdaki kodu yazın.

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

Kodu çalıştırdığınızda, aşağıdaki sonucu döndürür -

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

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