#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct arvore
{
int key;
struct arvore * right, *left;
};
typedef struct arvore Arvore;
Arvore * alocar(int key)
{
Arvore * p = (Arvore *)malloc(sizeof(Arvore));
p->key = key;
p->right = NULL;
p->left = NULL;
return p;
}
int procurafolha(Arvore * p)
{
int a = 0;
if(p->right == NULL && p->left == NULL)
{
return p->key;
}
else
{
if(p->left != NULL)
{
a = a + procurafolha(p->left);
}
if(p->right != NULL)
{
a = a + procurafolha(p->right);
}
}
return a;
}
int procurasemfolha(Arvore * p)
{
int a = 0;
if(p->left != NULL)
{
a = a + procurasemfolha(p->left);
}
if(p->right != NULL)
{
a = a + procurasemfolha(p->right);
}
if(p->right != NULL || p->left != NULL)
{
a = a + p->key;
}
return a;
}
Arvore * insere(Arvore * p, int key)
{
if(p == NULL)
{
p = alocar(key);
return p;
}
else if(key < p->key)
{
p->left = insere(p->left, key);
}
else if(key > p->key)
{
p->right = insere(p->right, key);
}
}
void libera(Arvore * p)
{
if(p != NULL)
{
libera(p->left);
libera(p->right);
free(p);
p = NULL;
}
}
int main()
{
Arvore *p = NULL;
char a;
int n, i = 0;
int qtd, qtd01;
while(1)
{
scanf("%d", &n);
p = insere(p, n);
scanf("%c", &a);
if(a == '\n')
{
break;
}
}
qtd = procurafolha(p);
qtd01 = procurasemfolha(p);
printf("%d %d\n", qtd, qtd01);
libera(p);
return 0;
}
Explicação do problema: Você deverá imprimir dois valores inteiros separados por espaço, o primeiro com a soma dos elementos que são folhas, o segundo com a soma dos elementos internos (não são folhas).
Teste 1:
entrada
1 2 3 4 5 6 7 8 9 10
saida
10 45
Teste 2:
entrada
5 3 7 2 4 6 8
saida
20 15
Teste 3:
entrada
10 2 3 0 5 1 15 20 4 6 7 8 11 9 12 16 19 17 18 21
saida
65 139