Count nodes in binary trees

Asked

Viewed 3,225 times

1

Good evening, I’m studying binary trees and I came across an exercise that asks me to count the knots. I did it by adapting an algorithm that calculates height and works...

int conta_nos (arvore *r) { 
    if (r == NULL) return 0;
    else {          
        int conte = conta_nos (r->esq);         
        int contd = conta_nos (r->dir); 
        return conte + contd + 1;   
    }
}

However I did not understand it very well, I already carry recursion doubts and I believe that this is the point of my doubt. In this question I declared two variables to receive what comes from left and right and in the return I added the two and 1. Then it follows, if I take the "+1" of the return he Zera the amount of us, I understood that every time he passes by one of the nodes he adds 1, blz, but, what gets these two variables count and contd, before that tried to return return conta_nos(r->esq) + conta_nos(r->dir) + 1; but it didn’t work out so well, as I wrote I carry recursion doubts and I feel like I’m getting stuck in trees.

c recursion

  • Certainty that return 1 + conta_nos(r->esq) + conta_nos(r->dir); didn’t work? Because it should

  • I may have done something wrong, I’ll check, but I still have doubts about what the two variables receive

1 answer

2


This is a function recursive, so it iterates to the limit calling itself then comes back returning desired values to the higher calls.

A recursive function is made up of 3 things:

  1. A conditional to stop recursion
  2. A call of its own
  3. The return of a value

Basically what this function does is walks to the right and left end of each side of the tree. For example,

int conte = *conta_nos (r->esq);*

return in case the values conte = 0 and contd = 0 so now the value of conte will be 1.

same goes for line 

int contd = conta_nos (r->dir);

So we will have in the penultimate in the tree, after the iteration of the two function calls, values conte = 1 and contd = 1 ( that represent the leaves of the tree associated with this penultimate node) and when doing the Return to the top node this will return the value of conte and contd above adding 1 more representing itself. The return will show you have 3 nodes down to the top node.

Browser other questions tagged c recursion

You are not signed in. Login or sign up in order to post.