Convert add and remove functions in tree to recursive

Question

I’m having trouble converting two tree functions into C recursive form.

int insere_arvore(ArvBin* raiz, int valor){
if(raiz == NULL)
    return 0;
NO* novo;
novo = (NO*) malloc(sizeof(NO));
if(novo == NULL)
    return 0;
novo->info = valor;
novo->dir = NULL;
novo->esq = NULL;

if(*raiz == NULL)
    *raiz = novo;
else{
    NO* atual = *raiz;
    NO* ant = NULL;
    while(atual != NULL){
        ant = atual;
        if(valor == atual->info){
            free(novo);
            return 0;
        }

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

NO* remove_atual(NO* atual) {
NO *no1, *no2;
if(atual->esq == NULL){
    no2 = atual->dir;
    free(atual);
    return no2;
}
no1 = atual;
no2 = atual->esq;
while(no2->dir != NULL){
    no1 = no2;
    no2 = no2->dir;
}
if(no1 != atual){
    no1->dir = no2->esq;
    no2->esq = atual->esq;
}
no2->dir = atual->dir;
free(atual);
return no2;
}

I tried it this way:

int insere_rec_arvore(ArvBin* raiz, int valor, NO* atual){
if(raiz == NULL)
    return 0;
NO* novo;
novo = (NO*) malloc(sizeof(NO));
if(novo == NULL)
    return 0;
novo->info = valor;
novo->dir = NULL;
novo->esq = NULL;

if(*raiz == NULL)
    *raiz = novo;
else{
    NO* atual = *raiz;
    NO* ant = NULL;
    if (atual != NULL) {
        ant = atual;
        if(valor == atual->info){
            free(novo);
            return 0;//elemento já existe
        }

        if(valor > atual->info) {
            atual = atual->dir;
        } else {
            atual = atual->esq;
            insere_rec_arvore(raiz, valor, atual);
        }
    }
    if(valor > ant->info)
        ant->dir = novo;
    else
        ant->esq = novo;
}
return 1;
}

NO* remove_rec_atual(NO* atual, NO *no1, NO *no2 ) {
if(atual->esq == NULL){
    no2 = atual->dir;
    free(atual);
    return no2;
}
no1 = atual;
no2 = atual->esq;
if(no2->dir != NULL){
    no1 = no2;
    no2 = no2->dir;
    remove_rec_atual(atual, no1, no2);
}
if(no1 != atual){
    no1->dir = no2->esq;
    no2->esq = atual->esq;
}
no2->dir = atual->dir;
free(atual);
return no2;
}

I couldn’t run the code.

Thank you.

Answer 1

Good afternoon friend, good let’s see !! For you to implement recursively the insert would look like this

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
int dado;
Node* esq;
Node* dir;
} Node;
typedef struct Node Arv;

// Insere o elemento recursivamente !!
void InsereArvore(Arv *Raiz,int dado){
Node* novo = (Node*)calloc(1,sizeof(Node));
novo->dado = dado;
novo->dir= NULL;
novo->esq= NULL;

if(Raiz == NULL)
{
    printf("Insere");
    Raiz = novo;
}
else
{
    Arv* auxiliar = Raiz;
    if(dado>auxiliar->dado)
    {
        InsereArvore(auxiliar->dir,dado);
    }
    else
    {
        InsereArvore(auxiliar->dir,dado);
    }

    }

    }


int main()
{

Arv *begin = NULL ; // Inicializando a arvore

InsereArvore(begin,5);
InsereArvore(begin,6);
InsereArvore(begin,4);
return 0;
}

I was only able to implement the insertion, not because the removal is difficult, but I forgot the rule to remove an element from a binary tree when having children, when a leaf node is easy, but I forgot the rule to remove a node that has one or two children.

Answer 2

Friend also has another way to implement without creating nodes that is a chatisse !! for binary tree you can implement this way

#include <stdio.h>
#include <stdlib.h>
#define infinito 10000
#define aloc (int*)calloc(infinito,sizeof(int))
#define null -987789654

void InsereArvore(int *arvore,int dado,int indice) {

if(!arvore[indice]) {
    arvore[indice]=dado;
} else {
    if(dado<arvore[indice]){
        InsereArvore(arvore,dado,(2*indice)+1); 
    } else {
        InsereArvore(arvore,dado,(2*indice)+2);
    }
}

}

void RemoveArvore(int *arvore,int dado,int indice) {

// Buscando pelo elemento a ser removido
if(dado==arvore[indice]) {
    // Encontrou o elemento a ser removido !!
    int filhoesq = 2*indice+1;
    int filhodir = 2*indice+2;
    /* tres casos para tratar !! Elemento é folha, elemento tem um filho,             
dois filhos*/

    if(!arvore[filhoesq]&&!arvore[filhodir]) {
        // Folha apenas remove
        arvore[indice]=0; return;
    }

    if(!arvore[filhodir]&&arvore[filhoesq]!=0) {
        // apenas o nó da esquerda
        int filhoesq = 2*indice+1;
        arvore[indice]=arvore[filhoesq]; // colocando o filho no lugar do pai
        arvore[filhoesq]=0; // removendo o filho
    }

    if(!arvore[filhoesq]&&arvore[filhodir]!=0) {
        // apenas o nó da direita
        arvore[indice]=arvore[filhodir]; // colocando o filho no lugar do 
        arvore[filhodir]=0; // removendo no da direita
    }

    if(arvore[filhodir]!=0&&arvore[filhoesq]!=0) {
        // o nó a ser removido tem dois nós filhos !!

        arvore[indice]=arvore[filhoesq]; 
        arvore[filhoesq]=arvore[filhodir];
        arvore[filhodir]=0;
    }

} else {
    if(dado<arvore[indice]){
        RemoveArvore(arvore,dado,(2*indice)+1);
    }else {
        RemoveArvore(arvore,dado,(2*indice)+2);
    }
}

}

void ImprimiArvore(int *arvore,int indice) {

int filhoesq = 2*indice+1;
int filhodir = 2*indice+2;

if(!arvore[indice])return;

printf("Dado: %d\n",arvore[indice]);
if(arvore[filhoesq]!=0)ImprimiArvore(arvore,filhoesq);
if(arvore[filhodir]!=0)ImprimiArvore(arvore,filhodir);
}

int main() {

int *arvore = aloc;
/* Para inserção, remoção, ou impressão da árvore sempre entrege o indice 
como sendo 0*/
/* Está arvore não aceita elemento 0 , como dado !! mas você pode modificar 
para aceitar 
*/
InsereArvore(arvore,5,0);
InsereArvore(arvore,3,0);
InsereArvore(arvore,6,0);
InsereArvore(arvore,1,0);
InsereArvore(arvore,2,0);
ImprimiArvore(arvore,0);
return 0;

}