How to print binary / generic trees using C?

Question

How to print binary / generic trees using C?

Navigation

#1 by (1 votes)
#2 by (0 votes)

3

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

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 tree root is the operation and the children are the values.

I can print them in a line, it would look 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 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 here is my attempt to print:

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

PS: Top is a reference to the top of the stack. In 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 make the tree generic.

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

c

asked by anonymous 25.05.2017 / 04:09

2 answers

Clear blanks of an array How to use CreateView

score 1 · Answer 1

In Sedgewick's book "Algorithms in C" it has a very interesting (and very similar to what you want to print trees (of any kind, but particularized to 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);
}

score 0 · Answer 2

I found this code here in StackOverflow. It's still vertical, but it's already more 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;
}