Monte uma árvore capaz de armazenar uma struct contendo as seguintes informações: nome do município, área total do município (em km2) e população. A árvore deverá ter funções para inserir (pelo nome), percorrer e listar. Implemente também funções para:
(a) Contar o número de municípios, percorrendo os nós cadastrados na árvore
(b) Mostrar apenas os nomes dos municípios com mais de X habitantes. Por exemplo, X pode ser 100.000 pessoas.
© Mostrar a densidade demográfica de cada cidade. A densidade demográfica é a relação entre a população e a área.
(d) Mostrar o somatório de área em km2 de todas as cidades juntas em relação ao território nacional (em porcentagem).
(e) Mostrar as cidades em ordem alfabética, com todos os dados.
(f) Mostrar o nome da cidade com a maior população.

Passo 1

Neste exercício, precisamos criar uma árvore binária de busca que armazene para cada município: nome, área (km²) e população. A árvore deve permitir inserção ordenada por nome e percursos para listar e executar várias consultas (contagem, filtros, densidade, somatório de área, ordenação alfabética e encontrar o município de maior população).

Passo 2

Definimos duas structs: uma “City” para guardar os dados do município (nome, área e população) e uma “Node” para representar cada nó da árvore, com ponteiros para filhos esquerdo e direito.

Passo 3

Implementamos createNode(City c) para alocar um nó novo e insertNode(Node **root, City c) para inserir recursivamente um município na árvore comparando nomes com strcmp.

Passo 4

Fazemos uma travessia inOrder genérica (inOrder) que aceita uma função de visita (visit) para aplicar em cada City. A partir dela, criamos funções específicas: countNodes (conta nós), printIfPopGreater (imprime nomes com população > X), printDensity (calcula e imprime densidade), sumArea (acumula área), printCity (imprime todos os dados) e findMaxPop (atualiza município de maior população).

Passo 5

Usamos variáveis globais auxiliares (THRESHOLD, totalArea, maxCity) para compartilhar estados entre as funções de visita e o main. No main, inserimos alguns municípios de exemplo e chamamos as rotinas emOrder com as visitas apropriadas para resolver cada item de (a) a (f).
Ao final, temos: a) contagem de nós, b) lista de nomes com população acima de X, c) densidades, d) somatório de área e porcentagem sobre área nacional, e) listagem alfabética completa e f) o nome do município mais populoso.

Resposta

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NAME 100
typedef struct {
char name[MAX_NAME];
float area;
int population;
} City;
typedef struct Node {
City city;
struct Node *left, *right;
} Node;
// Cria um novo nó com os dados do município
Node* createNode(City c) {
Node* node = (Node*)malloc(sizeof(Node));
if (!node) {
printf(“Erro de alocação\n”);
exit(1);
}
node->city = c;
node->left = node->right = NULL;
return node;
}
// Insere um município na árvore ordenando pelo nome
void insertNode(Node **root, City c) {
if (*root == NULL) {
*root = createNode©;
return;
}
if (strcmp(c.name, (*root)->city.name) < 0)
insertNode(&(*root)->left, c);
else
insertNode(&(*root)->right, c);
}
// Travessia in-order genérica
void inOrder(Node *root, void (*visit)(City)) {
if (root) {
inOrder(root->left, visit);
visit(root->city);
inOrder(root->right, visit);
}
}
// Função de visita para listar todos os dados
void printCity(City c) {
printf("%s: Pop=%d, Area=%.2f km2\n", c.name, c.population, c.area);
}
// Conta número de nós
int countNodes(Node *root) {
if (!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
// Mostra nomes com população > X
void printIfPopGreater(City c) {
extern int THRESHOLD;
if (c.population > THRESHOLD)
printf("%s\n", c.name);
}
// Mostra densidade demográfica de cada cidade
void printDensity(City c) {
float dens = c.population / c.area;
printf("%s: Densidade = %.2f hab/km2\n", c.name, dens);
}
// Soma área de todas as cidades
void sumArea(City c) {
extern float totalArea;
totalArea += c.area;
}
// Encontra a cidade com maior população
void findMaxPop(City c) {
extern City maxCity;
if (c.population > maxCity.population)
maxCity = c;
}
// Variáveis globais auxiliares
int THRESHOLD = 100000;
float totalArea = 0.0;
City maxCity = {"", 0.0, 0};
int main() {
Node *root = NULL;
// Exemplo de inserção
City c1 = {"AlphaVille", 120.5, 150000};
City c2 = {"BetaTown", 80.0, 80000};
City c3 = {"GammaCity", 200.0, 300000};
insertNode(&root, c1);
insertNode(&root, c2);
insertNode(&root, c3);

// a) Número de municípios
printf("Numero de municipios: %d\n", countNodes(root));

// b) Municípios com mais de X habitantes
printf("\nMunicipios com mais de %d hab:\n", THRESHOLD);
inOrder(root, printIfPopGreater);

// c) Densidade demográfica
printf("\nDensidades demograficas:\n");
inOrder(root, printDensity);

// d) Somatório de área e porcentagem
totalArea = 0.0;
inOrder(root, sumArea);
float nationalArea = 8515767.0; // Exemplo: área do país
printf("\nArea total das cidades: %.2f km2 (%.2f%% do territorio)\n",
       totalArea, (totalArea / nationalArea) * 100.0);

// e) Cidades em ordem alfabética com todos os dados
printf("\nCidades em ordem alfabetica:\n");
inOrder(root, printCity);

// f) Cidade com maior população
maxCity.population = 0;
inOrder(root, findMaxPop);
printf("\nCidade com maior populacao: %s (%d hab)\n",
       maxCity.name, maxCity.population);

return 0;
}

Exercícios relacionados