Ir ao conteúdo
  • Cadastre-se
Entre para seguir isso  
Henrique Yoshiaki

Erro em código que funciona-arvore

Recommended Posts

Boa noite, o código a seguir funciona com diversos testes que eu fiz, porém, ao enviar ao judge ele informa que o meu programa não passou em nenhum teste, por favor, poderiam me ajudar?

O programa escaneia um número n de nós, sendo que 0<n<31;

nas próximas n linhas, o programa escaneia três int, sendo o primeiro um identificador do nó, o segundo o identificador da sub árvore esquerda e o terceiro o identificador da sub árvore direita.

Eu devo no final, printar em ordem crescente de cada identificador as seguntes informações: o pai, o irmão, o grau, o nível, a altura e o tipo do nó( que pode ser, raiz, interno ou folha), semelhante ao exemplo à seguir:

"0: pai = 3, irmão = 4, grau = 2, nivel = 1, altura = 1, interno"

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

typedef struct {
    int id, esq, dir, pai, nivel, grau, altura;
}No;

typedef struct{
    int raiz, N;
    No *Nos;
}Arvore;

void CriarArv(Arvore *A, int n){
    A->Nos=malloc(n*sizeof(No));
}

void InsereNo(Arvore *A, int id, int esq, int dir){
    A->Nos[id].id=id;
    A->Nos[id].esq=esq;
    A->Nos[id].dir=dir;
    if (esq != -1) A->Nos[esq].pai=id;
    if (dir != -1) A->Nos[dir].pai=id;
}

void EncontraRaiz(Arvore *A){
    int i;
    for (i=0; i<A->N; i++){
        if(A->Nos[i].pai==-1 && A->Nos[i].id!=-1){
            A->raiz=i;
            A->Nos[i].pai=-1;
            break;
        }
    }
}

int max(int a, int b){
    if (a==b) return a;
    else if (a>b) return a;
    else return b;
}

int detAltura(Arvore *A, int id, int nivel){
    if (id == -1) return -1;

    if (A->Nos[id].esq==-1 && A->Nos[id].dir==-1) A->Nos[id].grau=0;
    else if (A->Nos[id].esq!=-1 && A->Nos[id].dir!=-1) A->Nos[id].grau=2;
    else if (A->Nos[id].esq!=-1 || A->Nos[id].dir!=-1) A->Nos[id].grau=1;

    A->Nos[id].nivel=nivel;
    A->Nos[id].altura = max(detAltura(A, A->Nos[id].esq, nivel+1), detAltura(A, A->Nos[id].dir, nivel+1)) + 1;
}

int EncontraIrmao(Arvore *A, int id){
    if (A->Nos[id].pai==-1) return -1;
    if (A->Nos[A->Nos[id].pai].esq == id) return A->Nos[A->Nos[id].pai].dir;
    if (A->Nos[A->Nos[id].pai].dir == id) return A->Nos[A->Nos[id].pai].esq;
}

char* defineTipo(Arvore *A, int id){
    static char tipo[10];
    if (A->Nos[id].pai==-1) strcpy(tipo, "raiz");

    else if (A->Nos[id].esq==-1 && A->Nos[id].dir==-1) strcpy(tipo, "folha");

    else strcpy(tipo, "interno");
    return tipo;
}

void iniciarTudo(Arvore *A, int n){
    int i = 0;
    for (i=0;i<n; i++){
        A->Nos[i].pai=-1;
        A->Nos[i].dir=-1;
        A->Nos[i].esq=-1;
        A->Nos[i].id=-1;
        A->Nos[i].grau=0;
        A->Nos[i].altura=0;
        A->Nos[i].nivel=0;
    }
}

int main(){
    int i, n, a, dir, esq, salva1;
    char salva2[10];
    Arvore ab;
    scanf(" %d", &n);
    CriarArv(&ab, 31);
    ab.N=31;
    iniciarTudo(&ab, 31);
    for (i=0; i<n; i++){
        scanf(" %d %d %d", &a, &esq, &dir);
        InsereNo(&ab, a, esq, dir);
    }
    EncontraRaiz(&ab);
    ab.Nos[ab.raiz].altura=detAltura(&ab, ab.raiz, 0);

    for (i=0; i<31; i++){
            salva1=EncontraIrmao(&ab, i);
            strcpy(salva2, defineTipo(&ab, i));
        if(ab.Nos[i].id!=-1){
            printf("%d: pai = %d, irmão = %d, grau = %d, nivel = %d, altura = %d, %s\n", i, ab.Nos[i].pai, salva1, ab.Nos[i].grau, ab.Nos[i].nivel, ab.Nos[i].altura, salva2);
        }
    }
    return 0;
}

Obrigado desde já.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora
Entre para seguir isso  





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×