Considere
as
seguintes
declarações
(NodoABP
e
PNodoABP),
adaptadas
dos
apontamentos:
struct NodoArv {
int Elemento;
struct NodoArv *Esquerda;
struct NodoArv *Direita;
};
typedef struct NodoArv *PNodoArv;
Copiar para o ficheiro “ArvoreBinariaPesquisa.h” e adaptar as funções associadas às
operações sobre árvores binárias de pesquisa que constam nos apontamentos.
1) Implementar uma função para construir uma ABP T com valores inteiros positivos,
inseridos a partir do teclado, usando a função InserirABP (consta dos apontamentos).
PNodoArv ConstruirArvoreABP () {
int X;
PNodoArv T;
T = CriarArvore();
printf(“Inserir um inteiro positivo não nulo (negativo para terminar): \n”);
scanf(“%d”, &X);
while (X > 0) {
T = InserirABP(X, T);
printf(“Inserir um inteiro positivo (negativo para terminar): \n”);
}
scanf(“%d”, &X);
return T;
}
2) ...
3) Usando a definição de ABP de inteiros em cima, implemente uma função que dada
uma ABP T, determine o maior elemento de T.
Nota: o maior elemento encontra-se no nodo mais à direita da árvore (não vazia).
int MaiorElementoABP (PNodoArv T) {
if (T->Direita == NULL)
return T->Elemento;
return MaiorElementoABP(T->Direita);
}
4) Usando a definição de ABP de inteiros em cima, implemente uma função que dada
uma ABP T, determine o menor elemento de T.
Nota: o menor elemento encontra-se no nodo mais à esquerda da árvore (não vazia).
int MenorElementoABP (PNodoArv T) {
if (T->Esquerda == NULL)
return T->Elemento;
return MenorElementoABP(T->Esquerda);
}
Programa principal:
#include <stdio.h>
#include <stdlib.h>
#include “ArvoreBinariaPesquisa.h” // deve estar na diretoria/pasta do main
main () {
PNodoABP T;
int maior, menor;
T = ConstruirArvoreABP();
ListarPorNiveis(T);
maior = MaiorElementoABP(T);
menor = MenorElementoABP(T);
printf(“Maior e menor elementos são: %d, %d\n”, maior, menor);
}
5) Usando a definição de ABP de inteiros em cima, implemente uma função que dada
uma ABP T, determine a soma dos elementos de T superiores a uma dada chave K.
int SomaElementosMaioresK (PNodoArv T, int K) {
int se, sd;
if (T == NULL)
return 0;
if (T->Elemento > K) {
se = SomaElementosMaioresK(T->Esquerda, K);
sd = SomaElementosMaioresK(T->Direita, K);
return (T->Elemento + se + sd);
}
else {
sd = SomaElementosMaioresK(T->Direita, K);
}
}
return sd;
Programa principal:
#include <stdio.h>
#include <stdlib.h>
#include “ArvoreBinariaPesquisa.h” // deve estar na diretoria/pasta do main
main () {
PNodoArv T;
int Num, soma, k;
T = ConstruirArvoreABP();
ListarPorNivel(T);
maior = MaiorElementoABP(T);
menor = MenorElementoABP(T);
printf(“Maior e menor elementos são: %d, %d\n”, maior, menor);
printf(“Insira um valor inteiro: “);
scanf(“%d”, &k);
soma = SomaElementosMaioresK(T, k);
printf(“Soma dos elementos maiores que %d: %d\n”, k, soma);
}
6) Usando a definição de ABP de inteiros em cima, implemente uma função que dada
uma ABP T, determine o número de elementos de T que são superiores a uma dada chave
(valor inteiro) K.
int NumeroElementosMaioresK (PNodoArv T, int K) {
int se, sd;
if (T == NULL)
return 0;
if (T->Elemento > K) {
se = NumeroElementosMaioresK(T->Esquerda, K);
sd = NumeroElementosMaioresK(T->Direita, K);
return (1 + se + sd);
}
else {
sd = NumeroElementosMaioresK(T->Direita, K);
return sd;
}
}
Programa principal:
#include <stdio.h>
#include <stdlib.h>
#include “ArvoreBinaria-esquisa.h” // deve estar na diretoria/pasta do main
main () {
PNodoArv T;
int Num, soma, k, Num;
T = ConstruirArvoreABP();
ListarPorNivel(T);
maior = MaiorElementoABP(T);
menor = MenorElementoABP(T);
printf(“Maior e menor elementos são: %d, %d\n”, maior, menor);
printf(“Insira um valor inteiro: “);
scanf(“%d”, &k);
soma = SomaElementosMaioresK(T, k);
printf(“Soma dos elementos maiores que %d: %d\n”, k, soma);
Num = NumeroElementosMaioresK(T, k);
printf(“Número de elementos maiores que %d: %d\n”, k, Num);
}
7) Usando a definição de ABP de inteiros em cima, implemente uma função que dada
uma ABP T e uma chave K, devolva a chave seguinte a K na ordem crescente.
Nota: a chave seguinte de K encontra-se no nodo mais à esquerda da subárvore direita
do nodo com a chave K.
int ChaveSeguinteK (PNodoArv T, int K) {
if (T->Elemento == K) { // procurar o nodo mais à esquerda da subárvore direita
if (T->Direita == NULL)
return -1; // K é a chave com maior valor (não existe seguinte)
return MenorElemento(T->Direita);
}
if (K > T->Elemento)
return ChaveSeguinteK(T->Direita, K);
return ChaveSeguinteK(T->Esquerda, K);
}
Programa principal:
#include <stdio.h>
#include <stdlib.h>
#include “ArvoreBinariaPesquisa.h” // deve estar na diretoria/pasta do main
main () {
PNodoArv T;
int Num, soma, k, Num, ChaveSeg;
T = ConstruirArvoreABP();
ListarPorNivel(T);
maior = MaiorElementoABP(T);
menor = MenorElementoABP(T);
printf(“Maior e menor elementos são: %d, %d\n”, maior, menor);
printf(“Insira um valor inteiro: “);
scanf(“%d”, &k);
soma = SomaElementosMaioresK(T, k);
printf(“Soma dos elementos maiores que %d: %d\n”, k, soma);
Num = NumeroElementosMaioresK(T, k);
printf(“Número de elementos maiores que %d: %d\n”, k, Num);
ChaveSeg = ChaveSeguinte(T, k);
printf(“A chave seguinte a %d é: %d\n”, k, ChaveSeg);
}