1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Tree Traversals

  1. Feb 16, 2007 #1
    1. The problem statement, all variables and given/known data
    I am having a hard time figuring out this postfix expression and turning it into a binary tree: ABCD+*/E-



    3. 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
     
  2. jcsd
  3. Feb 16, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Feb 16, 2007 #3
    What needs to be parsed? AB on the left and CD on the right?
     
  5. Feb 16, 2007 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    ?? 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.
     
  6. Feb 16, 2007 #5

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    (This belongs into the computer homework section.)

    It might be instructive for you to work out the equivalent infix expression.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Tree Traversals
  1. Semantic tree? (Replies: 2)

Loading...