¿Qué hace la siguiente función para un árbol binario dado?
int fun(struct node *root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 0; return 1 + fun(root->left) + fun(root->right); }
(A) Cuenta los Nodes hoja
(B) Cuenta los Nodes internos
(C) Devuelve la altura donde la altura se define como el número de aristas en el camino desde la raíz hasta el Node más profundo
(D) Devuelve el diámetro donde el diámetro es el número de aristas en el camino más largo entre cualquier dos Nodes
Respuesta: (B)
Explicación: La función cuenta los Nodes internos.
1) Si la raíz es NULL o un Node hoja, devuelve 0.
2) De lo contrario, devuelve 1 más el recuento de Nodes internos en el subárbol izquierdo, más el recuento de Nodes internos en el subárbol derecho.
Ver el siguiente programa completo.
#include <stdio.h> struct node { int key; struct node *left, *right; }; int fun(struct node *root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 0; return 1 + fun(root->left) + fun(root->right); } /* Helper function that allocates a new node with the given key and NULL left and right pointers. */ struct node* newNode(int key) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->key = key; node->left = NULL; node->right = NULL; return(node); } /* Driver program to test above functions*/ int main() { /* Constructed binary tree is 1 / \ 2 3 / \ / 4 5 8 */ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(8); printf("%d", fun(root)); getchar(); return 0; }
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA