Lista Árvores Binárias

Prévia do material em texto

LISTA Árvores Genéricas
Estruturas de Dados II
Prof. Murilo Ybanez
Desenhe uma árvore binária com os valores 1 a 17 e a menor altura possível. Repita com a maior altura possível.
Qual o resultado da impressão dos elementos da árvore binária abaixo a partir de caminhamentos em pré-ordem, in-ordem e pós-ordem?
Forneça um algoritmo que determina se uma árvore binária qualquer contendo valores inteiros é uma árvore de pesquisa binária, assumindo uma estrutura baseada em ponteiros. 
Tendo como base a árvore abaixo, desenhe a nova árvore que será obtida após a realização das seguintes operações: inserir 21, 46 e 44; remover 38 e 47; inserir 48.
Considere as seguintes definições de ordens de percurso de uma árvore binária: (POSCOMP)
Ordem A:
se a árvore binária não for vazia, então:
{
visitar a raiz;
percorrer a sub-árvore esquerda em Ordem B;
percorrer a sub-árvore direita em Ordem B;
}
Ordem B:
se a árvore binária não for vazia, então:
{
visitar a raiz;
percorrer a sub-árvore direita em Ordem A;
percorrer a sub-árvore esquerda em Ordem A;
}
Considere agora a seguinte árvore binária:
O percurso d árvore binária apresentada em Ordem A resulta em qual seqüência de visitas? (POSCOMP)
A B D C E K L M F I J G H
A B C D E F G H I J K L M
A B D C E K L M F G H I J
A B E C D F K G I L M H J
A B D C E F I J G H K L M
Mostre qual é a representação implícita (em array) de cada uma das seguintes árvores binárias:
 
Em uma estrutura de árvore binária de busca, foram inseridos os elementos “h”, “a”, “b”, “c”, “i”, “j”, nesta seqüência. Qual o tamanho do maior caminho na árvore, após a inserção dos dados acima? (POSCOMP)
2
6
4
5
3
Forneça os algoritmos de busca, inserção e remoção em um árvore de pesquisa binária.
Elabore um algoritmo que imprime o caminho percorrido dentro de uma árvore de pesquisa binária durante a busca de um determinado elemento (passado como argumento).
Usando árvores de pesquisa binárias que guardam números inteiros, forneça os algoritmos abaixo:
Eliminação de todos os elementos menores que x (mostre os elementos)
Eliminação de todos os elementos da árvore (devolva a sequência de remoções)
A operação de remoção em uma árvore binária de busca é comutativa? Justifique sua resposta. (Dica: uma operação comutativa garantiria que remover x e depois y ou remover y e depois x geraria a mesma árvore)
Escreva um algoritmo que receba o ponteiro de um nó n de uma árvore binária e imprima os valores dos nós sucessor e predecessor de n, assumindo um caminhamento em in-ordem.
Assumindo uma representação de árvore binária que inclua um ponteiro para o pai do nó, escreva um algoritmo que preencha corretamente os valores de todos os campos pai de uma árvore já montada apenas com os campos esq e dir preenchidos.
A profundidade de um nó n em uma árvore binária com raiz r é a distância entre n e r. Mais precisamente, a profundidade de n é o comprimento do (único) caminho que vai de r até n. Por exemplo, a profundidade de r é 0 e a profundidade de r->esq é 1. Escreva um algoritmo que determine a profundidade de um nó em relação à raiz da árvore.
Forneça um algoritmo que imprima os conteúdos de uma árvore binária com recuos de margem proporcionais à profundidade do nó na árvore. Por exemplo, a árvore
	 555
 / \ 
 
 333 888 
 / \ \ 
 111 444 999
 deve se representada assim: 
 555
 333
 111
 -
 -
 444
 -
 -
 888
 -
 999
 -
 -
 onde os caracteres '-' representam NULL.
Escreva um algoritmo não recursivo para calcular a altura de uma árvore binária.