2

Preciso ajustar esse código para que a árvore seja impressa com recuo de margem proporcional à profundidade do nó, e que imprima um caractere ' - ' para representar cada NULL. Alguém pode ajudar?

Caso eu não tenha explicado direito e alguém queira ver o que a questão pede, está nesse link, exercícios 3, questão 3: https://www.ime.usp.br/~pf/algoritmos/aulas/bint.html

Eis o enunciado do exercício:

3. Escreva uma função que imprima o conteúdo de cada nó de uma árvore binária com recuo de margem proporcional à profundidade do nó. Segue um exemplo de árvore e sua representação (os caracteres '-' representam NULL):

         555                555       
       /     \                 333    
                                  111 
    333       888                    -
   /   \         \                   -
 111   444       999              444 
                                     -
                                     -
                               888    
                                  -   
                                  999 
                                     -
                                     -

Segue o meu código:

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

typedef struct noh{
    int valor;
    struct noh *esquerda;
    struct noh *direita;
}no;

void desenha(no *arvore, int depth, char *path, int dir){
    int i, j;
    if (arvore == NULL)
        return;
    depth++;
    desenha(arvore->direita, depth, path, 1);
    path[depth-2] = 0;
    if(dir)
        path[depth-2] = 1;
    if(arvore->esquerda)
        path[depth-1] = 1;
    for(i=0; i<depth-1; i++){
        if(i == depth-2)
            printf(" ");
        else if(path[i])
            printf(" ");
        else
            printf(" ");
        for(j=1; j<depth; j++)
            if(i < depth-2)
                printf(" ");
        else
            printf(" ");
    }
    printf("%d\n", arvore->valor);
    for(i=0; i<depth; i++){
        if(path[i])
            printf(" ");
        else
            printf(" ");
        for(j=1; j<depth; j++)
            printf(" ");
    }
    desenha(arvore->esquerda, depth, path, 0);
}

void arvbin(no *arvore){
    char path[255] = {};
    desenha(arvore, 0, path, 0);
}

no n1, n2, n3, n4, n5, n6;

int main(){
    n1.valor = 444;
    n2.valor = 333;
    n3.valor = 999;
    n4.valor = 555;
    n5.valor = 111;
    n6.valor = 888;
    n1.direita = &n2;
    n1.esquerda = &n3;
    n2.direita = &n4;
    n2.esquerda = &n5;
    n3.direita = &n6;
    arvbin(&n1);
    return 0;
}

1 Resposta 1

3

O seu algoritmo está muito mais complicado do que deveria ser. Você não precisa de path e nem de dir.

Em especial, dê uma olhada nisso:

    if(i == depth-2)
        printf(" ");
    else if(path[i])
        printf(" ");
    else
        printf(" ");

Ocorre que qualquer que seja o caso que aconteça, o resultado é o mesmo: printf(" ");. Isso significa que o if, else if e else nesse caso não servem para nada.

Quando um nó é visitado, o que ocorre é, exatamente nessa ordem, isso:

  1. O número do nó é mostrado.
  2. A subárvore da esquerda é mostrada.
  3. A subárvore da direita é mostrada.

Você está tentando desenhar a subárvore da direita antes da subárvore da esquerda. Só isso já faz o seu algoritmo ficar maluco.

Além disso, os nós que você definiu não são os mesmos que são dados no enunciado do exercício. E lembre-se que os nós sem filhos devem ter os ponteiros esquerda e direita apontando para NULL evitando que apontem para lixo de memória.

Seu algoritmo corrigido é o que se segue. O código deve ser suficientemente simples para dispensar maiores explicações:

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

typedef struct noh {
    int valor;
    struct noh *esquerda;
    struct noh *direita;
} no;

void espacos(int depth) {
    while (depth) {
        printf("   ");
        depth--;
    }
}

void desenha(no *arvore, int depth) {
    espacos(depth);
    if (arvore == NULL) {
        printf("-\n");
        return;
    }
    printf("%d\n", arvore->valor);
    desenha(arvore->esquerda, depth + 1);
    desenha(arvore->direita, depth + 1);
}

void arvbin(no *arvore) {
    desenha(arvore, 0);
}

int main() {
    no n1, n2, n3, n4, n5, n6;
    n1.valor = 555;
    n2.valor = 333;
    n3.valor = 888;
    n4.valor = 111;
    n5.valor = 444;
    n6.valor = 999;
    n1.esquerda = &n2;
    n1.direita = &n3;
    n2.esquerda = &n4;
    n2.direita = &n5;
    n3.esquerda = NULL;
    n3.direita = &n6;
    n4.esquerda = NULL;
    n4.direita = NULL;
    n5.esquerda = NULL;
    n5.direita = NULL;
    n6.esquerda = NULL;
    n6.direita = NULL;
    arvbin(&n1);
    return 0;
}

A saída produzida é a esperada:

555
   333
      111
         -
         -
      444
         -
         -
   888
      -
      999
         -
         -

Veja aqui funcionando no ideone.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .