Grau de nós em árvores
O grau de um nó é o número de filhos que ele tem.
O grau de uma árvore é o grau máximo entre todos os seus nós.
Note
O número de filhos de um nó qualquer determina o grau desse nó.
Exemplo de implementação em Java:
class TreeNode {
int value;
TreeNode left, right;
TreeNode(int item) {
value = item;
left = right = null;
}
}
class BinaryTree {
TreeNode root;
int getDegree(TreeNode node) {
if (node == null) {
return 0;
}
int degree = 0;
if (node.left != null) {
degree++;
}
if (node.right != null) {
degree++;
}
int leftDegree = getDegree(node.left);
int rightDegree = getDegree(node.right);
return Math.max(degree, Math.max(leftDegree, rightDegree));
}
int getDegree() {
return getDegree(root);
}
}