Binary search tree

Navigation
0
#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;   
}

Problem explanation: You should print two integer values separated by space, the first with the sum of the elements that are sheets, the second with the sum of the internal elements (they are not sheets).

Test 1:

  

input 

1 2 3 4 5 6 7 8 9 10
     

exit 

10 45

Test 2:

  

input 

5 3 7 2 4 6 8
     

exit 

20 15

Test 3:

  

input 

10 2 3 0 5 1 15 20 4 6 7 8 11 9 12 16 19 17 18 21
     

exit 

65 139
    
asked by anonymous 02.12.2017 / 17:04

1 answer

0

Its function insere has the missing return, which does not allow you to build the tree correctly. The value to return must be p : 

Arvore * insere(Arvore * p, int key){
    ...

    return p; //falta este retorno
}

And this will already cause your functions to respond to the problem.

See how you get the right Ideone result

However, you can considerably simplify the function logic to find the sums. Here is my suggestion for both: 

int soma_folhas(Arvore *p){
    if (p == NULL) return 0;

    int valorNo = (p->left == NULL && p->right == NULL) ? p->key : 0;
    return valorNo + soma_folhas(p->left) + soma_folhas(p->right);
}

int soma_nao_folhas(Arvore *p){
    if (p == NULL) return 0;

    int valorNo = (p->left == NULL && p->right == NULL) ? 0 : p->key;
    return valorNo + soma_nao_folhas(p->left) + soma_nao_folhas(p->right);
}

Example of this version also in Ideone

I would like to point out that only valorNo has changed between the two functions, because a sheet is the inverse of non-sheet. Soon only the green and false values of the ternary operator were changed.

Notice that I've also changed the function names so they are more intuitive and perceptible relative to what they actually do.

    
02.12.2017 / 18:43
Limit the number of requests in the query Convert CURL command in WebRequest