Thread: Function which makes a simmetric visit in a Binary Search Tree

  1. #1
    Registered User
    Join Date
    Jun 2019
    Posts
    33

    Function which makes a simmetric visit in a Binary Search Tree

    Hi everyone.

    In this post I'm gonna show you just the definition of a function that I can't understand.

    Here we have the exercise.....
    Given a binary search tree:
    define a recursive function which makes a simmetric visit of the tree and which prints the value of every node.


    Two notes:
    Note number one: simmetric visit is that kind of visit which shows in order:
    1) Left sons;
    2) Root;
    3) Right sons.
    Note number two: every node of the tree is made like this:
    Code:
            struct btree{ 
                  float value; 
                 struct btree * left_ptr; 
                 struct btree * right_ptr; 
                 }


    Here we have the definition of the function that I can't understand:

    Code:
    void visit_r(struct btree * ptr){ 
    /*function which takes in input a pointer to struct btree*/
    
    
    
    if (ptr != NULL) { /*if the pointer points to something*/
    
        printf("I search the left son... "); 
    
        visit_r(ptr->left_ptr); 
    /*I can't understand what happens here. I re-use my 
    function with a new input, but I will give a new input 
    until pointer==NULL. 
    When pointer will be == NULL, I will not
     enter in the "if cycle", and I will not be able
     to print the value of my nodes!*/
    
    
        printf("\n I print the value: %f \n", ptr->value);
    
    
    printf("I search the right son... "); 
    visit_r(ptr->right_ptr);
    } printf("Let's go back... "); 
    
    /*I can't understand neither how it can go back, 
    how it can 'climb' the tree*/
    }
    Thanks everyone!!

  2. #2
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    it remembers what it has done on the stack. when it reaches the first recursive call it effectively pauses the of that instance of the function and creates another.

    think of it as the function main. it starts at the top and works its way down the lines of code till it reaches a function call. it then stops executing the lines of code in main and goes to the called function once it has finished running the lines of code in the called function it then resumes the code in main starting where it left off.

    incidentally did you write the function your self or did you copy it from somewhere

  3. #3
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by cooper1200 View Post
    ... till it reaches a function call. it then stops executing the lines of code in main and goes to the called function once it has finished running the lines of code in the called function it then resumes the code in main starting where it left off.
    Ok, so when it reaches line n10 it starts again from line n1 with a different input.
    But I still don't understand how it can work,
    because it will do this until 'ptr->left_ptr' will be' == NULL'.
    But when 'ptr->left_ptr' will be == 'NULL', I will not enter in the cycle "if(...)" and I will not be able to print the value of my nodes!

    Quote Originally Posted by cooper1200 View Post
    incidentally did you write the function your self or did you copy it from somewhere
    It is written by my university teacher.

    If you have time, please, answer to my questions!
    Anyway, thank you!!

  4. #4
    Registered User
    Join Date
    May 2019
    Posts
    209
    On the general subject of recursion

    The algorithm to traverse a binary tree you present is a typical recursive algorithm, though in two paths. First, to better understand recursion, one should review a single path in recursion.

    For that I start with a simple depth counter:


    Code:
    void foo( int n )
    {
     std::cout << "Entering at: " << n << std::endl;
    
     if ( n < 5 ) foo( n + 1 );
    
     std::cout << "Leaving at: " << n << std::endl;
    
    }
    
    int main()
    {
     foo( 0 );
     return 0;
    }

    The output is this:

    Entering at: 0
    Entering at: 1
    Entering at: 2
    Entering at: 3
    Entering at: 4
    Entering at: 5
    Leaving at: 5
    Leaving at: 4
    Leaving at: 3
    Leaving at: 2
    Leaving at: 1
    Leaving at: 0


    This illustrates two phases for each call to foo. The code before the recursive call (the call to foo inside foo) is phase 1, the recursive call itself descends into the recursion, then as that returns the code after the recursive call executes as phase 2 of the recursion.

    Some recursive algorithms ignore either phase, some rely upon both phases.

    What's important to understand is the operation of the stack when a function calls itself. You are probably aware of stack containers, but in the context of function oriented languages (most modern languages), "the" stack is as a block of memory intimately associated with the CPU (it has at least one register devoted to the operation of the stack). "The" stack operates as a LIFO stack (last in, first out). This is like a stack of cards dealt face up, one atop the other. Deal out 5 cards, and from your view they appear, from the top card, in reverse order from that which was dealt.

    Each function call generates a new entry on "the" stack. It represents, first among a number of things, the position of the code that called the function. That's how the CPU knows where to return when the function concludes.

    The next thing represented on the stack, often known as the stack frame, are the local variables declared in that function, and the parameters pass to that function.

    Armed with that, review how calling foo acts upon the stack. In main, the call to foo with paremeter 0 (foo at 0) pushes one entry on the stack, including a copy of the value of the parameter 0.

    When foo calls itself with foo at 1, another entry is pushed on the stack with a copy of the parameter (at 1 now). This repeats until the termination test is met (in the example n >= 5 terminates the recursion).

    At that moment all phase 1 steps of the recursion were performed, leading to the first half of the output example. At that moment "the" stack resembles that output of all the "entering at" statements, but in reverse. The stack, like that stack of cards dealt face up, shows parameter 5 on the top of the stack.

    Upon return from the recursive call with foo at 5, that entry on the stack is removed, much like pulling a card off the stop of the stack of cards and putting it aside.

    That reveals the parameter 4, which is the recursive level being executed upon the return from 5. The output of the "leaving at" lines are now being executed. 5 was already printed when that recursive call was denied, and upon return the entry on "the" stack for 5 was removed.

    Pause a moment to seal this image in mind. The execution is on the line printing "leaving at" where n is 4.

    Execution just returned from the call to foo, where n was 4 but the parameter was incremented. The stack, storing the value of n, represents the "stack frame" for this recursive call.

    All of the local variables (including the input parameters) are allocated in stack memory. That allocation is formed automatically for you by the compiler based on the code you write, so if you declare more local variables more room is set aside by the compiler.

    Each level of recursion is an entry on the stack. Each entry corresponds to a kind of structure formed by the local variables you declare. It is almost as if there is a hidden pointer to a structure defined by all the local variables (and input parameters).

    Actually, it's not "almost", it is. That's the stack pointer (or more specifically the stack frame pointer).

    Imagine you're inside the machine, that you've been transported into the computer, you're floating along with the data, you're standing on the stack at this moment where n is 4, and your feet are on that code about to print "leaving at".

    Looking down, through a translucent floor below you, there is now an array of structures underneath you. If you look carefully you'll see your on the 4th story of a building of structures, with the one below you being n at 3, and below that n at 2, and so on to the ground where n is 0.

    When you step forward through the code, and foo at 4 returns, you jump down to the floor below, where n was 3 (and because you dropped a floor, or level, n is 3 again).

    This is the general notion of recursion. Although many algorithms call recursion (depth), because they view this from a reverse perspective, it is actually more appropriate to think of each recursive call to be an upward growth of the stack, because it corresponds to real world analogies, like a stack of cards dealt face up, more naturally to the human mind.

    Factually, either view is just as valid because inside the machine there really is no absolute orientation, no gravity, no flat ground.

    Now, think upon your professor's example (which, no doubt, he got years ago from our elders).

    It recurses on two values, moving to left and a right node pointer, but the operation is exactly the same - there are just two paths. There is still only one stack at a time, but the path traveled forms a kind of illustration of the tree itself.

    If you followed the operation of the stack over time running the tree traversal code, you'd notice that each separate recursion traces out the path through the tree. The operation of the stack itself is the same as depicted above.

    Instead of incrementing a value like n, the traversal depends upon the structure of the data where each link points to another, where each recursion places a copy of the "next pointer" on the stack, and upon return is running code based on the same structure of the stack illustrated above.
    Last edited by Niccolo; 06-26-2019 at 03:18 PM.

  5. #5
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by Niccolo View Post
    On the general subject of recursion

    The algorithm to traverse a binary tree you present is a typical recursive algorithm, though in two paths. First, to better understand recursion, one should review a single path in recursion.

    For that I start with a simple depth counter:


    Code:
    void foo( int n )
    {
     std::cout << "Entering at: " << n << std::endl;
    
     if ( n < 5 ) foo( n + 1 );
    
     std::cout << "Leaving at: " << n << std::endl;
    
    }
    
    int main()
    {
     foo( 0 );
     return 0;
    }

    The output is this:

    Entering at: 0
    Entering at: 1
    Entering at: 2
    Entering at: 3
    Entering at: 4
    Entering at: 5
    Leaving at: 5
    Leaving at: 4
    Leaving at: 3
    Leaving at: 2
    Leaving at: 1
    Leaving at: 0


    This illustrates two phases for each call to foo. The code before the recursive call (the call to foo inside foo) is phase 1, the recursive call itself descends into the recursion, then as that returns the code after the recursive call executes as phase 2 of the recursion.

    Some recursive algorithms ignore either phase, some rely upon both phases.

    What's important to understand is the operation of the stack when a function calls itself. You are probably aware of stack containers, but in the context of function oriented languages (most modern languages), "the" stack is as a block of memory intimately associated with the CPU (it has at least one register devoted to the operation of the stack). "The" stack operates as a LIFO stack (last in, first out). This is like a stack of cards dealt face up, one atop the other. Deal out 5 cards, and from your view they appear, from the top card, in reverse order from that which was dealt.

    Each function call generates a new entry on "the" stack. It represents, first among a number of things, the position of the code that called the function. That's how the CPU knows where to return when the function concludes.

    The next thing represented on the stack, often known as the stack frame, are the local variables declared in that function, and the parameters pass to that function.

    Armed with that, review how calling foo acts upon the stack. In main, the call to foo with paremeter 0 (foo at 0) pushes one entry on the stack, including a copy of the value of the parameter 0.

    When foo calls itself with foo at 1, another entry is pushed on the stack with a copy of the parameter (at 1 now). This repeats until the termination test is met (in the example n >= 5 terminates the recursion).

    At that moment all phase 1 steps of the recursion were performed, leading to the first half of the output example. At that moment "the" stack resembles that output of all the "entering at" statements, but in reverse. The stack, like that stack of cards dealt face up, shows parameter 5 on the top of the stack.

    Upon return from the recursive call with foo at 5, that entry on the stack is removed, much like pulling a card off the stop of the stack of cards and putting it aside.

    That reveals the parameter 4, which is the recursive level being executed upon the return from 5. The output of the "leaving at" lines are now being executed. 5 was already printed when that recursive call was denied, and upon return the entry on "the" stack for 5 was removed.

    Pause a moment to seal this image in mind. The execution is on the line printing "leaving at" where n is 4.

    Execution just returned from the call to foo, where n was 4 but the parameter was incremented. The stack, storing the value of n, represents the "stack frame" for this recursive call.

    All of the local variables (including the input parameters) are allocated in stack memory. That allocation is formed automatically for you by the compiler based on the code you write, so if you declare more local variables more room is set aside by the compiler.

    Each level of recursion is an entry on the stack. Each entry corresponds to a kind of structure formed by the local variables you declare. It is almost as if there is a hidden pointer to a structure defined by all the local variables (and input parameters).

    Actually, it's not "almost", it is. That's the stack pointer (or more specifically the stack frame pointer).

    Imagine you're inside the machine, that you've been transported into the computer, you're floating along with the data, you're standing on the stack at this moment where n is 4, and your feet are on that code about to print "leaving at".

    Looking down, through a translucent floor below you, there is now an array of structures underneath you. If you look carefully you'll see your on the 4th story of a building of structures, with the one below you being n at 3, and below that n at 2, and so on to the ground where n is 0.

    When you step forward through the code, and foo at 4 returns, you jump down to the floor below, where n was 3 (and because you dropped a floor, or level, n is 3 again).

    This is the general notion of recursion. Although many algorithms call recursion (depth), because they view this from a reverse perspective, it is actually more appropriate to think of each recursive call to be an upward growth of the stack, because it corresponds to real world analogies, like a stack of cards dealt face up, more naturally to the human mind.

    Factually, either view is just as valid because inside the machine there really is no absolute orientation, no gravity, no flat ground.

    Now, think upon your professor's example (which, no doubt, he got years ago from our elders).

    It recurses on two values, moving to left and a right node pointer, but the operation is exactly the same - there are just two paths. There is still only one stack at a time, but the path traveled forms a kind of illustration of the tree itself.

    If you followed the operation of the stack over time running the tree traversal code, you'd notice that each separate recursion traces out the path through the tree. The operation of the stack itself is the same as depicted above.

    Instead of incrementing a value like n, the traversal depends upon the structure of the data where each link points to another, where each recursion places a copy of the "next pointer" on the stack, and upon return is running code based on the same structure of the stack illustrated above.

    sorry but I know just a little bit of C.
    I never saw

    "std::cout << "Entering at: "<< n << std::endl;
    if ( n < 5 ) foo( n + 1 );

    std::cout << "Leaving at: " << n << std::endl;"

    what does that mean?

  6. #6
    Registered User
    Join Date
    Feb 2019
    Posts
    500
    Quote Originally Posted by letthem View Post
    sorry but I know just a little bit of C.
    I never saw

    "std::cout << "Entering at: "<< n << std::endl;
    if ( n < 5 ) foo( n + 1 );

    std::cout << "Leaving at: " << n << std::endl;"

    what does that mean?
    This is an *invalid* C code... but a valid C++ one.
    Equivalent C code:
    Code:
    void foo( int n )
    {
      printf( "Entering at: %d\n", n );
    
      if ( n < 5 )
        foo( n + 1 );
    
      printf( "Leaving at: %d\n", n );
    }
    Last edited by flp1969; 06-28-2019 at 09:15 AM.

  7. #7
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Niccolo should have used C code for a C forum, not C++...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Search function for binary tree
    By Jacopo in forum C Programming
    Replies: 4
    Last Post: 02-22-2018, 05:00 AM
  2. Replies: 1
    Last Post: 04-16-2011, 04:44 AM
  3. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  4. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  5. FunctionType visit and binary search trees
    By MRAB54 in forum C++ Programming
    Replies: 1
    Last Post: 05-11-2004, 05:20 AM

Tags for this Thread