30 nov. 2012

Programación en C - Nomenclatura de Arboles

Hola a todos, en esta ocasión les presento la nomenclatura mas usada de los Arboles en C (y seguramente también en otros lenguajes), para que cualquiera pueda entender a que nos referimos cuando hablamos por ejemplo de una Hoja o de un Árbol Completo.

Sin más preámbulos, pasemos a las definiciones:

Raíz: Es aquel Nodo que no depende de ningún otro.

Rama: Es la arista entre 2 Nodos, también se la llama arco o enlace.

Padre: Un Nodo X es padre de un Nodo Y si por alguna Rama de X se puede llegar a Y.

Hijo: Un Nodo Y es hijo de un Nodo X si por alguna Rama de X se puede llegar a Y.

Subárbol: Es cada uno de los Árboles que depende de un Nodo.

Grado de un Nodo: Es la cantidad de Subárboles no vacios que tiene el Nodo (Es la cantidad de Hijos).

Grado de un Árbol: Es el máximo entre el grado de los Nodos.

Hoja: Es aquel Nodo que no tiene Hijos (Nodo de Grado 0).

Nivel: Es la cantidad de Ramas que hay que recorrer para llegar de la Raíz hasta un Nodo.

Altura: Es el máximo Nivel del Árbol.

Ancho: Es la máxima cantidad de Nodos existente en un mismo Nivel.

Árbol Completo: Es aquel Árbol en el que todo Nodo tiene cero o N Hijos, siendo N el Grado del Árbol.

Árbol Perfecto: Es aquel Árbol Completo en el que todas sus Hojas se encuentran en el mismo nivel


Pasemos a unos ejemplos para que nos queden más claros los conceptos:

Ejemplo de Arbol



Pasemos a Analizar cada definición.

Raíz: 24, ya que es el Nodo el cual no depende de ningún otro

Rama: Son las líneas que unen los Nodos

Padre del 24: No tiene Padre, es la Raíz
Padre del 39, 12, 22: El Padre de estos Nodos es el 24
Padre del 05: El Padre es el Nodo 39
Padre del 23, 11: El Padre de estos Nodos es el 22

Hijo del 24: Los Hijos del Nodo 24 son el 39, 12 y 22
Hijo del 39: El Hijo del Nodo 39 es el 05
Hijo del 12: El Nodo 12 no tiene hijos
Hijo del 22: Los Hijos del Nodo 22 son el 23 y 11

SubArboles del 24: El Nodo 24 tiene 3 SubArboles
SubArboles del 39: El Nodo 39 tiene 1 SubArbol
SubArboles del 12: El Nodo 12 no tiene SubArboles
SubArboles del 39: El Nodo 22 tiene 2 SubArboles

Grado del Nodo 24: 3
Grado del Nodo 39: 1
Grado del Nodo 05: 0
Grado del Nodo 12: 0
Grado del Nodo 22: 2
Grado del Nodo 23: 0
Grado del Nodo 11: 0

Grado de un Árbol: 3

Hojas del Árbol: 05, 23, 11

Nivel: El nivel se especifica en la imagen del Árbol, siendo la Raiz el Nivel 0, aumentando por cada fila de nodos. En este caso:

Nivel 0: 24
Nivel 1: 39, 12, 22
Nivel 2: 05, 23, 11

Altura del Árbol: 2

Ancho del Árbol: 3

Árbol Completo: Este Árbol NO es un Árbol Completo. Para que sea un Árbol Completo deberían figurar los siguientes nodos



En esta modificación se observa que todo Nodo tiene 0 o 3 hijos (siendo 3 el grado del Árbol), cumpliendo así las condiciones necesarias para ser un Árbol Completo

Árbol Perfecto: El Árbol anterior no es un Árbol Perfecto, ya que debe cumplir con la condición de Árbol Completo y que todas sus Hojas se encuentren al mismo Nivel. Una forma de mostrarlo sería agregándole 3 Hijos al Nodo: 12, ya que todas las hojas estarían al mismo nivel y seguiría cumpliendo con las condiciones de Árbol Completo. Pero una forma más clara de verlo es quitando todo el Nivel 3, quedando conformado de esta forma el Árbol:



Esto es todo por hoy, cualquier duda/pregunta en los comentarios :)

Saludos!

-----
Argies_Dario


Fuentes:
Ninguna

No hay comentarios:

Publicar un comentario

Dejanos tu comentario sobre esta nota