Arvore avl c++

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1024 palavras )
  • Download(s) : 0
  • Publicado : 29 de agosto de 2012
Ler documento completo
Amostra do texto
Lista de Exercícios– Estruturas de Dados 1. Tente construir uma árvore com base nas informações abaixo:  O nodo C tem grau 3.  O nodo X é neto de C e filho de B.  O avô de B é A.  O nodo A tem altura 0 e T tem altura 1.  Os antepassados de P são A,T e K, que são também antepassados de H.  T tem grau 2, e um dos seus filhos é o nodo S.  O nodo G tem 2 sub-árvores que são netos de C.  D éirmão de G, que é uma folha.  E e F tem graus 0 e 1 respectivamente e são também netos do nodo C.  O nodo N tem nível 4.

2.

3.

Implemente uma função que retorne a quantidade de folhas de uma árvore binária. Essa função deve obedecer ao protótipo: int folhas (Arv* a); Implemente uma função que compare se duas árvores binárias são iguais. Essa função deve obedecer ao protótipo: Arv* igual(Arv* a, Arv* b); Escreva uma função que imprima, em-ordem, os conteúdos apenas das folhas de uma árvore binária.

4.

5.

6. 7.

Dada uma árvore binária, encontrar um nó da árvore cujo conteúdo tenha um valor k. Escreva uma função que encontre o primeiro elemento que será impresso da busca em-ordem. Escreva uma função que encontre o ultimo elemento que será impresso da busca pósordem.8.

9.

10. Escreva o procedimento cópia: procedure cópia (t: tree; var c: tree); (* cria uma árvore, c, que é a mesma de t *) 11. Escreva o procedimento espelho: procedure espelho(t: tree; var e: tree); (* cria uma árvore, e, que é a imagem no espelho de t *) 12. Uma árvore binária é denominada estritamente binária quando nenhum dos seus nodos possui apenas uma sub-árvore. Em outraspalavras, cada nodo possui duas sub-árvores ou é um nodo folha. Implemente em C++ uma função que receba um ponteiro T para uma árvore binária e retorne verdadeiro ou falso conforme uma árvore binária seja ou não seja estritamente binária. 13. Escrever um algoritmo que, a partir de uma árvore binária de busca já construída, exiba os seus elementos através das três formas de caminhamento. Para as trêsformas, apresentar os algoritmos recursivos e não-recursivos. Já existe um ponteiro chamado RAIZ que aponta para o elemento que está localizado na raiz da árvore. 14. Dada uma árvore binária de busca, onde cada nodo é constituído pelas seguintes informações: NOME, SEXO ('M' ou 'F'), IDADE e PESO. Sabendo que a árvore foi

construída com a chave NOME e que já existe um ponteiro chamado RAIZ queaponta para o nodo raiz da árvore, construir algoritmos para :
 informar a quantidade de homens e a média de idade das  pesquisar a idade e o peso de uma determinada pessoa.

mulheres;

15. Escreva um algoritmo que encontre o menor e o maior valor armazenados em uma árvore binária de busca já construída. 16. Escreva algoritmos recursivos e não-recursivos para determinar: a. O número de nós emuma árvore binária. b. A soma dos conteúdos de todos os nós em uma árvore binária, considerando que cada nó contém um inteiro. c. A profundidade de uma árvore binária. 17.

18.

19. Escreva um algoritmo para remoção de elementos em árvores binárias de busca. 20. Defina em poucas palavras uma árvore balanceada e qual a finalidade de sua utilização. 21. Partindo de uma árvore AVL vazia, realize ainserção da seguinte sequência de chaves: 99, 44, 71, 80, 74, 63, 59, 120, 98, 150. Redesenhe a árvore a cada inserção. Indique para cada rotação feita, o nome da rotação e o nó desregulado. Indique as árvores resultantes da exclusão dos nós 59 e 63. 22. Considere árvore AVL da figura abaixo.

Desenhe as árvores obtidas após a execuções da sequência das seguintes operções: a. Inserção de 105b. Inserção de 20 c. Remoção de 99 d. Remoção de 36 23. Dada as seguintes árvores binárias abaixo, indique os passos para torná-las uma árvore binária balanceada (AVL).

24. Sem utilizar estruturas auxiliares (pilhas, filas, ...) escreva em C uma função não recursiva para determinar a altura de uma árvore AVL, visitando o menor número de nós possível. Use a estrutura: typedef struct no t_no;...
tracking img