Árboles Enearios
Al igual que en los TDAs estudiados con anterioridad, la forma de implementar un árbol n-ario dependerá del problema a resolver y de la capacidad del diseñador.
No obstante, existen 3 Implementaciones básicas:
- Implementación matricial. El árbol se representa en un vector de enteros, donde cada componente contiene el índice de su nodo padre.
- Implementación con listas. Se representa mediante un vector de listas. Cada índice de las componentes del vector se asocia con un nodo del árbol, y cada componente es una lista con los Hijos del nodo.
- Implementación con celdas enlazadas. Cada nodo del árbol es una celda enlazada con un puntero a su padre, a su hijo izquierda y a su hermano derecha.
- El tipo Nodo del árbol es entero.
- La relación padre-hijo se representa en un vector P, donde P[i] indica cuál es el nodo padre de i. Si el nodo no tiene padre (es la raíz), P[i] tomará valor -1.
- Las etiquetas de los nodos se representan en otro vector de etiquetas.
Esta implementación es relativamente sencilla y con bajo coste de memoria. Facilita las operaciones de acceso a los ancestros de un nodo (eficiencia O(log(n)) para viajar desde un nodo hoja hasta la raíz), pero resulta difícil gestionar operaciones con los hijos (conocer la altura, determinar los hijos, establecer hijo izquierda y hermano derecha...)
árbol eneario
- Implementación matricial. El árbol se representa en un vector de enteros, donde cada componente contiene el índice de su nodo padre.
- Implementación con listas. Se representa mediante un vector de listas. Cada índice de las componentes del vector se asocia con un nodo del árbol, y cada componente es una lista con los Hijos del nodo.
- Implementación con celdas enlazadas. Cada nodo del árbol es una celda enlazada con un puntero a su padre, a su hijo izquierda y a su hermano derecha.
- El tipo Nodo del árbol es entero.
- La relación padre-hijo se representa en un vector P, donde P[i] indica cuál es el nodo padre de i. Si el nodo no tiene padre (es la raíz), P[i] tomará valor -1.
- Las etiquetas de los nodos se representan en otro vector de etiquetas.
Esta implementación es relativamente sencilla y con bajo coste de memoria. Facilita las operaciones de acceso a los ancestros de un nodo (eficiencia O(log(n)) para viajar desde un nodo hoja hasta la raíz), pero resulta difícil gestionar operaciones con los hijos (conocer la altura, determinar los hijos, establecer hijo izquierda y hermano derecha...)
árbol eneario
árbol enario en piramide
Un Arbol se denomina Piramide si el valor del nodo padre es igual a la suma de los valores de los nodos hijos. Excepto para las hojas
Ejemplo: Este video no tiene lucro para esta pagina
Para mayor información sigueme en:
No hay comentarios:
Publicar un comentario