1

Boa noite, estou estudando árvores binárias e me deparei com um exercício que pede pra contar os nós. Imitei adaptando um algoritmo que calcula altura e deu certo...

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

Porém não entendi muito bem, já carrego dúvidas de recursão e acredito que isso seja o ponto da minha dúvida. Nessa questão declarei duas variáveis pra receber o que vem da esquerda e da direita e no retorno somei as duas e acrescentei 1. Daí segue, se tiro o "+ 1" do retorno ele zera a quantidade de nós, entendi que toda vez que passa por um dos nós ele soma 1, blz, mas, o que recebe essas duas variáveis conte e contd, antes disso tentei retornar return conta_nos(r->esq) + conta_nos(r->dir) + 1; mas não deu muito certo, como escrevi carrego dúvidas de recursão e sinto que estão me atrapalhando em árvores.

2
  • Certeza que return 1 + conta_nos(r->esq) + conta_nos(r->dir); não funcionou? Pois deveria
    – mercador
    28/06/2017 às 1:29
  • Posso ter feito algo errado, vou verificar, mas ainda tenho dúvida sobre o que recebe as duas variáveis 28/06/2017 às 1:34

1 Resposta 1

2

Essa é uma função recursiva, portanto ela itera até o limite chamando a si mesma depois volta retornando valores desejados paras as chamadas superiores.

Uma função recursiva é feita de 3 coisas:

  1. Uma condicional para parar a recursividade
  2. Uma chamada própria
  3. O retorno de um valor

Basicamente o que essa sua função faz é caminha até o extremo direito e esquerdo de cada lado da arvore. Por exemplo,vamos pensar no penúltimo nó da arvore ao chamar essa linha

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

retornará no caso os valores conte = 0 e contd = 0 portanto agora o valor de conte será 1.

o mesmo vale para linha

int contd = conta_nos (r->dir); 

Portanto teremos no penúltimo no da arvore, depois da iteração das duas chamadas da função, valores conte = 1 e contd = 1 ( que representam as folhas da arvore associadas à esse penúltimo nó) e ao fazer o return para o nó superior este vai retornar o valor de conte e contd acima somando mais 1 que representa ela mesma. O return mostrará que têm 3 nós abaixo para o nó superior.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .