Counts nodes in binary trees

Question

Counts nodes in binary trees

Navigation

#1 by (1 votes)

1

Good evening, I'm studying binary trees and I came across an exercise that asks us to count the knots. I imitated adapting an algorithm that calculates height and worked out ...

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;   
    }
}

But I do not understand very well, I already have doubts about recursion and I believe this is the point of my doubt. In this question I declare two variables to receive what comes from the left and the right and in the return I added the two and added 1. From this follows, if I take the "+ 1" of the return it zeroes the amount of nodes, I understood that every time it passes for one of the nodes it adds 1, blz, but, what gets these two variables count and contd, before that I tried to return return conta_nos(r->esq) + conta_nos(r->dir) + 1; but it did not work very well, as I wrote I carry doubts about recursion and I feel like I'm getting in the way of trees.

c

asked by anonymous 28.06.2017 / 02:42

1 answer

Get error message in Post HttpClient Aligning images inside Panel Bootstrap

score 1 · Accepted Answer

This is a recursiva function, so it iterates to the limit by calling itself after returning values desired for higher calls.

A recursive function is made up of 3 things:

A conditional to stop recursion

Own call

Returning a value

Basically what this function does is walk to the right and left end of each side of the tree. For example, let's think about the penultimate node of the tree when calling this line

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

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

The same goes for line

int contd = conta_nos (r->dir);

Then, in the second to last in the tree, after the iteration of the two function calls, conte = 1 and contd = 1 (representing the tree leaves associated with this penultimate node) and return to the upper node this will return the value of conte and contd above adding 1 more that represents itself. The return will show that they have 3 nodes below for the top node.