• Support PF! Buy your school textbooks, materials and every day products Here!

Tree Traversals

  • Thread starter Bucs44
  • Start date
  • #1
57
0

Homework Statement


I am having a hard time figuring out this postfix expression and turning it into a binary tree: ABCD+*/E-



The Attempt at a Solution



what's confusing me is the left side of the tree - the ABCD - I know the right side of the tree would look like this: - is the root and * / E

Any help would be greatly appreciated
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
When you see a letter, think of it as an instruction to put it on a stack. When you see an operator, think of pulling the last two things off the stack and pushing the result of the operation back on the stack. So after you've parsed the ABCD, you have four things on the stack waiting for later operations.
 
  • #3
57
0
What needs to be parsed? AB on the left and CD on the right?
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
What needs to be parsed? AB on the left and CD on the right?
?? Neither. I can't start drawing a tree until I hit the +, at which point I realize C and D are leaves of the + node. Then the + node is itself a leaf of the * node, to get the other leaf I go back and see what's on the stack and there is a B etc etc.
 
  • #5
NateTG
Science Advisor
Homework Helper
2,450
5
(This belongs into the computer homework section.)

It might be instructive for you to work out the equivalent infix expression.
 

Related Threads on Tree Traversals

  • Last Post
Replies
2
Views
2K
Replies
8
Views
7K
  • Last Post
Replies
6
Views
6K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
4
Views
1K
Replies
6
Views
607
  • Last Post
Replies
4
Views
6K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
3
Views
554
Top