Profundidade de uma árvore binária. Escreva uma função depth que receba uma árvore binária e determine seu número de níveis.
Passo 1
Para calcular a profundidade/altura de uma árvore binária, usaremos uma função recursiva.
A função passará os nós TreeNodePtr.
Primeiro, temos que verificar se o nó raiz foi inicializado:
int depth(TreeNodePtr treePtr)
{
if (treePtr == NULL)
return 0;
...
}
Passo 2
Então, para cada nó esquerdo/direito, chame recursivamente a função passando o nó esquerdo/direito:
int depth(TreeNodePtr treePtr)
{
...
int leftHeight = depth(treePtr->leftPtr);
int rightHeight = depth(treePtr->rightPtr);
...
}
Passo 3
Por fim, retorne a altura maior (esquerda/direita) + 1 (o nó atual):
int depth(TreeNodePtr treePtr)
{
...
return max(leftHeight, rightHeight) + 1;
}
Resposta
Ver o desenvolvimento.