Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.
COURSE of the MONTH
15 days, 7 hours left to enrollBecome a Premium Member and unlock a new, free course in leading technologies each month.
[X]
Welcome to Experts Exchange
Add your voice to the tech community where 5M+ people just like you are talking about what matters.
- Help others & share knowledge
- Earn cash & points
- Learn & ask questions
10
6
3
19 Comments
Active today
See this question for an explanation:
http://www.experts-exchange.com/Programming/Algorithms/Q_25014702.html
http://www.experts-exchange.com/Programming/Algorithms/Q_25014702.html
Active today
And this follow-up question adds color to the tree:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_25031661.html
http://www.experts-exchange.com/Programming/Languages/CPP/Q_25031661.html
Active today
what about a horizontal output ?
you could use inorder traversal and could compute each line shape (offsets and bars) from item level, tree depth and previous nodes.
Sara
-- 5
|
*
|
| -- 3
| |
-- +
|
-- 1
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);
}
}
Active today
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.
Active today
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
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
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?
Active today
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?
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.
*
/ \
+ 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.
Active today
>> 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).
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).
Active today
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.
Active today
Are all the numbers and operators a single char? If so, then the spacing becomes easier.
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.
*
/ \
+ 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.
Active today
>> 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.
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
Stack.h
Main.cpp
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
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
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;
}
Active today
>> 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.)
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.)
Active today
I guess you don't like paper and pencil. I can't do without them. Good luck in your studies!
Active today
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
(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
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
(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
Featured Post
Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.
Question has a verified solution.
If you are experiencing a similar issue, please ask a related question
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control. For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks. Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses
Course of the Month15 days, 7 hours left to enroll
741 members asked questions and received personalized solutions in the past 7 days.
Join the community of 500,000 technology professionals and ask your questions.