Binary Tree Implementation - C Language

Asked

Viewed 3,423 times

1

I’m trying to insert a tree node.

I am using this code, but there are a number of small errors that I cannot understand why of the errors.

The last of them is related to valor1, which is not stated. However I need my node new receive a value to make comparisons of smaller and larger than struct registro to be added to the tree.

void insere_Arvore(nodo* raiz, struct registro_st registro){
    if(raiz == NULL)
        {
        return 0;
        }
    nodo* novo = (nodo*)malloc(sizeof(nodo));
    if(novo == NULL){
        return 0;
    }
    novo->dado->valor = valor1;
    novo->dir = NULL;
    novo->esq= NULL;
        if(*raiz = NULL)
        {
            *raiz = novo;
        }
    else{
    nodo* atual = *raiz;
    nodo* ant = NULL;
    }

        while(atual != NULL)
            {
            ant = atual;
            if (valor1 == atual->dado->valor){
                            free(novo);
                            return 0;
            }

        if(valor1 > atual->dado->valor)
                                    {
                    atual = atual->dir
    }
        else{
                    atual = atual->esq;
        }
        if(valor1 > ant->dado->valor)
                                    {
        ant->dir = novo;
        }
        else{
        ant->esq = novo;
        }
        if(valor > ant->dado->valor){
            ant->dir = novo;
        }
        else{
        ant->esq = novo;
        }
        }
            }
        return 1;
}

Complete code:

typedef struct registro_st{         // sequência de objetos do mesmo tipo
    char login[50];
    char nome[50];
    float valor;
    struct registro *prox;
} registro;

typedef struct nodo_st{
    registro *dado;
    struct nodo_st *dir;
    struct nodo_st *esq;
} nodo;

typedef struct Lista_st{
    nodo *cabeca;
    nodo *cauda;
    int tamanho;
} lista;

void insere_Arvore(nodo* raiz, struct registro_st registro){
    if(raiz == NULL)
        {
        return 0;
        }
    nodo* novo = (nodo*)malloc(sizeof(nodo));
    if(novo == NULL){
        return 0;
    }
    novo->dado->valor = valor1;
    novo->dir = NULL;
    novo->esq= NULL;
        if(*raiz = NULL)
        {
            *raiz = novo;
        }
    else{
    nodo* atual = *raiz;
    nodo* ant = NULL;
    }

        while(atual != NULL)
            {
            ant = atual;
            if (valor1 == atual->dado->valor){
                            free(novo);
                            return 0;
            }

        if(valor1 > atual->dado->valor)
                                    {
                    atual = atual->dir
    }
        else{
                    atual = atual->esq;
        }
        if(valor1 > ant->dado->valor)
                                    {
        ant->dir = novo;
        }
        else{
        ant->esq = novo;
        }
        if(valor > ant->dado->valor){
            ant->dir = novo;
        }
        else{
        ant->esq = novo;
        }
        }
            }
        return 1;
}
c

  • return 0; Change: 'must be' Return;

  • `For ease of readability and comprehension, constantly ignore the code. Discard after each open clamp, no power before each closing armour. Suggests each traverse level be 4 spaces

  • In C, heap allocation functions (malloc, calloc, realloc) returnvoid *which can be assigned to any pointer, Casting only blocks the code.

  • nodo* novo = It’s very poor programming practice too weak to name variables the same as a type name

1 answer

3


There’s a lot of things that aren’t quite right.

  • To be able to modify the root within the function a pointer has to be passed to the pointer instead of a normal pointer (more on this topic if you want to read).

  • It is incorrect to use returns with type values 0 or 1 in a function void.

  • Loop/loop should only be used to get to the correct node the insertion made only after this.

Therefore the code should be as follows:

//A raiz passou a **raiz, e registro a *registro
void insere_Arvore(nodo **raiz, struct registro_st *registro) {
    nodo* novo = malloc(sizeof(nodo)); //agora sem cast pois é desnecessário
    if(novo == NULL){
        return; // é void logo não pode ter tipo de retorno
    }

    novo->dado = registro; //o dado é o registro todo em si
    novo->dir = NULL;
    novo->esq= NULL;

    if(*raiz == NULL){ //ver se o valor do ponteiro é null, logo arvore vazia
        *raiz = novo;
        return;
    }

    nodo* atual = *raiz;
    nodo* ant = NULL;

    while(atual != NULL){ // laço/ciclo agora só para navegar até ao sitio correto
        ant = atual;

        //o valor a ser inserido vem no próprio registro, com registro->valor
        if (registro->valor == atual->dado->valor){
            free(novo);
            return; // é void logo não pode ter tipo de retorno
        }

        if(registro->valor > atual->dado->valor){
            atual = atual->dir;
        }
        else{
            atual = atual->esq;
        }
    }

    //após navegar é feita a inserção pelo no anterior.
    if (registro->valor > ant->dado->valor){ //se maior que o anterior fica a direita
        ant->dir = novo;
    }
    else { //senão fica a esquerda
        ant->esq = novo;
    }
}

The main naturally will also be a little different:

int main(){
    nodo *arvore = NULL;

    registro *reg = malloc(sizeof(registro));
    strcpy(reg->nome, "O nome aqui");
    strcpy(reg->login, "O login aqui");
    reg->valor = 10;


    insere_Arvore(&arvore, reg); 
    //            ^-- agora com o endereço de arvore

    //...

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.