How to print tree with indentation proportional to the depth of the node in C?

Question

I need to adjust this code so that the tree is printed with margin indentation proportional to the node depth, and that it prints a character ' - ' to represent each NULL. Anyone can help?

If I have not explained right and someone wants to see what the question asks, is on this link, exercises 3, question 3: https://www.ime.usp.br/~pf/algorithms/classes/bint.html

This is the statement of the exercise:

3. Write a function that prints the contents of each node of a binary tree with margin indentation proportional to the depth of the node. Follow an example of a tree and its representation (the characters '-' represent NULL):

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

Just follow my code:

#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;
}

Answer 1

Your algorithm is much more complicated than it should be. You don’t need to path nor dir.

In particular, take a look at this:

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

It turns out that whatever happens, the result is the same: printf(" ");. That means that the if, else if and else then they’re no use at all.

When a node is visited, what happens is, exactly in that order, that:

1. The node number is shown.
2. The subtree on the left is shown.
3. The right subtree is shown.

You are trying to draw the right subtree before the left subtree. That alone makes your algorithm go crazy.

Also, the nodes you have defined are not the same that are given in the exercise statement. And remember that the childless knots must have the pointers esquerda and direita pointing to NULL preventing them from pointing to memory junk.

Your corrected algorithm is as follows. The code should be simple enough to dispense with further explanations:

#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;
}

Output produced is expected:

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

See here working on ideone.