arvore_binaria.c

#include "arvore_binaria.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct no_arvore No_Arvore;

struct no_arvore{
    char string_item[5];
    No_Arvore* filho_dir;
    No_Arvore* filho_esq;
};


struct arvore_binaria{
    No_Arvore* raiz;
    int profundidade;
};



No_Arvore* no_criar_arvore(char* string_item){
    No_Arvore* novo_no = (No_Arvore*)malloc(sizeof(No_Arvore));

    if(!novo_no){
        return NULL;
    }

    novo_no->filho_dir = NULL;
    novo_no->filho_esq = NULL;
    strcpy(novo_no->string_item, string_item);

    return novo_no;
}

Arvore_Binaria* arvore_criar(char* string_item){//cria arvore já com a raiz
    Arvore_Binaria* nova_arvore = (Arvore_Binaria*)malloc(sizeof(Arvore_Binaria));

    if(!nova_arvore){
        return NULL;
    }

    nova_arvore->profundidade = -1;
    nova_arvore->raiz = no_criar_arvore(string_item);
    return nova_arvore;
}

void arvore_inserir_esquerda(Arvore_Binaria* arvore, char* string_item){
    if(!arvore){
        return;
    }


    No_Arvore* novo_no = no_criar_arvore(string_item);

        if(!novo_no){
            printf("impossivel criar novo no\n");
        }

    arvore->raiz->filho_esq = novo_no;

    return;
}



void arvore_inserir_direita(Arvore_Binaria* arvore, char* string_item){
    if(!arvore){
        return;
    }

    No_Arvore* novo_no = no_criar_arvore(string_item);

        if(!novo_no){
            printf("impossivel criar novo no\n");
        }

    arvore->raiz->filho_dir = novo_no;

    return;
}

void arvore_apontar_null(Arvore_Binaria* arvore){//função utilizada para apagar a árvore da pilha
    if(!arvore){
        printf("arvore é null\n");
        return;
    }

    arvore->raiz = NULL;
    return;
}


void arvore_desalocar_nos(No_Arvore** raiz){
    if((*raiz) != NULL){
        arvore_desalocar_nos(&(*raiz)->filho_esq);
        arvore_desalocar_nos(&(*raiz)->filho_dir);

        free(*raiz);
       (*raiz) = NULL;

    }

    return;
}

void arvore_desalocar(Arvore_Binaria** arvore){
    if(!arvore){
        printf("arvore é null\n");
        return;
    }

    arvore_desalocar_nos(&(*arvore)->raiz);
    free(*arvore);
    (*arvore) = NULL;

    return;
}
//a função arvore_fusao abaixo une duas árvores inseridas na pilha;
//quando há uma inserção de operador na pilha, é necessário fazer o nó que contem o operador ter seu nó esquerdo apontado para
//a subárvore armazenada no topo da pilha, e seu nó direito apontado para a árvore que ocupa a posição logo após o topo da pilha;

Arvore_Binaria* arvore_fusao_esquerda(Arvore_Binaria* subarvore_esquerda, Arvore_Binaria* arvore_mae ){
    if(!subarvore_esquerda || !subarvore_esquerda->raiz || !arvore_mae){
        printf("parametros incorretos para arvore_fusao_esquerda\n");
        return NULL;
    }

    arvore_mae->raiz->filho_esq = subarvore_esquerda->raiz;

    return arvore_mae;
}


Arvore_Binaria* arvore_fusao_direita(Arvore_Binaria* subarvore_direita, Arvore_Binaria* arvore_mae){
    if(!subarvore_direita || !subarvore_direita->raiz || !arvore_mae){
        printf("parametros incorretos para arvore_fusao_direita\n");
        return NULL;
    }

    arvore_mae->raiz->filho_dir = subarvore_direita->raiz;

    return arvore_mae;
}
/*void arvore_binaria_inserir(Arvore_Binaria* arvore, int item){//função só para arvore binaria de busca
    if(!arvore_binaria){
        return;
    }

    if(arvore->raiz == NULL){
        No* raiz = no_criar(item);
        arvore->raiz = raiz;
        arvore->profundidade++;
        return;
    }

    recursao_inserir(arvore->raiz, item);

    arvore->profundidade++;
}

void recursao_inserir(No* no, int item){
    if(no == NULL){
        no = no_criar(item);
        return;
    }

    if(item > no->item){
        recursao_inserir(no->filho_dir, item);
    }
    else{
        recursao_inserir(no->filho_esq, item);
    }
}
*/
void arvore_imprimir_no(No_Arvore* no){
    if(!no){
        //printf("BOTOU O NULL PRA MAMA\n");
        return;
    }

    printf("%s -", no->string_item);
    arvore_imprimir_no(no->filho_esq);
    arvore_imprimir_no(no->filho_dir);
}

void arvore_imprimir(Arvore_Binaria* arvore){
    if(!arvore){
        printf("arvore é null\n");
        return;
    }

    arvore_imprimir_no(arvore->raiz);
    printf("\n");
    printf("arvore impressa\n");
}


/*
teste da arvore binaria e fusão
int main(){
    printf("entrei na main\n");

    Arvore_Binaria* nova_arvore = arvore_criar("R1");

    arvore_inserir_esquerda(nova_arvore, "E1");
    arvore_inserir_direita(nova_arvore, "D1");

    No_Arvore* novo_no = no_criar("E12");
    nova_arvore->raiz->filho_esq->filho_esq = novo_no;

    printf("ARVORE UM:\n");
    arvore_imprimir(nova_arvore);

    Arvore_Binaria* segunda_arvore = arvore_criar("R2");

    arvore_inserir_esquerda(segunda_arvore, "E2");
    arvore_inserir_direita(segunda_arvore, "D2");

    printf("ARVORE DOIS:\n");
    arvore_imprimir(segunda_arvore);


    Arvore_Binaria* arvore_mae = arvore_criar("+");
    Arvore_Binaria* arvore_um = arvore_fusao_esquerda(nova_arvore, arvore_mae);
    //arvore_apontar_null(nova_arvore);

    printf("\nimprimindo após a fusão esquerda:\n");
    arvore_imprimir(arvore_um);

    arvore_um = arvore_fusao_direita(segunda_arvore, arvore_mae);
    arvore_apontar_null(segunda_arvore);
    //imprimir a mae

    printf("\nimprimindo após a fusão direita:\n");
    arvore_imprimir(arvore_um);

    return 0;
}

*/