LISP - Árvore

Você pode construir estruturas de dados em árvore a partir de células cons, como listas de listas.

Para implementar estruturas de árvore, você terá que projetar funcionalidades que atravessariam as células cons, em ordem específica, por exemplo, pré-ordem, ordem e pós-ordem para árvores binárias.

Árvore como lista de listas

Vamos considerar uma estrutura em árvore composta por células cons que formam a seguinte lista de listas -

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

Diagramaticamente, pode ser expresso como -

Funções de árvore em LISP

Embora na maioria das vezes você precise escrever suas próprias funcionalidades de árvore de acordo com sua necessidade específica, o LISP fornece algumas funções de árvore que você pode usar.

Além de todas as funções de lista, as seguintes funções funcionam especialmente em estruturas de árvore -

Sr. Não.	Descrição da função
1	copy-tree x e vecp opcional Ele retorna uma cópia da árvore de células cons x. Ele copia recursivamente as direções do carro e do cdr. Se x não for uma célula cons, a função simplesmente retorna x inalterado. Se o argumento opcional vecp for verdadeiro, esta função copia vetores (recursivamente), bem como células cons.
2	tree-equal xy & chave: teste: não teste: chave Ele compara duas árvores de células cons. Se xey são células cons, seus carros e cdrs são comparados recursivamente. Se nem x nem y forem células cons, são comparados pelo eql ou de acordo com o teste especificado. A função: key, se especificada, é aplicada aos elementos de ambas as árvores.
3	subst nova árvore antiga e chave: teste: não teste: chave Substitui as ocorrências de determinado item antigo por novo item, na árvore , que é uma árvore de células cons.
4	nsubst nova árvore antiga e chave: teste: não teste: chave Funciona da mesma forma que subst, mas destrói a árvore original.
5	sublis árvore de lista e chave: teste: não teste: chave Ele funciona como subst, exceto que ele leva uma lista de associação alist de pares novo old-. Cada elemento da árvore (após aplicar a função: key, se houver), é comparado com os carros de alist; se for igual, ele será substituído pelo cdr correspondente.
6	nsublis árvore de lista e chave: teste: não teste: chave Funciona como sublis, mas é uma versão destrutiva.

Exemplo 1

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

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

Quando você executa o código, ele retorna o seguinte resultado -

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

Exemplo 2

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

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

Quando você executa o código, ele retorna o seguinte resultado -

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

Construindo sua própria árvore

Vamos tentar construir nossa própria árvore, usando as funções de lista disponíveis no LISP.

Primeiro, vamos criar um novo nó que contém alguns dados

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

Em seguida, vamos adicionar um nó filho à árvore - ele pegará dois nós da árvore e adicionará a segunda árvore como filho do primeiro.

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

Esta função retornará o primeiro filho de uma determinada árvore - pegará um nó da árvore e retornará o primeiro filho desse nó, ou nil, se este nó não tiver nenhum nó filho.

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

Esta função irá retornar o próximo irmão de um determinado nó - ela pega um nó da árvore como argumento e retorna uma referência ao próximo nó irmão, ou nil, se o nó não tiver nenhum.

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

Por último, precisamos de uma função para retornar as informações em um nó -

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

Exemplo

Este exemplo usa as funcionalidades acima -

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

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

Quando você executa o código, ele retorna o seguinte resultado -

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

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