Considere as seguintes declarações (NodoArv e PNodoArv), adaptadas dos apontamentos:
struct NodoArv {
int Elemento;
struct NodoArv *Esquerda;
struct NodoArv *Direita;
};
typedef struct NodoArv *PNodoArv;
Copiar para o ficheiro “ArvoreBinaria.h” e adaptar as funções associadas às operações
sobre árvores binárias (3.1 a 3.12)
1) Implementar uma função para construir uma árvore binária T com valores inteiros
positivos, inseridos a partir do teclado, usando a função InserirPorAltura (ver
apontamentos).
PNodoArv ConstruirArvore () {
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 = InserirPorAltura(X, T);
printf(“Inserir um inteiro positivo (negativo para terminar): \n”);
scanf(“%d”, &X);
}
}
return T;
2) Usando a definição de árvore binária de inteiros em cima, implemente uma função
que dada uma árvore T, determine o número de elementos com o mesmo valor da raíz.
int NumeroElementosIguaisRaiz (PNodoArv T) {
int NumeroIguaisK (PNodoArv T, int k) {
int igEsq, igDir;
if (T == NULL)
return 0;
igEsq = NumeroIguaisK(T->Esquerda, k);
igDir = NumeroIguaisK(T->Direita, k);
if (T->Elemento == k)
return (1 + igEsq + igDir);
else
return (igEsq + igDir);
}
if (ArvoreVazia(T))
return 0;
else
return NumeroIguaisK(T, T->Elemento);
}
Programa principal:
#include <stdio.h>
#include <stdlib.h>
#include “ArvoreBinaria.h” // deve estar na diretoria/pasta do main
main () {
PNodoArv T;
int Num;
T = ConstruirArvore();
ListarPreOrdem(T);
ListarEmOrdem(T);
ListarPosOrdem(T);
Num = NumeroElementosIguaisRaiz(T);
}
printf(“Número de elementos iguais à raíz : %d\n”, Num);
3) Usando a definição de árvore binária de inteiros em cima, implemente uma função
que dada uma árvore T, determine o maior elemento de T.
Nota: esta função só se aplica a árvores não vazias, pois devolver o valor 0 para indicar o
maior elemento duma árvore vazia não é correto. Assim sendo, vai-se considerar como
caso terminal a árvore só com um nodo (folha).
int MaiorElemento (PNodoArv T) {
int me, md, maior;
if (T->Esquerda == NULL && T->Direita == NULL) // T é folha
return T->Elemento;
maior = T->Elemento;
if (T->Esquerda != NULL) {
// a subárvore esquerda é não vazia
me = MaiorElemento(T->Esquerda);
if (me > maior)
maior = me;
if (T->Direita != NULL) {
// a subárvore direita é não vazia
md = MaiorElemento(T->Direita);
if (md > maior)
maior = md;
}
else { // a subárvore direita é não vazia, com toda a certeza
md = MaiorElemento(T->Direita);
if (md > maior)
maior = md;
}
return maior;
}
Programa principal:
#include <stdio.h>
#include <stdlib.h>
#include “ArvoreBinaria.h” // deve estar na diretoria/pasta do main
main () {
PNodoArv T;
int Num, maior;
T = ConstruirArvore();
ListarEmOrdem(T);
Num = NumeroElementosIguaisRaiz(T);
printf(“Número de elementos iguais à raíz : %d\n”, Num);
maior = MaiorElemento(T);
printf(“O maior elemento da árvore é : %d\n”, maior);
}
4) Usando a definição de árvore binária de inteiros em cima, implemente uma função
que dada uma árvore T, determine a soma dos elementos de T.
int SomaElementos (PNodoArv T) {
int se, sd, soma;
if (T == NULL)
return 0;
se = SomaElementos(T->Esquerda);
sd = SomaElementos(T->Direita);
return (T->Elemento + se + sd);
}
Programa principal:
#include <stdio.h>
#include <stdlib.h>
#include “ArvoreBinaria.h” // deve estar na diretoria/pasta do main
main () {
PNodoArv T;
int Num, maior, soma;
T = ConstruirArvore();
ListarEmOrdem(T);
Num = NumeroElementosIguaisRaiz(T);
printf(“Número de elementos iguais à raíz : %d\n”, Num);
maior = MaiorElemento(T);
printf(“O maior elemento da árvore é : %d\n”, maior);
soma = SomaElementos(T);
}
7) Escreva uma função em C que aceite um ponteiro para uma árvore binária e retorne
um ponteiro para uma nova árvore binária que seja a imagem espelhada da primeira
(isto é, todas as subárvores da esquerda são agora subárvores da direita e vice-versa)
PNodoArv ArvoreEspelhada (PNodoArv T) {
PNodoArv TEsp;
if (T == NULL)
return NULL;
TEsp = CriarNodo(T->Elemento);
TEsp->Esquerda = ArvoreEspelhada(T->Direita);
TEsp->Direita = ArvoreEspelhada(T->Esquerda);
return TEsp;
}
Programa principal:
#include <stdio.h>
#include <stdlib.h>
#include “ArvoreBinaria.h” // deve estar na diretoria/pasta do main
main () {
PNodoArv T, TEsp;
int Num, maior, soma;
T = ConstruirArvore();
ListarEmOrdem(T);
Num = NumeroElementosIguaisRaiz(T);
printf(“Número de elementos iguais à raíz : %d\n”, Num);
maior = MaiorElemento(T);
printf(“O maior elemento da árvore é : %d\n”, maior);
soma = SomaElementos(T);
TEsp = ArvoreEspelhada(T);
}
ListarEmOrdem(TEsp);