cpppro

Printing Binary Trees in Ascii

In C Tidbits, Data Structures in C/C++ on December 21, 2007 at 8:14 pm

Here we are not going to discuss what binary trees are (please refer this, if you are looking for binary search trees), or their operations but printing them in ascii.

The below routine prints tree in ascii for a given Tree representation which contains list of nodes, and node structure is this

struct Tree
{
  Tree * left, * right;
  int element;
};

This pic illustrates what the below routine does on canvas..
ascii tree

Here is the printing routine..

//prints ascii tree for given Tree structure
void print_ascii_tree(Tree * t)
{
  asciinode *proot;
  int xmin, i;
  if (t == NULL) return;
  proot = build_ascii_tree(t);
  compute_edge_lengths(proot);
  for (i=0; iheight && i < MAX_HEIGHT; i++)
  {
    lprofile[i] = INFINITY;
  }
  compute_lprofile(proot, 0, 0);
  xmin = 0;
  for (i = 0; i height && i < MAX_HEIGHT; i++)
  {
    xmin = MIN(xmin, lprofile[i]);
  }
  for (i = 0; i height; i++)
  {
    print_next = 0;
    print_level(proot, -xmin, i);
    printf("\n");
  }
  if (proot->height >= MAX_HEIGHT)
  {
    printf("(This tree is taller than %d, and may be drawn incorrectly.)\n",
           MAX_HEIGHT);
  }
  free_ascii_tree(proot);
}

Auxiliary routines..

//This function prints the given level of the given tree, assuming
//that the node has the given x cordinate.
void print_level(asciinode *node, int x, int level)
{
  int i, isleft;
  if (node == NULL) return;
  isleft = (node->parent_dir == -1);
  if (level == 0)
  {
    for (i=0; ilablen-isleft)/2)); i++)
    {
      printf(" ");
    }
    print_next += i;
    printf("%s", node->label);
    print_next += node->lablen;
  }
  else if (node->edge_length >= level)
  {
    if (node->left != NULL)
    {
      for (i=0; iright != NULL)
    {
      for (i=0; ileft,
                x-node->edge_length-1,
                level-node->edge_length-1);
    print_level(node->right,
                x+node->edge_length+1,
                level-node->edge_length-1);
  }
}

//This function fills in the edge_length and
//height fields of the specified tree
void compute_edge_lengths(asciinode *node)
{
  int h, hmin, i, delta;
  if (node == NULL) return;
  compute_edge_lengths(node->left);
  compute_edge_lengths(node->right);

  /* first fill in the edge_length of node */
  if (node->right == NULL && node->left == NULL)
  {
    node->edge_length = 0;
  }
  else
  {
    if (node->left != NULL)
    {
      for (i=0; ileft->height && i left, 0, 0);
      hmin = node->left->height;
    }
    else
    {
      hmin = 0;
    }
    if (node->right != NULL)
    {
      for (i=0; iright->height && i right, 0, 0);
      hmin = MIN(node->right->height, hmin);
    }
    else
    {
      hmin = 0;
    }
    delta = 4;
    for (i=0; ileft != NULL && node->left->height == 1) ||
	      (node->right != NULL && node->right->height == 1))&&delta>4)
    {
      delta--;
    }

    node->edge_length = ((delta+1)/2) - 1;
  }

  //now fill in the height of node
  h = 1;
  if (node->left != NULL)
  {
    h = MAX(node->left->height + node->edge_length + 1, h);
  }
  if (node->right != NULL)
  {
    h = MAX(node->right->height + node->edge_length + 1, h);
  }
  node->height = h;
}
asciinode * build_ascii_tree_recursive(Tree * t)
{
  asciinode * node;

  if (t == NULL) return NULL;

  node = malloc(sizeof(asciinode));
  node->left = build_ascii_tree_recursive(t->left);
  node->right = build_ascii_tree_recursive(t->right);

  if (node->left != NULL)
  {
    node->left->parent_dir = -1;
  }

  if (node->right != NULL)
  {
    node->right->parent_dir = 1;
  }

  sprintf(node->label, "%d", t->element);
  node->lablen = strlen(node->label);

  return node;
}

//Copy the tree into the ascii node structre
asciinode * build_ascii_tree(Tree * t)
{
  asciinode *node;
  if (t == NULL) return NULL;
  node = build_ascii_tree_recursive(t);
  node->parent_dir = 0;
  return node;
}

//Free all the nodes of the given tree
void free_ascii_tree(asciinode *node)
{
  if (node == NULL) return;
  free_ascii_tree(node->left);
  free_ascii_tree(node->right);
  free(node);
}

//The following function fills in the lprofile array for the given tree.
//It assumes that the center of the label of the root of this tree
//is located at a position (x,y).  It assumes that the edge_length
//fields have been computed for this tree.
void compute_lprofile(asciinode *node, int x, int y)
{
  int i, isleft;
  if (node == NULL) return;
  isleft = (node->parent_dir == -1);
  lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2));
  if (node->left != NULL)
  {
    for (i=1; i edge_length && y+i left, x-node->edge_length-1, y+node->edge_length+1);
  compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}

void compute_rprofile(asciinode *node, int x, int y)
{
  int i, notleft;
  if (node == NULL) return;
  notleft = (node->parent_dir != -1);
  rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2));
  if (node->right != NULL)
  {
    for (i=1; i edge_length && y+i left, x-node->edge_length-1, y+node->edge_length+1);
  compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}

Here is the asciii tree structure…

struct asciinode_struct
{
  asciinode * left, * right;

  //length of the edge from this node to its children
  int edge_length;

  int height;

  int lablen;

  //-1=I am left, 0=I am root, 1=right
  int parent_dir;

  //max supported unit32 in dec, 10 digits max
  char label[11];
};

Please refer reference code for collection of posts in data structures

[note: I'd used msvc6 (which is a bit old one), so when you use new compilers you may get few compilations errors, fix them yourself or drop a msg over here..]

About these ads
  1. Thx 4ever

  2. quick and dirty (but working) java version is here: http://pastebin.com/fd713b9f

  3. and i forgot to thank you, man:)

  4. Here you can find a Linux port of this program (compiled fine with GCC 4.3.3). I’ve also split binary tree routines and ascii drawing into separate .c files. Makefile included, just type ‘make’ :)

    http://tfsoft.org.ua/downloads/ascii_bt_linux.tar.gz

  5. thanks a lot… it really helped… :)

  6. how can i compile these without main function?

  7. Hi Thanks my friend….
    Thank you very much…..
    These programs are helping me very much…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: