MC600 - Segundo semestre de 2003 - LISTA 6
------------------------------------------


As funções a seguir referem-se a operações com árvores binárias 
de busca representadas como listas da seguinte forma: cada nó é
representado por (info esq dir), onde info é a informação (ordenável),
esq e dir são as subárvores esquerda e direita, respectivamente.

Faça funções que

 1. Verifique se uma árvore é vazia.

Resposta:

   (defun vazia (arv)
     (null arv)
   )


 2. Construa uma folha com informação dada.

Resposta:

   (defun cria_folha (info)
     (list info nil nil)
   )


 3. Retorne a informação de um nó dado.

Resposta:

   (defun info (lst)
     (car lst)
   )


 4. Retorne a subárvore esquerda de um nó dado.

Resposta:

   (defun esq (lst)
     (car (cdr lst))
   )


 5. Retorne a subárvore direita de um nó dado.

Resposta:

   (defun dir (lst)
     (car (cdr (cdr lst)))
   )


 6. Busque um elemento dada a chave (info).

Resposta:

(defun busca (info arv)
  (cond
   ((vazia arv) nil)
   ((= info (info arv) arv)
   ((> info (info arv) (busca info (dir arv)))
   (t                  (busca info (esq arv)))
  )
)


 7. Insira um novo elemento (se já não estiver).

Resposta:

(defun insere (chave arvore)
   (cond
      ( (null arvore)         (cria-folha chave) )
      
      ( (< chave (info arvore))
        (list (info arvore) (insere chave (esq arvore)) (dir arvore)) )

      ( (> chave (info arvore))
        (list (info arvore) (esq arvore) (insere chave (dir arvore))) )

      (  t                     arvore )
   )
)

 8. Liste os elementos em pré-ordem.

Resposta:
 
(defun pre (arvore)
  (if (vazia arvore)
      nil
      (progn
        (print (info arvore))
        (pre (esquerda arvore))
        (pre (direita arvore))
      )
  )
)


 9. Liste os elementos em in-ordem.

Resposta:
 
(defun in (arvore)
    (if (vazia arvore)
      nil
      (progn   
        (in (esquerda arvore))
        (print (info arvore))
        (in (direita arvore))
      )
    )
 )


10. Liste os elementos em pós-ordem.

Resposta:
 
(defun pos (arvore)
  (if (vazia arvore)
      (progn
        (pos (esquerda arvore))
        (pos (direita arvore))
        (print (info arvore))
      )
   )
 )


11. Retorne a altura da árvore.

Resposta:

(defun altura (arvb)
    (if (vazia arvb)
        0
        (max (+ 1 (altura (esq arvb))) (+ 1 (altura (dir arvb))))
    )
)

12. Verifique se a árvore é balanceada.

Resposta:

(defun bal (tree)
  (if (vazia tree)
    t
    (if (> (abs (- (altura (esq tree)) (altura (dir tree)))) 1))
      nil
      (and
         (bal (esq tree))
         (bal (dir tree))
      )
    )
  )
)