Solved

How to print out a binary tree

Posted on 2011-03-09
19
740 Views
Last Modified: 2012-05-11
Hello Everyone,

I am trying to figure out how can I print a binary tree out in the tree structure.  For example, if I enter in an equation it must print out like this.

       *
      / \
     +   5
    / \
   1   3
0
Comment
Question by:brich744
  • 10
  • 6
  • 3
19 Comments
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
And this follow-up question adds color to the tree:
     http://www.experts-exchange.com/Programming/Languages/CPP/Q_25031661.html
0
 
LVL 32

Expert Comment

by:sarabande
Comment Utility
what about a horizontal output ?

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

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

0
 

Author Comment

by:brich744
Comment Utility
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);
		
		
	}
		
}

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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.
0
 
LVL 32

Accepted Solution

by:
sarabande earned 500 total points
Comment Utility
you can't print by recursion cause you can't get back when reached the bottom line.

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

Sara
0
 

Author Comment

by:brich744
Comment Utility
 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?
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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?
0
 

Author Comment

by:brich744
Comment Utility
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.  
0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> 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).
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
Are all the numbers and operators a single char? If so, then the spacing becomes easier.
0
 

Author Comment

by:brich744
Comment Utility
Yes, all of the operators are a single char.
0
 

Author Comment

by:brich744
Comment Utility
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.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> 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.
0
 

Author Comment

by:brich744
Comment Utility
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

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

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;
}

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> 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.)
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
I guess you don't like paper and pencil. I can't do without them. Good luck in your studies!
0
 
LVL 32

Expert Comment

by:sarabande
Comment Utility
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

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





0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now