How to print binary/generic trees using C?

Question

I am suffering with the following problem: I want to print in the terminal the "drawing" of a tree.

The algorithm I’m working on is based on a stack. In this stack, I insert values(string or integer) and 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 a line, it would be something like: ((5 + 2) - (3 * 1)).

In this example we have as root the operation "-", as children the operations "+" and "*" 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 cell 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 attempt at printing:

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 spacing.

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

PS2.: Only binary trees are generated at first, but in the future I’d like to add methods that simplify accounts and make the tree generic.

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

Answer 1

In the book "Algorithms in C" Sedgewick has a very interesting form (and very similar to what you want to print trees (of any type, but particularized for binary trees). With small changes you put 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);
}

Answer 2

I found this code here in Stackoverflow. It’s still vertical, but it’s already stylized:

#include <stdio.h>

#define espaco 5


typedef struct no{
   int valor;          // valor of the no
   struct no *esquerda;  // esquerda no
   struct no *direita; // direita no
}no;

//secondary function
void desenha_arvore_horiz(no *arvore, int depth, char *path, int direita)
{
    // stopping condition
    if (arvore== NULL)
        return;

    // increase spacing
    depth++;

    // start with direita no
    desenha_arvore_horiz(arvore->direita, depth, path, 1);

    // set | draw map
    path[depth-2] = 0;

    if(direita)
        path[depth-2] = 1;

    if(arvore->esquerda)
        path[depth-1] = 1;

    // print root after spacing
    printf("\n");

    for(int i=0; i<depth-1; i++)
    {
      if(i == depth-2)
          printf("+");
      else if(path[i])
          printf("|");
      else
          printf(" ");

      for(int j=1; j<espaco; j++)
      if(i < depth-2)
          printf(" ");
      else
          printf("-");
    }

    printf("%d\n", arvore->valor);

    // vertical espacors below
    for(int i=0; i<depth; i++)
    {
      if(path[i])
          printf("|");
      else
          printf(" ");

      for(int j=1; j<espaco; j++)
          printf(" ");
    }

    // go to esquerda no
    desenha_arvore_horiz(arvore->esquerda, depth, path, 0);
}

//primary fuction
void draw_arvore_hor(no *arvore)
{
    // should check if we don't exceed this somehow..
    char path[255] = {};

    //initial depth is 0
    desenha_arvore_horiz(arvore, 0, path, 0);
}



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

int main()
{
  n1.valor = 1;
  n2.valor = 2;
  n3.valor = 3;
  n4.valor = 4;
  n5.valor = 5;
  n6.valor = 6;
  n7.valor = 7;

  n1.direita = &n2;
  n1.esquerda = &n3;
  //n2.direita = &n4;
  //n2.esquerda = &n5;
  n3.direita = &n6;
  n3.esquerda = &n7;

  n2.direita = &n3;
  n2.esquerda = &n3;

  draw_arvore_hor(&n1);
  getchar();

  return 0;
}