Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trees as Data Structures

  1. Aug 5, 2014 #1

    Maylis

    User Avatar
    Gold Member

    Hello,

    There are three different orders of traversal that we learned about
    ##\bullet## pre-order traversal
    ##\bullet## in-order traversal
    ##\bullet## post-order traversal

    Anyone know of any easy ways of remembering these 3 and how to order them? I have posted my lecture slides, but I could imagine the tree looking differently and then not knowing how to adapt and analyze how the calls would be made to a different looking tree.

    Also, when one writes a recursive program, which order of traversal is taken? Is there some sort of default? Why are there 3 ways of traversing?
     

    Attached Files:

    Last edited: Aug 5, 2014
  2. jcsd
  3. Aug 5, 2014 #2
    If you write a recursive function (R) to print (P) each node on the tree, you have these choices:
    R(this) { if(this) {P(this); R(this->left); R(this-right) } }
    R(this) { if(this) {R(this->left); P(this); R(this-right) } }
    R(this) { if(this) {R(this->left); R(this-right); P(this) } }

    Note how each yields a different print order.
     
  4. Aug 5, 2014 #3

    jtbell

    User Avatar

    Staff: Mentor

    There's no default. It's up to you to decide how you want to traverse a binary tree.

    There are actually more than three ways. Consider your "ingredients:"

    • A. Process the data in the node that you're pointing to.
    • B. Process the subtree that the node's left link points to.
    • C. Process the subtree that the node's right link points to.

    How many different sequences can we perform these three items in?

    A, B, C
    A, C, B
    B, A, C
    [you fill in the rest]

    The proper sequence to use depends on what you want to do, that is, what overall algorithm the traversal is part of.
     
  5. Aug 6, 2014 #4

    Maylis

    User Avatar
    Gold Member

    Okay, well I wrote a recursive function to find the fibonacci number of the ##n^{th}## term in the sequence as the input to the function with the formula for the fibonacci number given as

    ##F_{n} = F_{n-1} + F_{n-2}## with the base case ##F_{1} = 1## and ##F_{2} = 1##

    Code (Text):
    function fibonacci_number = fibnum(n)
    if n < 1
        return;
    elseif n == 1 || n == 2
        fibonacci_number = 1;
    else
        fibonacci_number = fibnum(n-1) + fibnum(n-2);
    end
    How do I decipher this to determine the order of traversal taken, or even how this recursive tree will appear? I turned on the breakpoint and am trying to follow it step by step, but it just isn't making sense to me. This could be in part due to an incomplete understanding of how the green and white arrows are interacting, and how the green arrow pointing down means.

    What if I flipped my sum to be fibnum(n-2) + fibnum(n-1)?? Is the first term of the summation the left child of the root node? And it's sibling the right side.

    EDIT: Just discovered that it matters very much indeed. I had it the other way around, so it wasn't calling in the order that my lecture slides indicated, because they had the sum flipped around. Very interesting...But can I manipulate this code to follow a post-order or in-order.

    I did the breakpoint and ran the code step by step, and I see how it is recursively calling, however, I don't see how it is returning the calls.

    Here is the updated code
    Code (Text):
    function fibonacci_number = fibnum(n)
    if n > 2
        fibonacci_number = fibnum(n-2) + fibnum(n-1);
    else
        fibonacci_number = 1;
    end
     
    Last edited: Aug 6, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Trees as Data Structures
Loading...