Concepto de Árbol
Un árbol consta de un conjunto finito de elementos, denominados nodos y un conjunto finito de líneas dirigidas, denominadas ramas, que conectan a los nodos.
Estructura
graph TD
A(("A")) --> C(("C"))-->F(("F"))
A --> B(("B")) --> D(("D"))
B --> E(("E"))
Y se tiene los elementos siguiente
graph TB
A(("A")) --> C(("C"))-->F(("F"))
A --> B(("B")) --> D(("D"))
B --> E(("E"))
raíz --- A
nodo_hijo --- C
hojas --- F
Otro ejemplo es:
graph TB
16(("16")) -->|Izquierda| 8(("8")) -->|Izquierda| 3(("3"))
16 -->|Derecha| 24(("24")) -->|Izquierda| 19(("19")) -->|Derecha| 21(("21"))
8 -->|Derecha| 13(("13"))
3 -->|Derecha| 7(("7"))
Raíz es donde comienza la estructura.
Hoja son los elementos que no tiene hijos o donde termina la estructura.
¿Cómo definimos un Nodo?
Necesitamos un nodo que apunte a otros nodos.
struct Nodo{
int dato;
Nodo *der;
Nodo *izq;
En caso de ser un árbol con más conexiones (Ternario u otro) simplemente incluye más Nodos.
Propiedades del Árbol
graph TB
16(("16")) -->|Izquierda| 8(("8")) -->|Izquierda| 3(("3"))
16 -->|Derecha| 24(("24")) -->|Izquierda| 19(("19")) -->|Derecha| 21(("21"))
8 -->|Derecha| 13(("13"))
3 -->|Derecha| 7(("7"))
Longitud de camino:
"Es el número de ramas que tienes que pasar para llegar de un Nodo a otro"
Por ejemplo:
- La longitud de camino para llegar a 7 es 3.
Esto se hace contando las ramas o contando los nodos en el camino menos 1: $nodos camino - 1$.
Altura de un nodo:
"Se ve hacia arriba", partiendo de una hoja.
Por ejemplo:
- La altura del nodo 24 es 2.
Profundidad de un nodo. Nivel
Para esto es necesario ver los niveles de un árbol.
Y dado un Nodo buscar en que nivel se encuentra.
Por ejemplo:
- La profundidad del Nodo 19 es 2.
Nodos Hermanos
- Deben estar al mismo Nivel
- Tener el mismo padre
Por ejemplo:
- El nodo 3 y el Nodo 13 son hermanos.
Orden
La máxima cantidad de hijos que puede tener un Nodo.
Orden 2: un nodo puede tener 0, 1, 2 hijos.
Orden 3: un nodo puede tener 0, 1, 2, 3 hijos.
...
Código disponible en: GitHub