LISP - Drzewo

Możesz budować drzewiaste struktury danych z komórek wad, jako listy list.

Aby zaimplementować struktury drzewiaste, będziesz musiał zaprojektować funkcje, które będą przechodzić przez komórki wad w określonej kolejności, na przykład zamówienie przed, w kolejności i po zamówieniu dla drzew binarnych.

Drzewo jako lista list

Rozważmy strukturę drzewa złożoną z komórek wad, które tworzą następującą listę list -

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

Schematycznie można to wyrazić jako -

Funkcje drzewa w LISP

Chociaż przeważnie będziesz musiał napisać własne funkcje drzewa zgodnie z twoimi konkretnymi potrzebami, LISP zapewnia kilka funkcji drzewa, których możesz użyć.

Oprócz wszystkich funkcji list, następujące funkcje działają szczególnie na strukturach drzewiastych -

Sr.No.	Opis funkcji
1	copy-tree x i opcjonalnie vecp Zwraca kopię drzewa komórek wad x. Rekurencyjnie kopiuje kierunki samochodu i cdr. Jeśli x nie jest komórką wad, funkcja po prostu zwraca x niezmienione. Jeśli opcjonalny argument vecp ma wartość true, ta funkcja kopiuje wektory (rekurencyjnie), a także komórki wad.
2	tree-equal xy & klucz: test: test-not: klucz Porównuje dwa drzewa komórek wad. Jeśli x i y są komórkami wad, ich samochody i cdrs są porównywane rekurencyjnie. Jeśli ani x, ani y nie są komórką wad, są porównywane przez eql lub zgodnie z określonym testem. Funkcja: key, jeśli została określona, ​​jest stosowana do elementów obu drzew.
3	subst nowe stare drzewo i klucz: test: test-not: key Zastępuje wystąpienia danej starej pozycji nową pozycją w drzewie , które jest drzewem komórek wad.
4	nsubst nowe stare drzewo i klucz: test: test-not: key Działa tak samo jak subst, ale niszczy oryginalne drzewo.
5	sublis drzewo alist & key: test: test-not: key Działa jak subst, z tą różnicą, że pobiera listę skojarzeń starych-nowych par. Każdy element drzewka (po zastosowaniu funkcji: key, jeśli występuje) jest porównywany z samochodami alist; jeśli pasuje, jest zastępowany przez odpowiedni plik cdr.
6	nsublis drzewo alist & key: test: test-not: key Działa tak samo jak sublis, ale w wersji destrukcyjnej.

Przykład 1

Utwórz nowy plik kodu źródłowego o nazwie main.lisp i wpisz w nim następujący kod.

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

Po wykonaniu kodu zwraca następujący wynik -

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

Przykład 2

Utwórz nowy plik kodu źródłowego o nazwie main.lisp i wpisz w nim następujący kod.

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

Po wykonaniu kodu zwraca następujący wynik -

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

Budowanie własnego drzewa

Spróbujmy zbudować własne drzewo, korzystając z funkcji list dostępnych w LISP-ie.

Najpierw utwórzmy nowy węzeł zawierający pewne dane

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

Następnie dodajmy węzeł potomny do drzewa - zajmie to dwa węzły drzewa i doda drugie drzewo jako dziecko pierwszego.

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

Ta funkcja zwróci pierwsze dziecko w danym drzewie - weźmie węzeł drzewa i zwróci pierwsze dziecko tego węzła lub nil, jeśli ten węzeł nie ma żadnego węzła potomnego.

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

Ta funkcja zwróci następny węzeł siostrzany danego węzła - przyjmuje węzeł drzewa jako argument i zwraca odniesienie do następnego węzła siostrzanego lub zero, jeśli węzeł nie ma.

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

Na koniec potrzebujemy funkcji zwracającej informacje w węźle -

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

Przykład

W tym przykładzie wykorzystano powyższe funkcje -

Utwórz nowy plik kodu źródłowego o nazwie main.lisp i wpisz w nim następujący kod.

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

Po wykonaniu kodu zwraca następujący wynik -

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

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