1) Crie uma árvore binária para armazenar a seguinte expressão aritmética: (14 – (12 -25) * (32-47) % 6 ). A prioridade entre os operadores deve ser respeitada.
2) Crie três funções de busca em árvore binária de busca que:
a) encontre uma chave K, percorrendo a árvore em pré-ordem;
b) encontre uma chave K, percorrendo a árvore em ordem;
c) encontre uma chave K, percorrendo a árvore em pós-ordem.
Para cada uma das funções, imprimir os nós percorridos.
3) Escreva o resultado da execução da aplicação das funções do exercício (2) para a árvore abaixo, seguindo os critérios:
a) chave 30, função (a)
b) chave 35, função (b)
c) chave 25, função (c)
– 20
– / \
– 10 30
– / \
– 25 35
– / \
– 21 27
4) Implemente uma função que some os elementos pares de uma árvore binária de busca.
5) Implementar uma função que, dada uma chave K, busque o seu elemento sucessor. Usar método iterativo.
6) Explique a diferença entre o método de balanceamento de uma árvore AVL e uma árvore rubro-negra. Existe uma das duas em que o fator de balanceamento é menor (árvore mais balanceada)?
7) Dada a árvore abaixo:
a) Descreva o fator de balanceamento de cada nó.
b) Insira o elemento 8 na raiz, e mostre as árvores resultantes após cada rotação, até o resultado final.
c) Explique como podemos adaptar de maneira simples o algoritmo de inserção em árvore binária de busca para suportar inserção na raiz.
– 40
– / \
– 10 50
– / \
– 09 18
– / \
– 15 20
8) Como modificar a função de rotação à esquerda abaixo para suportar um ponteiro para o nó pai?
– tNo rotEsq( tNo no ){
– tNo aux;
– aux = no->dir;
– no->dir = aux->esq;
– aux->esq = no;
– return aux;
}
9) Explique quais são as propriedades de uma árvore para ser uma árvore 2-3-4.
10) O código abaixo foi projetado para buscar chaves em uma árvore 2-3-4. Porém, ele contém um problema. Explique qual é o problema e como corrigi-lo.
tNo busca (tNo *no, int chave) {
– if( no != NULL ){
– for( i=0; i < no.tam; i++)
– if( no.chave[i] == chave )
– return no;
– else if( chave < no.chave[i] )
– return busca( no.p [i], chave );
– return no;
– }
}
11) Porque usar a técnica de inclusão na folha é vantajosa em árvores 2-3-4?
12) Dada a árvore 2-3-4, represente uma árvore rubro-negra equivalente.
———– 25
——– / \
—20-22-24 26 – 27
13) Crie uma árvore rubro-negra incluindo os seguintes elementos, nesta ordem: 10, 2, 3, 12, 11. Mostrar as árvores resultantes após cada inserção.
14) A altura mínima de uma árvore é o número de nós pretos a partir da raiz. Implemente um algoritmo que calcule a altura mínima de uma árvore rubro-negra.
15) Dada a árvore rubro negra abaixo:
a) exclua o 16.
– 16
– <b>
– / \
– 12 18
– <b> <b>
– / / \
– 11 17 22
– <b> <b> <r>
– / \
– 20 25
– <b> <b>