Estructuras de Datos y Algoritmos/Árboles
Nodo (en nuestro caso nodo de un árbol) es un elemento unitario de composición de un árbol.
Camino direccional entre dos nodos de un árbol o relación padre-hijo. Sean dos nodos n1,n2 vamos a definir n1>n2 como la relación en la que n1 es el predecesor de o el padre de n2, R12.
Definición de árbol es un conjunto de relaciones o caminos direccionales entre los nodos del mismo cumpliendo una propiedad fundamental, que es que no hay ciclos entre las relaciones. Esto quiere decir que siguiendo las relaciones padre hijo no podemos nunca volver a un predecesor.
Ejemplo :
Sean los nodos n1,n2 podemos definir el árbol A para esos nodos como :
A={ (n1>n2)}={R12}
Sean los nodos n1,n2,n3,n4 podemos definir el árbol A para esos nodos como :
A={ (n1>n2),(n2>n3)}={R12,R23}
Sean los nodos n1,n2,n3,n4 podemos definir el árbol A para esos nodos como :
A={ (n1>n2),(n2>n3),(n1>n4)}={R12,R23,R14}
Si añadiéramos la relación R31=(n3>n1) A dejaría de ser un árbol porque tendría un ciclo :
G={ (n1>n2),(n2>n3),(n1>n4),(n3>n1)}={R12,R23,R14,R31}
De n1 a n2 por la relación R12
De n2 a n3 por la relación R23
De vuelta a n1 por la relación R21
Nodo raíz o raíz de un árbol: Es el nodo del árbol que no tiene predecesor (o padre). En el ejemplo n1
Nodo de tipo hoja o hoja de un árbol: Es un nodo del árbol que no tiene sucesores o hijos. En el ejemplo n3 y n4