C Pre-ordem em árvore binária não funcionando

oAnfibio · 6 de julho de 2022

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

//Constantes
#define tamanho 100
#define E 0
#define D 1
#define R -1

//Estrutura
struct str_no {
    char dado;
    int esquerda;
    int direita;
    int pai;
};

//Variáveis
struct str_no arvore[tamanho];
int lado, indice = 0;
int opt = -1;
char pai, no;

//Prototipação
void arvore_insere(int pai, char dado, int lado);
int arvore_procura(char dado);
void menu_mostrar(void);
void preOrdem(struct str_no* raiz);

//Função principal
int main(void) {
    int temp;
    do {
        menu_mostrar();
        scanf("%d",&opt);
        switch (opt){
            case 1:
                printf("Digite o valor do PAI:\n");
                scanf(" %c",&pai);
                printf("pai: %c\n",pai);
                printf("Digite o valor do NO:\n");
                scanf(" %c",&no);
                printf("no: %c\n",no);
                printf("Digite o lado da subarvore (E=%d/D=%d/R=%d):\n", E,D,R);
                scanf(" %d",&lado);
                printf("lado: %d\n",lado);
                temp = arvore_procura(pai);
                arvore_insere(temp, no, lado);
                break;
            case 2:
                printf("Digite o valor do NO:\n");
                scanf(" %c",&no);
                temp = arvore_procura(no);
                printf("No %c\nFilho Esquerda: %c\nFilho Direita: %c\n\n",
                        arvore[temp].dado,
                        arvore[arvore[temp].esquerda].dado,
                        arvore[arvore[temp].direita].dado);
                system("read -p 'Pressione Enter para continuar...' var");
                break;
            case 3:
                preOrdem(&arvore[0]);
                system("read -p 'Pressione Enter para continuar...' var");
                break;

        }
    }while (opt != 0);
    system("read -p 'Pressione Enter para continuar...' var");
    return 0;
}

//Inserir nó
void arvore_insere(int pai, char dado, int lado) {
    switch (lado){
        case E:
            arvore[pai].esquerda = indice;
            arvore[indice].dado = dado;
            arvore[indice].pai = pai;
            arvore[indice].esquerda = -1;
            arvore[indice].direita = -1;
            indice++;
        break;
        case D:
            arvore[pai].direita = indice;
            arvore[indice].dado = dado;
            arvore[indice].pai = pai;
            arvore[indice].esquerda = -1;
            arvore[indice].direita = -1;
            indice++;
        break;
        case R:
            arvore[indice].dado = dado;
            arvore[indice].pai = -1;
            arvore[indice].esquerda = -1;
            arvore[indice].direita = -1;
            indice++;
        break;
    }
}

//Desenha o menu na tela
void menu_mostrar(void) {
    system("clear");
    for (int i = 0; i < indice; i++) {
        printf("| %c ",arvore[i].dado);
    }
    printf("\n1 - Inserir um NO na arvore");
    printf("\n2 - Pesquisar um NO na arvore");
    printf("\n3 - Imprimir o percurso pré-ordem da Arvore Binaria");
    printf("\n0 - Sair...\n\n");
}

//Procura nó
int arvore_procura(char dado) {
    if(indice != 0){
        for(int i = 0; i < indice; i++) {
            if (arvore[i].dado == dado) {
                return i;
            }
        }
    }
    return 0;
}

void preOrdem(struct str_no* raiz){
    if(raiz->dado != -1){
        printf("\n%c",raiz->dado);
        preOrdem(&arvore[arvore_procura(raiz->esquerda+'0')]);
        preOrdem(&arvore[arvore_procura(raiz->direita+'0')]);
    }
}

Após a inserção de alguns nodes na arvore, ao executar a opção 3 no menu, o preOrdem loopa infinitamente no node raiz da árvore.

Eu simplesmente não sei mais o que eu fazer.

Quem poder me dar uma luz, agradeço bastante.

devair1010 · 8 de julho de 2022

@oAnfibio você colocou uma função recursiva , e ela serve para Quê !

arfneto · 8 de julho de 2022

Nunca escreva um programa interativo antes de estar pronto. Só vai perder --- como está perdendo --- tempo.

Não use system. De nada serve.
Teste o retorno de scanf SEMPRE. É ingênuo seguir adiante sem saber se leu algo
Porque usou um vetor de tamanho fixo para uma estrutura cuja vantagem é ser dinâmica? Performance?
Não use esses nomes gigantes para as variáveis. Só dificulta a leitura de seu próprio código. Até o usuário digita E e D para esquerda e direita e você mantem por extenso nos nomes no programa?
Talvez não precise escrever tanto "arvore" tambem...
não misture ias funções da arvore com o conteúdp. Só complica. A árvore é de nós e os nós é que tem os dados
use arquivos para a leitura. É muito mais simples

Sugiro alterar antes de procurar o erro. Vai perder muito tempo testando assim

arfneto · 9 de julho de 2022

        menu_mostrar();
        scanf("%d", &opt);

Nunca use void funcao(void).É um desastre e é probido em toda parte. Vendo de um modo simples não acha que essa função deveria receber um menu como argumento e RETORNAR a opção? Não faria a vida mais simples?

E se está claro que só vai ter um menu não poderia só retornar a opção??

    printf("\n1 - Inserir um NO na arvore");
    printf("\n2 - Pesquisar um NO na arvore");
    printf(
        "\n3 - Imprimir o percurso pré-ordem da Arvore "
        "Binaria");
    printf("\n0 - Sair...\n\n");

Um printf de 4 linhas é dezenas de vezes mais rápido que 4 printf de uma linha. E é muito mais fácil de ler e de ajustar

    system("clear");

Não use system(). É em geral proibido mesmo. Mas entenda que clear roda no Linux/Unix/Mac mas não no Windows então pode preferir manter as coisas portáveis...

// Função principal
int main(void)
//...

Evite esse tipo de comentário. É sabido que main é a função principal. No fundo seu programa não tem um único comentário sobre o que ou porque está fazendo, apenas essas coisas meio que óbvias

Não use acentos em comentários. Não acrescentam nada e podem não sair na tela ou na impressão

// Prototipação
void arvore_insere(int pai, char dado, int lado);
int  arvore_procura(char dado);
void menu_mostrar(void);
void preOrdem(struct str_no* raiz);