Estudo de Árvores Binárias e Algoritmos de Busca

1) O que é uma Árvore?

É uma estrutura composta por um conjunto de nós.

2) O que é Árvore Binária?

É uma árvore na qual cada nó tem zero, um ou dois filhos (não mais que dois) e só pode ter um único pai.

3) Qual a propriedade fundamental de todas as árvores?

É que só existe um caminho da raiz para qualquer nó.

4) O que é altura?

É o comprimento do caminho mais longo da raiz até uma das folhas.

5) O que é Árvore Binária de Pesquisa?

É um tipo de árvore onde os registros com chaves menores que a raiz estão na subárvore da esquerda e os registros com chaves maiores que a raiz estão na subárvore direita.

6) Faça a Implementação da Função do Antecessor do Nó

int antecessor(ArvBin *subArvEsq) {
  if (arvoreVazia(direita(subArvEsq))) {
    return raiz(subArvEsq);
  } else {
    return antecessor(direita(subArvEsq));
  }
}

7) Faça a Implementação da Função de Pesquisa de um elemento na árvore

ArvBin* pesquisar(ArvBin* arvore, int elem) {
  if (arvoreVazia(arvore)) {
    return NULL;
  }
  if (elem < raiz(arvore)) {
    return pesquisar(arvore->esquerda, elem);
  } else if (elem > raiz(arvore)) {
    return pesquisar(arvore->direita, elem);
  } else {
    return arvore;
  }
}

8) Faça a Implementação da Função para percorrer a árvore através da Ordem, Pós-Ordem e Pré-Ordem

ORDEM:

void imprimirEmOrdem(ArvBin* arvore) {
  if (arvore != NULL) {
    imprimirEmOrdem(arvore->esquerda);
    printf("%d", raiz(arvore));
    imprimirEmOrdem(arvore->direita);
  }
}

9) Escreva uma Função que calcule o número de nós de uma Árvore

int quantNos(ArvBin* arvore) {
  if (arvore == NULL) {
    return 0;
  } else {
    return quantNos(direita(arvore)) + quantNos(esquerda(arvore)) + 1;
  }
}

10) Escreva uma Função que encontre o menor valor da árvore

int menor(ArvBin* arvore) {
  if (esquerda(arvore) != NULL && raiz(esquerda(arvore)) < raiz(arvore)) {
    return menor(esquerda(arvore));
  } else {
    return raiz(arvore);
  }
}

11) Quais são os dois tipos de busca quando a árvore não é binária de pesquisa e não é ordenada?

• Busca em Largura: A busca em largura inicia pela raiz e explora primeiro todos os nós vizinhos do mesmo nível até atingir a última folha.
• Busca em Profundidade: A busca em profundidade também inicia pela raiz e explora a árvore até chegar a uma folha. Se o elemento não for encontrado, faz um backtrack e segue em direção a outra folha não visitada.

12) Desenvolva o algoritmo da Busca em Largura

1. Insere na fila o nó raiz;
2. Remover o elemento da fila e analisar;
3. Se achar o elemento;
4. Finaliza a busca;
5. Se não, insere na fila todos os filhos do nó;
6. Se a fila estiver vazia;
7. Finaliza o algoritmo;
8. Se não, volta para o passo 2.

13) Desenvolva o algoritmo da Busca em Profundidade

1. Insere na pilha o nó raiz;
2. Remove o nó e analisa;
3. Se encontrar o elemento;
4. Finaliza a busca;
5. Se não, insere todos os filhos do elemento na pilha;
6. Se a pilha estiver vazia;
7. Finaliza o algoritmo;
8. Se não, volta para o passo 2.

14) O que é Árvore AVL?

Árvore AVL é uma árvore binária de pesquisa autobalanceada, onde a diferença de altura entre as subárvores é de, no máximo, 1 unidade. Cada inserção e remoção pode requerer um rebalanceamento da árvore, exigindo uma ou mais rotações.

15) Quando uma árvore é dita balanceada?

Quando a diferença entre as alturas das subárvores não é maior do que 1.

16) E quais são as características das operações de rotações?

Uma das características das operações de rotação é preservar a ordem das chaves.