C Construir Arvore binaria em C, a partir da ordem infixa e posfixa..!

Gabriel Tellaroli Ramos · 2 de outubro de 2020

Galera seguinte estou com um problema em C para construir uma arvore binaria a partir de dois vetores um que tem os dados da arvore em-ordem e outro tem seus dados em pós-ordem. A partir desses dados eu tenho que fazer a criação da arvore, eu fiz algumas tentativas e deu certo para esse exemplo do problema porém fui testar outros exemplos e n deu certo. Se alguém puder me ajudar vou anexar os arquivos com os meus códigos e com o enunciado do problema.

Trabalho - 1.zip == São meus códigos. (O makefile n sei se está correto, mas esta funcionando kkk)
Planilha com meu teste de mesa == https://docs.google.com/spreadsheets/d/1iPu3WRVJTxvhAoP2OyG4jo40RCZ5R4_eVA7JDeeKIgI/edit?usp=sharing
ED2-Trab1-2020 == Problema.

Trabalho - 1.zip ED2-Trab1-2020.pdf

arfneto · 2 de outubro de 2020

Poste o código compilável, dentro daquele formulário <code> assim ajuda os outros a ajudarem você. Também os dados de entrada se tem, um enunciado, o makefile. O normal para que alguém que tenha tempo e queira ajudar possa ler aqui o material. E para alguém que tem um problema similar possa ler também

Gabriel Tellaroli Ramos · 2 de outubro de 2020

@arfneto Então, o código são 3 arquivos, por isso coloquei em zip acredito ser mais fácil, de analisar assim você pode descompactar e ver todos os arquivos, mas a minha duvida em si é nessa função que eu vou usar para criar a arvore. Na minha logica deu certo mas eu fiquei muito preso ao caso de exemplo do enunciado, e quando fui testar com outro caso não deu certo! Se você puder me ajudar, o maior problema é achar alguma condição que atenda a todos os casos de ter uma subarvore esquerda ou direita.

void make_tree(arvbin *t, int n, int in_index, int *infixa, int pos_index, int *posfixa)
{
    if ((*t = (arvbin)malloc(sizeof(struct no_arvbin))) == NULL)
    {
        fprintf(stderr, "Erro de alocacao de memoria!\n");
        exit(1);
    }
    //int countDir = 0;
    (*t)->dado = posfixa[pos_index];
    (*t)->esq = (*t)->dir = NULL;
    int count = 0;

    while (infixa[in_index] != posfixa[pos_index])
    {
        in_index++;
        count++;
    }

    // Verificor se tem Subarvore esquerda!!
    if (in_index > 0 && count != 1)
    {
        // Tem Subarvore esquerda
        if (in_index % 2 == 0)
        {
            make_tree(&(*t)->esq, in_index, 0, infixa, in_index - 1, posfixa);
        }
        else
        {
            make_tree(&(*t)->esq, in_index, count+1, infixa, count+2, posfixa);
        }
    }

    // Verificor se tem Subarvore direita!!
    if (in_index + 1 < n )
    {
        // Tem Subarvore direita
        make_tree(&(*t)->dir, pos_index, in_index, infixa, pos_index - 1, posfixa);
    }
}

adicionado 3 minutos depois

arfneto · 2 de outubro de 2020

12 minutos atrás, Gabriel Tellaroli Ramos disse:

Então, o código são 3 arquivos, por isso coloquei em zip acredito ser mais fácil, de analisar assim você pode descompactar e ver todos os arquivos, mas a minha duvida em si é nessa função que eu vou usar para criar a arvore. Na minha logica deu certo mas eu fiquei muito preso ao caso de exemplo do enunciado, e quando fui testar com outro caso não deu certo! Se você puder me ajudar, o maior problema é achar alguma condição que atenda a todos os casos de ter uma subarvore esquerda ou direita

Bom que postou os dados de entrada, a saida esperada e o enunciado.

O mais fácil é ter aqui os 3 arquivos, de mod que se pode DIRETO do forum, importar os dados para um ambiente de desenvolvimento e compilar, quando se tem tempo e acha que pode ajudar.

Não é mais fácil sair do forum, fazer o download de 3 arquivos de algum lugar, extrair para um outro lugar, criar um projeto com eles e aí sim compilar.

Mais ainda: muita gente não se sente a vontade fazendo download de arquivos estranhos de origem desconhecida. É muito diferente quando vê um texto na sua tela e pode simplesmente copiar.

Vou ler seu código.

Em relação ao que já li porque não precisei sair da tela:

void make_tree(arvbin *t, int n, int in_index, int *infixa, int pos_index, int *posfixa)
{
    if ((*t = (arvbin)malloc(sizeof(struct no_arvbin))) == NULL)
    {

Essas funções tipo factory, que alocam e criam coisas, devem DEVOLVER O ENDEREÇO da tal coisa.

Em geral nunca retorne void. Quase sempre é um desperdício. Muitas vezes é um erro. Aqui é um erro mesmo.

Todos esses ponteiros são locais, a menos que tenha declarado variáveis globais e aí seria um outro erro.

Isso quer dizer que sua função não retorna nada e tudo que tem lá dentro some. Como aloca memória, a cada chamada tem um vazamento já que nunca mais vai por a mão naqueles endereços. Sugiro ler algo sobre scope no seu livro se tem um. Ou arrumar um ou dois se não tem nenhum. É muito importante.

Evite ao máximo declarar ponteiros como tipos. Em geral isso só dá problema. Não é bom você ter que saber que arvbin é um ponteiro, nem mesmo se fosse Parvbin. Não faça isso.

Se Arvore é um tipo então

Arvore* é um ponteiro para árvore
Arvore** é um ponteiro para um ponteiro para Arvore

E está tudo resolvido e legível. Não precisa ler nenhum header nem aprender nada sobre o programa. Apenas convencione, por exemplo: os nomes de todos tipos começam por maiúscula e nenhum tipo é um ponteiro. E nunca vai ter que pensar nisso.

/* percurso em pré-ordem da ABB */
int pre_ordem(Arvore*);

Sugiro evitar acentos em comentários. E evitar comentários desse tipo. Dá pra imaginar o uma função chamada pre_ordem() faz.

E curiosamante é o único comentário em seu programa.

não declare nomes em protótipos. São apenas para o compilador.

Compare com esse trecho e veja se não é mais simples de ler:

#include <stdio.h>

typedef int Dado;

typedef struct node 
{
    Dado         dado;
    struct node* D;
    struct node* E;

}   Arvore;

Arvore* make_tree(int,int,int[],int,int[]);
int pre_ordem(Arvore* A) { return 0; };

int main()
{
    int n = 0;
    int infixa[5], posfixa[5];
    Arvore* pinheiro = make_tree(n, 0, infixa, n - 1, posfixa);
    n = pre_ordem(pinheiro);
    return 0;
};

Arvore* make_tree(int n, int in_index, int* infixa, int pos_index, int* posfixa)
{
    return NULL;
};

Não precisa de uma função init() se tem uma funçao make_tree()

adicionado 9 minutos depois

O makefile está certo. Mas as opções de compilação não estão lá. Seria bom se certificar de algumas, como -std no mínimo

Gabriel Tellaroli Ramos · 2 de outubro de 2020

@arfneto então essa duas funções ja são definidas no problema em si eu só peguei e criei a logica dentro da maketree, o professor n exige que utilize elas mas eu achei que seria melhor utilizando elas pois ele disse que resolvou com elas, o problema é que essa logica que eu criei n atende a todos os casos de árvore e acabou funcionando apenas para a do enunciado.

adicionado 1 minuto depois

A respeito do makefile o que seria essa -std, nunca tinha feito o make file antes, me baseei em um que ja estava pronto só troquei os nomes dos arquivos.

arfneto · 2 de outubro de 2020

3 minutos atrás, Gabriel Tellaroli Ramos disse:

@arfneto então essa duas funções ja são definidas no problema em si eu só peguei e criei a logica dentro da maketree, o professor n exige que utilize elas mas eu achei que seria melhor utilizando elas pois ele disse que resolvou com elas, o problema é que essa logica que eu criei n atende a todos os casos de árvore e acabou funcionando apenas para a do enunciado.

adicionado 1 minuto depois

A respeito do makefile o que seria essa -std, nunca tinha feito o make file antes, me baseei em um que ja estava pronto só troquei os nomes dos arquivos.

Isso só funciona se passar o endereço de uma Arvore já alocada antes de entrar em make_tree(). Se passar um ponteiro vai sumir. Está errado. É frágil e não se escreve assim. Avise seu professor.

-std define o nível da linguagem que vai usar. Use -std=C11 e estará bem.

arfneto · 2 de outubro de 2020

li seu programa. Parece complicado demais sem necessidade.

E aquele erro de que falei não existe: arvbin é um ponteiro então arvbin*, primeiro parâmetro para make_tree(), é

    struct no_arvbin**

e o que está passado é um endereço de um ponteiro e então retorna ok. Como vê eu fui vítima do problema que eu te mostrei: é muito difícil de ler isso, mesmo que seja o seu programa. Não use isso como norma. Te mostrei a diferença acima no outro post.

Mais ainda, não há razão para tantos parâmetros em make_tree() como declarou:

    void make_tree(arvbin * t, int n, int in_index, int infixa[], int pos_index,int posfixa[]);

Ou o mais claro,

     void    make_tree( struct no_arvbin** t, int n, int in_index, int infixa[], int pos_index,int posfixa[] );

Para que não seja preciso pesquisar para saber que o parâmetro é um ponteiro.

No entanto bastaria escrever

    arvbin    make_tree(int N, infixa[],  posfixa[]);

E mais uma vez vou dizer: NÃO defina tipos ponteiros. Só vai cair na sua cabeça.

Porque não precisa do resto?

Entenda que na verdade não precisa ficar copiando o vetor da entrada. É um só. E o número de nós que vai receber em make_tree() é sempre o mesmo para os dois vetores, já que só muda o percurso. Veja em sua planilha. Como os vetores são passados por referência, os tais int[], você pode fazer o simples e passar o endereço já corrigido...

Instintivamente já dá pra imaginar que se são subárvores da mesma árvore inicial deveria bastar passar o início.

Nunca use menus e fique lendo dados do teclado enquanto seu programa não está pronto.Só perde seu tempo.

Veja a diferença com os dados do exemplo, em SEU programa

    const int n = 8;
    const int infixa[] =  {  5,  4, 20,  9,  8, 10, 18, 15 };
    const int posfixa[] = {  4,  5,  9, 20, 18, 10, 15,  8 };

Qual o sentido de ficar digitando tudo isso a cada teste? Apenas chame make_tree() com esses valores até dar certo. E depois teste com outros.

E nunca não leia dados do teclado. Leia de um arquivo. É muito, mas muito mais fácil. E pode reproduzir os testes a qualquer momento, simplesmente guardando os arquivos. Ler do teclado é inútil. Se o enunciado exige ao final você troca. Mas o final chega antes se não ficar perdendo tempo com dezenas de dados a cada mísero teste.

Não se esqueça: o programa tem que poder ler até 1 milhão de dados, o nome popular para 10 elevado à sexta potência.

Não precisa de uma tree_init()...