How to print binary/generic trees using C?

Question:

I'm suffering with the following problem: I want to print the "drawing" of a tree on the terminal.

The algorithm I'm working on is based on a stack. In this stack, I'm inserting values ​​(string or integer) and I have the following commands: add, sub, mult and div. These commands take the 2 values ​​that are at the top of the stack and create a tree with the operation, where the root of the tree is the operation and the children are the values.

I can print them on one line, it would be something like: ((5 + 2) – (3 * 1)).

In this example we have the operation "-" as the root, the operations "+" and "*" as children, and as children of addition, 2 and 5, and children of multiplication, 3 and 1.

But I would also like to print "graphically". On the console would come out something like:

           |-|
            |
    |+|-----------|*|
     |             |
|2|-----|5|   |3|-----|1|

The structure of my stack is as follows:

struct T;

typedef struct Temp {
    char *data;
    struct Temp *next;
    struct T *firstChild;
} Node;

typedef struct T {
    struct T *next;
    Node *child;
} SonNode;

And this is my print attempt:

void treeAux( Node *n, int tam ) {
    if ( n == NULL ) return;
    if ( n == top || n->firstChild == NULL ) addChar(tam, ' ');
    printf("|%s|", n->data);
    if ( n->firstChild == NULL ) return;
    printf("\n");
    addChar( tam+1, ' ');
    printf("|\n");
    SonNode *f = n->firstChild;
    while ( f != NULL ) {
        if ( f != n->firstChild ) addChar(5, '-');
        treeAux( f->child, (int)tam/2 + 6);
        if ( f->next == NULL ) return;
        f = f->next;
    }
}

void tree() {
    treeAux( top, 20 );
}

The main problem I'm having is how to control the spacings.

PS.: Top is a reference to the top of the stack. In this case, it would be a Node.

PS2.: At first only binary trees are generated, but in the future I would like to add methods that simplify accounts and that would make the tree generic.

PS3.: The addChar method simply adds the character passed as parameter so many times, without breaking the line at the end.

Answer:

In Sedgewick's book "Algorithms in C" there is a very interesting way (and very similar to what you want to print trees (of any type, but particularized for binary trees). With small changes you can put it in the format you want.

// A função mostraArvore faz um desenho esquerda-direita-raiz // da árvore x. O desenho terá uma margem esquerda de // 3b espaços. void mostraArvore(Arv* a, int b) { if (a == NULL) { imprimeNo('*', b); return; } mostraArvore(a->dir, b+1); imprimeNo(a->info, b); mostraArvore(a->esq, b+1); } // A função auxiliar imprimeNo imprime o caracter // c precedido de 3b espaços e seguido de uma mudança // de linha. void imprimeNo(char c, int b) { int i; for (i = 0; i < b; i++) printf(" "); printf("%c\n", c); }

Scroll to Top