Revisão
IF672 - Algoritmos e Estruturas de
Dados CIn - UFPE
Allan Jefferson Silva de Souza
Artur Lira dos Santos
Diêgo João Costa Santiago
Diego Lemos de Almeida Melo
Eliaquim Lima Sá Neto
Jerônimo Barbosa da Costa Júnior
Lucas Silva Figueiredo
Pablo Carvalho Pinheiro
Tiago Lins Falcão
Vinicius Alexandre Kursancew
{ajss, als3, djcs, dlam, elsn, jbcj, lsf, pcp, tlf, vak}@cin.ufpe.br
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Índice
1. Elabore um algoritmo que dada uma fila, retorne como saída
essa fila com a ordem invertida.
2.
Elabore um algoritmo que dada uma árvore, retorne uma
fila dos elementos de um determinado nível k.
3. Elabore um algoritmo que dada uma árvore retorne se ela é
uma árvore AVL.
Obs1.: Cada elemento só pode ser visitado apenas uma vez;
Obs2.: Cada nó aponta apenas para seus filhos;
Obs3.: Inicialmente o balance e a altura de cada nó(elemento) é 0
4. Elabore o algoritmo que dada uma árvore retorne uma lista
ordenada.
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
1.
Elabore um algoritmo que dada uma fila, retorne como
saída essa fila com a ordem invertida.
ALGORITMO INVERTE_FILA
ENTRADAS = fila : Fila
SAÍDAS = fila : Fila
VARIÁVEIS = auxPilha : Pilha, auxElement : Elemento
ENQUANTO fila não estiver vazia FAÇA
auxElement := remover (fila)
inserir (auxPilha, auxElement)
FIM-ENQUANTO
ENQUANTO auxPilha não estiver vazia FAÇA
auxElement := remover (auxPilha)
inserir (fila, auxElement)
FIM-ENQUANTO
FIM-ALGORITMO
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
2.
Elabore um algoritmo que dada uma árvore, retorne uma
fila dos elementos de um determinado nível k.
ALGORITMO NIVEL
ENTRADAS = arvore : Arvore, k : Inteiro
SAÍDAS = lista : Lista
VARIÁVEIS = auxLista : Lista
inserir (auxLista, raiz(arvore))
lista := NIVEL_AUX (auxLista, k, 0)
FIM-ALGORITMO
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
2.
Elabore um algoritmo que dada uma árvore, retorne uma
fila dos elementos de um determinado nível k.
ALGORITMO NIVEL_AUX
ENTRADAS = inLista : Lista, k : Inteiro, atualK : Inteiro
SAÍDAS = outLista : Lista
VARIÁVEIS = auxLista : Lista
SE k = atualK ENTÃO outLista := inLista
SENÃO
auxElement := head (inLista)
ENQUANTO auxElement ≠ NIL FAÇA
inserir (auxLista, esquerda(element))
inserir (auxLista, direita(element))
auxElement = prox(auxElement)
FIM-ENQUANTO
outLista = NIVEL_AUX (auxLista, k, atualK+1)
FIM-SE
FIM-ALGORITMO
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
3.
Elabore um algoritmo que dada uma árvore retorne se ela
é uma árvore AVL.
ALGORITMO AVL
ENTRADAS = arvore : Arvore
SAÍDAS = avl : Booleano
avl := AVL_AUX (raiz(arvore))
FIM-ALGORITMO
ALGORITMO AVL_AUX
ENTRADAS = element : Elemento
SAÍDAS = avl : Booleano
avl := AVL_AUX (esquerda(element)) E AVL_AUX (direita(element))
E absoluto(altura(direita(element))-altura(esquerda(element)))≼1
setBalance (element, altura(direita(element))altura(esquerda(element)))
setAltura (element, maximo(altura(esquerda(element)),
altura(direita(element)))+1)
FIM-ALGORITMO
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
4.
Elabore o algoritmo que dada uma árvore retorne uma
lista ordenada.
ALGORITMO IN-ORDEM
ENTRADAS = arvore : Arvore
SAÍDAS = fila : Fila
fila : = IN-ORDEM_AUX(raiz(arvore), fila)
FIM-ALGORITMO
ALGORITMO IN-ORDEM_AUX
ENTRADAS = element : Elemento, fila : Fila
SAÍDAS = fila : Fila
SE element ≠ NIL
ENTÃO
fila := IN-ORDEM_AUX(esquerda(element), fila)
inserir (fila, element)
fila := IN-ORDEM_AUX(direita(element), fila)
FIM-SE
FIM-ALGORITMO
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados