How to print out a binary tree

See this question for an explanation:
    http://www.experts-exchange.com/Programming/Algorithms/Q_25014702.html

And this follow-up question adds color to the tree:
     http://www.experts-exchange.com/Programming/Languages/CPP/Q_25031661.html

what about a horizontal output ?

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

Select all Open in new window

you could use inorder traversal and could compute each line shape (offsets and bars) from item level, tree depth and previous nodes.

Sara

Sorry everyone,  the program lets the user enter in an infix expression.  Then the program converts the equation to a postfix equation using stacks.  Finally, the program puts the postfix expression into a binary tree.  So the equation is already in postfix equation I just want to figure out how to take the expression and print it out in the tree format.  I have to create a function print_tree() but it does not print out the entire tree.

 

template<class object>
void BinaryNode<object>::print_tree(BinaryNode<object> *tree, int size)
	{
		
		size *= 2;
		int left_size = size - 2;
		int right_size = size + 2;
		
		

	if(tree == NULL)
		return;
	
	cout<<setfill(' ')<<setw(size);
	cout<<*tree->data<<endl;
	
	
	if(tree->left!= NULL)
	{
		 
		cout<<setfill(' ')<<setw(size);
		cout<<"/"<<endl;
		cout<<setfill(' ')<<setw(left_size);
		print_tree(tree->left, left_size);
		
	}

	
	else if(tree->right != NULL)
	{
		 
		cout<<setfill(' ')<<setw(size);
		cout<<"'\'"<<endl;
		cout<<setfill(' ')<<setw(right_size);
		print_tree(tree->right, right_size);
		
		
	}
		
}

Select all Open in new window

At a given depth, you may have to print out in a single line 2^k symbols. That means that you are going to have to obtain all the nodes at a given depth. After printing that line, increment depth by one and do this again until you have reached the max depth.

 either need horizontial output using in-order traversal or vertical output using level-traversal.

or you print to a char 2d-array in memory where you can move up in rows when necessary.  

I have to build the tree from the bottom up so how would I handle the spacing and placement of each node for in-order traversal or for the 2-d array?

1) >> I am trying to figure out how can I print a binary tree
My understanding of the question is that you already have an Expression Binary Tree filled in (based on some input string, which no longer matters at this point).

2) >> I have to build the tree from the bottom
But wait, this implies that you are still trying to figure out how to build a tree. Now, I don't really know which problem you are trying to attach for this particular question.

Assuming that this question is about (1),  then isn't your binary tree shown as in your OP? If so, isn't your top node '*' and it has 2 children '+' and '5'? If so, then wouldn't you want to print out the top node first?

I am sorry, I am referring to printing the tree out.  Yes I already have constructed the binary tree.  But, I just wanted to figure out how to print it out in the conceptual tree format.  My professor wants us to print the tree out starting from the depth of the tree all the way back up to the root of the entire tree.  So I was trying to figure how can I  space the deepest level of the tree and move back up and space them properly.  So that the parent nodes are align with the children nodes.

       *
      / \
     +   5
    / \
   1   3

 For example the first thing that I will print out from this tree will be the 1 and 3 .  Then, I will go up a level and print out + and 5. Finally the root will be printed.  

>> For example the first thing that I will print out from this tree will be the 1 and 3 .
Then the tree gets printed out upside down from what you have drawn. Is this what you want printed out?

   1    3
     \ /
      +  5
       \ /
        *

For formatting, I suggest that you add an extra level (or two) and at the bottom level, have one child for each node (sometimes left, sometimes right); and for the previous level, leave out at least one node, but have more than 2. This new example will then help identify the formatting issues you will encounter.

It sounds the main issue you are having with this question is traversing your input Expression Binary Tree correctly. So, after you do that, if you have trouble spacing, you can deal with that later (although you may need to keep track of some state information while traversing the tree to handle the spacing).

One thing to always keep in mind is that at each level, there are potentially 2^k nodes, some of which may not exist, but are conceptually present (and affect proper spacing accordingly). So think about that when collecting your symbols and state information.

Are all the numbers and operators a single char? If so, then the spacing becomes easier.

Yes, all of the operators are a single char.

Oh yeah I am using breadth first search to traverse through the binary tree to get the depth level of each operator.  Therefore, I have the level numbers for each node in the binary tree.  I am keeping track of the depth level of each node as well as the parent node.  Next I am going to store the values into a 2d array starting from the leaf nodes.  BTW my professor wants the tree to still be in this format.  

       *
      / \
     +   5
    / \
   1   3

The professor just wants us to start from the bottom and work our way up.  But, it must be in the above tree format.  That is why I am using a 2d array so I can start from the bottom and work my way up to the root but, printing the tree out  in the same manner.

>> That is why I am using a 2d array
Oh, I didn't see any array in your code post. Perhaps you could post your program with all the updates. If you want it to be testable by us, then include a test main driver that creates the binary tree. Don't forget to make the problem a little more involved than your OP sample or you may get somthing that works for the OP, but fails for other trees.

>> For example the first thing that I will print out from this tree will be the 1 and 3 .
Ok, then actually, this will not be the first thing you print out. Maybe you meant that this is the first pair that you save in your 2d array?

Instead of an array, you could consider using a container where each level has a different number of elements in it; maybe a vector? Then you have a ragged 2d array. The vector could even be of a pair of symbols where the pair has the same parent. But that is completely up to you.

I have not actually created the 2d array yet because I was trying to figure out how to space the elements out first.  But here is what I have

BinaryNode.h

 

#ifndef BINARYNODE_H
#define BINARYNODE_H

#include<iomanip>
#include<iostream>
#include<queue>
#include<string>

template<class object>
class BinaryNode
{
public:
	BinaryNode(object&);
	BinaryNode(BinaryNode<object> * , int );

	
	void breadth_first_search(BinaryNode<object> *);
	void spacing(char, int);

	int level;
	object *data;
	BinaryNode<object> *left;
	BinaryNode<object> *right;
};

template<class object>
BinaryNode<object>::BinaryNode(object& node)
{
	data = &node;
	left = NULL;
	right = NULL;

}

template<class object>
BinaryNode<object>::BinaryNode(BinaryNode<object> *node, int size)
{

	breadth_first_search(node);

}

template<class object>
void BinaryNode<object>::breadth_first_search(BinaryNode<object> *node)
{
	int level_count=0;

	node->level=level_count;

	queue<BinaryNode*> queue_node;

	queue_node.push(node);

	spacing('\t', node->level);
	cout<<*node->data;

	while(!queue_node.empty())
	{
		node = queue_node.front();

		if(node->left != NULL)
		{	int left_level_count =node->level;
			node->left->level = ++left_level_count;
			queue_node.push(node->left);
			spacing('\t',node->left->level);
			cout<<*node->left->data;
		}

		if(node->right != NULL)
		{
			int right_level_count = node->level;
			node->right->level = ++right_level_count;
			queue_node.push(node->right);
			spacing('\t',node->right->level);
			cout<<*node->right->data;
		}
		//cout<<*node->data<<endl;

		queue_node.pop();

	}


}

template<class object>
void BinaryNode<object>::spacing(char space, int data)
{
	for(int i = 0; i<data; i++)
		cout<<space;

}
#endif

Select all Open in new window

Stack.h

 

#ifndef STACKLI_H_
#define STACKLI_H_

#include <stdlib.h>
#include<exception>

using namespace std;

#include"BinaryNode.h"
//#include "Except.h"


// Stack class -- linked list implementation.
//
// CONSTRUCTION: with no parameters.
//
// ******************PUBLIC OPERATIONS*********************
// void push( x )        --> Insert x
// void pop( )           --> Remove most recently inserted item
// Object top( )         --> Return most recently inserted item
// Object topAndPop( )   --> Return and remove most recently inserted item
// bool isEmpty( )       --> Return true if empty; else false
// void makeEmpty( )     --> Remove all items
// ******************ERRORS********************************
// UnderflowException thrown as needed.

template <class Object>
class Stack
{
  public:
    Stack( );
    Stack( const Stack & );
    ~Stack( );

    bool isEmpty( ) const;
    const Object & top( ) const;
    void makeEmpty( );
    void pop( );
    void push( const Object & );
    Object topAndPop( );

    const Stack & operator=( const Stack & );

  private:
    struct ListNode
    {
        Object    element;
        ListNode *next;

        ListNode( const Object & theElement, ListNode * n = NULL )
          : element( theElement ), next( n ) { }
    };

    ListNode *topOfStack;
};

//#include "StackLi.cpp"


// Construct the stack.
template <class Object>
Stack<Object>::Stack( )
{
    topOfStack = NULL;
}

// Copy constructor.
template <class Object>
Stack<Object>::Stack( const Stack<Object> & rhs )
{
    topOfStack = NULL;
    *this = rhs;
}


template<>
Stack<BinaryNode<char>*>::Stack()
{
	topOfStack = NULL;

}

// Destructor.
template <class Object>
Stack<Object>::~Stack( )
{
    makeEmpty( );
}

// Test if the stack is logically empty.
// Return true if empty, false, otherwise.
template <class Object>
bool Stack<Object>::isEmpty( ) const
{
    return topOfStack == NULL;
}

// Make the stack logically empty.
template <class Object>
void Stack<Object>::makeEmpty( )
{
    while( !isEmpty( ) )
        pop( );
}

// Return the most recently inserted item in the stack.
// or throw an UnderflowException if empty.
template <class Object>
const Object & Stack<Object>::top( ) const
{
    //if( isEmpty( ) )
        //throw UnderflowException( );
    return topOfStack->element;
}



// Remove the most recently inserted item from the stack.
// Throw Underflow if the stack is empty.
template <class Object>
void Stack<Object>::pop( )
{
   // if( isEmpty( ) )
       // throw UnderflowException( );

    ListNode *oldTop = topOfStack;
    topOfStack = topOfStack->next;
    delete oldTop;
}

// Return and remove the most recently inserted item
// from the stack.
template <class Object>
Object Stack<Object>::topAndPop( )
{
    Object topItem = top( );
    pop( );
    return topItem;
}

// Insert x into the stack.
template <class Object>
void Stack<Object>::push( const Object & x )
{
    topOfStack = new ListNode( x, topOfStack );
}

// Deep copy.
template <class Object>
const Stack<Object> & Stack<Object>::operator=( const Stack<Object> & rhs )
{
    if( this != &rhs )
    {
        makeEmpty( );
        if( rhs.isEmpty( ) )
            return *this;

        ListNode *rptr = rhs.topOfStack;
        ListNode *ptr  = new ListNode( rptr->element );
        topOfStack = ptr;

        for( rptr = rptr->next; rptr != NULL; rptr = rptr->next )
            ptr = ptr->next = new ListNode( rptr->element );
    }
    return *this;
}



#endif

Select all Open in new window

Main.cpp

 

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<iterator>
#include<vector>
#include<algorithm>

using namespace std;

#include"StackLi.h"

#include"BinaryNode.h"


bool lower_procedence(char *tokenPtr, char top_of_stack)
{
// Checks if operaotr just read in is of higher or equal presedence
// than the operator next on the stack
	bool flag = true;

	if ((*tokenPtr == '+') && (top_of_stack == '+'))
	{
			flag = true;
		
	}	

	else if ((*tokenPtr == '-') && (top_of_stack == '-'))
	{
			flag = true;
		
	}	

	else if ((*tokenPtr == '-') && (top_of_stack == '+') )
	{
		flag = true;
	}

	else if ((*tokenPtr == '+') && (top_of_stack == '-'))
	{
			flag = false;
		
	}	
	
	else if(((*tokenPtr == '+') || (*tokenPtr == '-')) && ((top_of_stack == '*') || (top_of_stack == '/')))
	{
			flag= true;
	}	

	else if ((*tokenPtr == '*') && (top_of_stack == '/'))
	{
			flag = false;
	}	
	
	else if ((*tokenPtr == '*') && (top_of_stack == '*'))
	{
			flag = true;
		
	}	

	else if ((*tokenPtr == '/') && (top_of_stack == '/'))
	{
			flag = true;
		
	}	

	else if ((*tokenPtr == '/') && (top_of_stack == '*'))
	{
			flag = true;
		
	}	
	

	else if(((*tokenPtr == '*') || (*tokenPtr == '/')) && ((top_of_stack == '+') || (top_of_stack == '-')))
	{
			flag= false;
	}


	else if((*tokenPtr == ')')&& (top_of_stack != '(') )
	{
			flag= false;
	
	}

	else if ((*tokenPtr == ')') && ( top_of_stack == '('))
	{
		flag = true;
	}

	else if(top_of_stack == '(')
		flag = false;

	else
		flag = true;

	return flag;
}


int main()
{
	Stack<char> * operator_Stack = new Stack<char>;

	Stack<BinaryNode<char>*> * ptrStack = new Stack<BinaryNode<char>*>;
	

   char equation[50];
   char* tokenPtr;
   
   //vector<char> postfix_Equations(1, 0);
   vector<char> postfix_Equations;

   cout<<"Please Enter In A Equation"<<endl;

   cin.getline(equation, sizeof(equation), '\n');//To catch all of the char p
   
   tokenPtr = strtok(equation," ");

   
   
   
   while(tokenPtr != NULL)
   {
	    if( *tokenPtr == '+' || *tokenPtr=='-' || *tokenPtr == '/' || *tokenPtr == '*' || *tokenPtr == '^')
			   {
				   
					   while(!operator_Stack->isEmpty())
							{
								if(lower_procedence(tokenPtr, operator_Stack->top()))
								{
										postfix_Equations.push_back(operator_Stack->topAndPop());
								}
								
								else
								{
									operator_Stack->push(*tokenPtr);
									break;
								}
							
							 }

					   				   

					   if(operator_Stack->isEmpty())
									operator_Stack->push(*tokenPtr);

				  
				}

		else if (*tokenPtr == '(')
			operator_Stack->push(*tokenPtr);

		else if(*tokenPtr == ')')
		{
			while((operator_Stack->top() != '(')&& (!operator_Stack->isEmpty()))
				postfix_Equations.push_back(operator_Stack->topAndPop());

			if( operator_Stack->top() == '(' || operator_Stack->top() == ')' )
			{
				operator_Stack->pop();
			}
	
										
		}

		else if(isalpha(*tokenPtr) || isalnum(*tokenPtr))
			postfix_Equations.push_back(*tokenPtr);
			   
				
			    tokenPtr = strtok(NULL, " ");
   }

   if(!operator_Stack->isEmpty())
   {
	   while(!operator_Stack->isEmpty())
		   postfix_Equations.push_back(operator_Stack->topAndPop());
   }

   cout<<"\nPostfix Equation\n"<<endl;
   for(int i =0; i!= postfix_Equations.size(); i++)
	   cout<<postfix_Equations[i];

   cout<<"\n"<<endl;

   //End of POSTFIX---------------------------------------------------------------------------------------------------

   

   for(int i = 0; i < postfix_Equations.size(); i++)
   {
	   
	   
	   if(postfix_Equations[i] == '(' || postfix_Equations[i] == ')' || postfix_Equations[i] == '+' || postfix_Equations[i]=='-' || postfix_Equations[i] == '/' || postfix_Equations[i] == '*' || postfix_Equations[i] == '^')
	   {
		   if(ptrStack->isEmpty())
		   {
			
			BinaryNode<char> *newNode = new BinaryNode<char>(postfix_Equations[i]);
			ptrStack->push(newNode);
		   }

		   else
		   {
			   BinaryNode<char> *newNode = new BinaryNode<char>(postfix_Equations[i]);
	
			   
				newNode->right = ptrStack->topAndPop();
					
				
			  
				 
			   if(!ptrStack->isEmpty())
			   {
					newNode->left = ptrStack->topAndPop();
			   }

			   ptrStack->push(newNode);


		   }
		   
	   }

	   else if(postfix_Equations[i] == '~' || postfix_Equations[i] == '!' || postfix_Equations[i] == '&')
	   {
		   BinaryNode<char> *newNode = new BinaryNode<char>(postfix_Equations[i]);

		   newNode->right = ptrStack->topAndPop();

		   ptrStack->push(newNode);
	   }

	   else
	   {
		   BinaryNode<char> *newNode = new BinaryNode<char>(postfix_Equations[i]);
		   ptrStack->push(newNode);
		   
	   }
	   tokenPtr = strtok(NULL, " ");

   }

   BinaryNode<char> *finalNode = new BinaryNode<char>(ptrStack->topAndPop(), postfix_Equations.size());
	
	system("PAUSE");

	return 0;
}

Select all Open in new window

>> I have not actually created the 2d array yet because I was trying to figure out how to space the elements out first.

The way to solve this problem is to break out the formatting spacing issue as a separate problem from collecting the data. So, with pencil and paper, and forgetting about printing, just show a 2d array (or a ragged array - your choice) as you traverse your tree:

       *
      / \
     +   5
    / \
   1   3

That is desribe step-by-step how your 2d container looks after each getting of the node values. Then you'll have a better idea of how to design your program. (It appears that the problem you are having is not related to the C++ zone, but rather to the Algorithms zone.)

I guess you don't like paper and pencil. I can't do without them. Good luck in your studies!

i think the bottom-up print-out is not really practicable.

if you know the depth of your tree and reserve 3 bytes for each operand than you need

          (2^(depth-1)) * 3 + (2^(depth-1) - 1)

bytes in the bottom line. the first term is for the operands, the second term for the gaps.

for a depth of  3 as in your sample it is (4*3) + (4-1) == 15.

of course your drawing sample needs less cause you only used 1 byte for operands and the tree was degenerated as it has only 2 items at bottom.

if you would have a numbering (x.y.z) of the bottom level items like 1.1.1, 1.1.2, 1.2.1, 1.2.2 you easily could compute from that index the position where the item (value) needs to get placed in the line:

  offset = (y + (z-1) ) * w  +  (y + (z-1) ) * g

where y+(z-1) is the number of items left from x.y.z multiplied with w (=chars per item value) and multiplied with the gap between two items (for that level).  

  offset for 1.2.2 and w=3 and g=1:  3*3 + 3*1 = 12

if you are not at the bottom line you would need to add an offset to the most-left item of that level which in our sample would be 2 what you could see from a 'painting' like

  xyz     uvw 
abc def ghi jkl

Select all Open in new window

(that is what phoffric told you!!!!)

the gap would increase from 1 to 5. one level up we would have an initial offset of 6 and a gap of 13.

so the sequence of initial offset is 0, 2, 6  and sequence of gap is 1, 5, 13.

if you look at the differences you easily could compute the next values ...

and similar computations can be done for each line with slash-backslash bars.

so you would compute offsets and gaps for each line from bottom to top. then do any traversal and create a second binary tree with the indices (as std::vector<int>) for each node of the first tree.

with all that you now could do a left or top traversal (in-order or level-traversal) and do the appropriate printouts into a 2d-array.

Sara