cenas

´
Arvores
em Haskell

´
Arvores
Linguagem Haskell
Maria Adriana Vidigal de Lima
˜ - UFU
Faculdade de Computac¸ao
Dezembro - 2009

Maria Adriana Vidigal de Lima

´
Arvores

´
Arvores
em Haskell

1

´
Arvores
em Haskell
´
˜ sobre Arvores
Noc¸oes
´
´
Arvore
Binaria
de Busca
´
´
´
Arvore
Binaria
Generica

Maria Adriana Vidigal de Lima

´
Arvores

´
Arvores
em Haskell

´
˜
Noc¸oes sobre Arvores
´
´
Arvore
Binaria de Busca
´
´
´
Arvore
Binaria
Generica

Fundamentos
´
Uma arvore e´ uma estrutura de dados baseada em listas encadeadas, que possuem um elemento superior, definido
´
como a raiz da arvore.
´ denominados nos
´ filhos.
O no´ raiz aponta para outros nos,
´ abaixo deste.
Cada no´ filho pode ser no´ pai de outros nos
´
Dessa forma, a arvore e´ uma estrutura recursiva.
˜ um tipo especial de arvore
´
ˆ
´
´
As arvores binarias sao e tem
˜ limitado em dois. Assim, qualquer o fator de ramificac¸ao
´
´
´
´ filhos. no´ da arvore binaria tem no maximo dois nos

Maria Adriana Vidigal de Lima

´
Arvores

´
Arvores
em Haskell

´
˜
Noc¸oes sobre Arvores
´
´
Arvore
Binaria de Busca
´
´
´
Arvore
Binaria
Generica

´
´
Exemplo de Arvore
Binaria
´
´
Uma arvore binaria e´ uma estrutura de dados caracterizada por:
˜ possui elementos (arvore
´
Nao vazia). Possui um elemento distinto (raiz), com dois ponteiros para as
´
´ sub-arvore esquerda e sub-arvore direita. Maria Adriana Vidigal de Lima

´
Arvores

´
Arvores
em Haskell

´
˜
Noc¸oes sobre Arvores
´
´
Arvore
Binaria de Busca
´
´
´
Arvore
Binaria
Generica

´
´
Arvore
Binaria
em Haskell
˜ de dados para uma arvore
´
´
A definic¸ao binaria em Haskell considerando o armazenamento de numeros inteiros pode ser:
´
data ArvoreBinInt = Nulo |
No Int ArvoreBinInt ArvoreBinInt deriving Show
´
´
A arvore binaria da figura e´ descrita por: arvEx = (No