Printing a Binary Tree

[basukinjal]

Ive made my binary tree in the following format

typedef struct node
{	int info;
	struct node *left;
	struct node *right;
}*nodeptr;

Im looking for a function that will accept the root pointer and print the tree in a graphical format.
for eg.
i want the output to be
_____5
_____/\
____3__7
____/__/\
___2__6_8
_________\
__________9
How can i get such and output (without the underscores .. given only because spaces cannot be detected.)
Please Help!!

[Salem]

Some ideas:
1. measure the depth of the tree, so you know how much to indent the root node
2. as you recursively print it, going left decrements the current indent, and going right increments it.

[Narue]

If you don't mind a 90 degree rotation, I use this for printing the structure of a tree because it's fast and easy:

void padding ( char ch, int n )
{
  int i;

  for ( i = 0; i < n; i++ )
    putchar ( ch );
}

void structure ( struct node *root, int level )
{
  int i;

  if ( root == NULL ) {
    padding ( '\t', level );
    puts ( "~" );
  }
  else {
    structure ( root->right, level + 1 );
    padding ( '\t', level );
    printf ( "%d\n", root->info );
    structure ( root->left, level + 1 );
  }
}

int main ( void )
{
  struct node *tree = NULL;

  /* ... */

  structure ( tree, 0 );

  /* ... */
}

[dv1r]

and how would it be done with out the 90 degree turn??
iv been trying and i always get the hole left side then the hole right and its all messed up =\

[MosaicFuneral]

Well this forum is pretty much expired, but you're only confused because of that bong, Towlie[dv1r].

[Salem]

> iv been trying and i always get the hole left side then the hole right and its all messed up
I suppose we could all trot over to www.crystal-ball-programming-network.com and hold a mass "ummmmmm" seance to determine what your code might look like.

Alternatively, just post it here with your test case and get a pretty fast and accurate analysis of the problem(s).

You must have managed to do something in the last 4 months.

[dv1r]

i know whats wrong but im confused of how to solve it...
(with out a global or static...)

void printtreeright(nodeptr t)
{
  int i=getheight(t),j;
  if(t)
  {
  for(j=0;j<i;j++)
  {
   printf("      ");
  }
  printf("%d",t->info);
  printtreeright(t->left);
  printtreeright(t->right);
  printf("\n");
  }
}//EOF

[Murtan]

So what are the 'given' parameters for the tree?

Are all values in the tree guaranteed to be single digits?

Is there a maximum depth limit?

Ok, let me work this out 'on paper' so I understand it:

{Note that spaces are preserved inside code tags.}

Tree with 3 nodes, one L and one R from the root:

B
 / \
A    C

Seems easy enough...

Lets expand the tree by another complete row:

D
   / \
  B   F
 / \ / \
A   C   G

Oops...There is supposed to be a C and an E where the C is...

How do I re-format this to make room for it? Does this work?

D
    / \
  B     F
 / \   / \
A   C E   G

or do I need to add the extra vertical line to keep the lines pretty?

D
    / \
   /   \
  B     F
 / \   / \
A   C E   G

Lets expand it another row:

H 
          / \
     D           L
    / \         / \
  B     F     J     N
 / \   / \   / \   / \
A   C E   G I   K M   O

That looks pretty strange, but maybe we could live with it as it only has one row of 'lines' for every row of data.

If you have to add the extra rows to make the lines pretty, you end up with more rows to get the horizontal motion you need:

H 
          / \
         /   \
        /     \
       /       \
      /         \
     D           L
    / \         / \
   /   \       /   \
  B     F     J     N
 / \   / \   / \   / \
A   C E   G I   K M   O

It would appear that plotting an 'arbitrary' binary tree (in character graphics) is non-trivial even if character positions are limited to single digits / characters.

When I was building the desired output by hand, I started from the bottom of the tree as it sets the 'required width' for the tree. Note that if you have values that aren't in the tree, you would have to replace them with their 'space' equivalent and somehow suppress the 'line' that would otherwise be drawn.

If you end up using the tree's maximum depth to calculate the maximum width for the bottom row, does the solution still lend itself to a recursive implementation?

[dv1r]

i don't want to add extra lines or make it gritty i don't mind it being like this

H 
          / \
     D           L
    / \         / \
  B     F     J     N
 / \   / \   / \   / \
A   C E   G I   K M   O

i just cant seen to figure it out =\

[Narue]

>i just cant seen to figure it out =\
Liar. You did it manually, so clearly you figured it out. Now you need to break what you did manually into clear and precise steps so you can tell the computer how to do it.

This is a very strict structure, I find it hard to believe that you can't see any patterns for formalizing how to display it. I imagine you've gone through enough tree theory to understand how to find the height of a tree and be able to traverse it level by level as well. Those basic concepts and an understanding of the patterns the structure creates is enough to do what you want in a natural way.

[Murtan]

If you want to use a recursive algorithm, I think you will have to pre-define the entire output area as a grid to allow the left and right sides random access to the output space. Then when the recursion calls are complete, you output the grid.

To be able to 'output as you go' you will need to use a non-recursive algorithm as you need to traverse the tree by depth.

In either case, the width of the output will be determined by the depth of the tree and the output size of the elements in the tree. (One character or more?)

Once you determine the width, the root node is 'centered' on the width.
Then at each lower level, the new 'top' node is 'centered' on its half of the previous width.

With single character outputs, a 1 depth (root only) tree is 1 wide, a 2 depth tree is 5 wide, a 3 depth tree is 11 wide and a 4 depth tree is 23 wide.

So in the output tree, there are 11 spaces in front of the H
Split 23 into 2 halves of 11 each and there are 5 spaces in front of the D. Split 11 into 2 halves of 5 each and there are 2 spaces in front of the B.

Thoughts on a recursive implementation:

A 4 depth tree, needs 23 width and 7 rows.

We could declare a 2 dimensional array: char outbuf[7][24]; but passing those around is a little hard as the 24 part has to be hard-coded.

Alternatively, we could declare a single dimentional array (or allocate it...hmm) and a 'next row' offset.

At each recursion level, we would need to pass the buffer, next row offset, width for this node, offset into the buffer for this node, the node

The node would put its value where indicated.

If the node had a left child, the node would add the '/' character one row down, one column left, calculate the width and offset for the left and recurse.

If the node had a right child, the node would add the '\' character one row down, one column right, calculate the width and offset for the rigth and recurse.

If you like the idea in principle, give it a try and see how you do.

[costica1]

I think that a good idea is to transform the tree into it’s nodes’ vector key and complete this with NULLs values until a full binary tree (total of 2^H – 1 values). Then read this vector value after value, first value is the level one, next two values are the second level, next four values are the third level and so on. The only aspect that has to be implemented is the aligning that with some effort can be accomplish. The snapshot of code is below.

typedef struct _TREE_NODE
{
	_TREE_NODE* left;
	_TREE_NODE* right;
	int value;
	_TREE_NODE(): left(NULL), right(NULL), value(0){};
	_TREE_NODE(int val): left(NULL), right(NULL), value(val){};
} TREE_NODE, *PTREE;


int height(TREE_NODE* tree)
{
	if(!tree)
		return 0;
	else
	{
		int left  = height(tree->left);

		int right = height(tree->right);

		if(left >= right)
			return left + 1;
		else
			return right + 1;
	}
}

deque<TREE_NODE*> d;
void print(TREE_NODE* tree)
{
	if(tree)
	{
		int H = height(tree);
		int dimension = (int)(pow((float)2, H) - 1);
		vector<int> nodes(dimension, -1); // the vector with all nodes, total 2^H -1, 
		                                  // the full binary tree with unused nodes with value -1
		nodes[0] = tree->value;
		d.push_back(tree);
		while(!d.empty())
		{
			TREE_NODE* current = d.front();
			d.pop_front();

			int position;
			for(int pos = 0; pos < nodes.size(); pos++)
				if(nodes[pos] == current->value)
					position = pos;

			if(current->left)
			{
				nodes[2 * position + 1] = current->left->value;
				d.push_back(current->left);
			}
			if(current->right)
			{
				nodes[2 * position + 2] = current->right->value;
				d.push_back(current->right);
			}
		}
		for(int n = 0; n < dimension; n++)
		{
			if(nodes[n] != -1)
				cout << "[" << setw(4) << nodes[n] << "] ";
			else
			   cout << "[NULL] ";
			if(!((n + 2) & (n + 1))) //test wheather n + 1 is power of 2
				cout << endl; 
		}
	}
}

[steve.lorimer]

It's been a while since anyone posted to this, but for completeness' sake I thought I'd post a working solution.

I found that it was relatively trivial if you calculate the padding offset required before each node and add it on either side of the node.

That is, let's say the offset is 4, then to print a node x, the following is printed:

....x....

My solution does require a supplementary data structure to store the current node's depth within the tree (this because if you're working with an incomplete tree a given sub-tree's depth may not be consistent with it's depth in the full tree.

Working solution below:

#include <iostream>
#include <utility>
#include <algorithm>
#include <list>

namespace tree {

template<typename T>
struct node
{
  T data;
  node* l;
  node* r;
  node(T&& data_ = T()) : data(std::move(data_)), l(0), r(0) {}
};

template<typename T>
int max_depth(node<T>* n)
{
  if (!n) return 0;
  return 1 + std::max(max_depth(n->l), max_depth(n->r));
}

template<typename T>
void prt(node<T>* n)
{
  struct node_depth
  {
    node<T>* n;
    int lvl;
    node_depth(node<T>* n_, int lvl_) : n(n_), lvl(lvl_) {}
  };

  int depth = max_depth(n);

  char buf[1024];
  int last_lvl = 0;
  int offset = (1 << depth) - 1;

  // using a queue means we perform a breadth first iteration through the tree
  std::list<node_depth> q;

  q.push_back(node_depth(n, last_lvl));

  while (q.size())
  {
    const node_depth& nd = *q.begin();

    // moving to a new level in the tree, output a new line and calculate new offset
    if (last_lvl != nd.lvl)
    {
      std::cout << "\n";

      last_lvl = nd.lvl;
      offset = (1 << (depth - nd.lvl)) - 1;
    }

    // output <offset><data><offset>
    if (nd.n)
      sprintf(buf, " %*s%d%*s", offset, " ", nd.n->data, offset, " ");
    else
      sprintf(buf, " %*s", offset << 1, " ");
    std::cout << buf;

    if (nd.n)
    {
      q.push_back(node_depth(nd.n->l, last_lvl + 1));
      q.push_back(node_depth(nd.n->r, last_lvl + 1));
    }

    q.pop_front();
  }
}

}

int main()
{
  typedef tree::node<int> node;
  node* head = new node();
  head->l    = new node(1);
  head->r    = new node(2);
  head->l->l = new node(3);
  head->l->r = new node(4);
  head->r->l = new node(5);
  head->r->r = new node(6);

  tree::prt(head);
  
  return 0;
}