Arboles

ARBOLES EN C++
Un árbol es una estructura no lineal en la que cada nodo puede
apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una
estructura en compuesta porun dato y varios árboles.
Esto son definiciones simples. Pero las características que
implican no lo son tanto.
Lo podremos ver en el grafico que podemos apreciar debajo.

Está compuesto por:
• Nodohijo: cualquiera de los nodos apuntados por uno de los
nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
• Nodo padre: nodo que contiene un puntero al nodo actual. En
el ejemplo, el nodo 'A'es padre de 'B', 'C' y 'D'.
Los árboles con los que veremos tienen otra característica
importante: cada nodo sólo puede ser apuntado por otro nodo, es
decir, cada nodo sólo tendrá un padre. Esto haceque estos
árboles estén fuertemente jerarquizados, y es lo que en realidad
les da la apariencia de árboles.

En cuanto a la posición dentro del árbol:
• Nodo raíz: nodo que no tiene padre. Este esel nodo que
usaremos para referirnos al árbol. En el ejemplo, ese nodo
es el 'A'.
• Nodo hoja: nodo que no tiene hijos. En el ejemplo hay
varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
• Nodo rama:aunque esta definición apenas la usaremos,
estos son los nodos que no pertenecen a ninguna de las dos
categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Existen otros conceptos quedefinen las características del árbol, en
relación a su tamaño:
•

Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este
modo, diremos que un árbol en el que cada nodopuede apuntar a otros dos es de orden
dos, si puede apuntar a tres será de orden tres, etc.

•

Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol
delejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen
elementos con más de tres hijos.

•

Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida...