Concepto de Árbol Binario
Un árbol binario es un árbol de orden 2. Se conoce el cono de la izquierda como hijo izquierdo y el de la derecha como hijo derecho.
graph TB A --- B --- D B --- E --- H E --- G A --- C --- F
graph LR C --- N[" "] A --- B --- C --- D --- E
Un árbol binario es una estructura recursiva. Un árbol binario se divide en tres subconjuntos disjuntos:
- Nodo Raíz
- Subárbol Izquierdo
- Subárbol Derecho
Por ejemplo un árbol se puede descomponer
graph TB R --- D --- C R --- I --- B I --- A
A lo siguiente
graph TB R
Subárbol Izquierdo
graph TB I --- B I --- A
Subárbol Derecho
graph TB D --- C
En cada nivel se vuelve a repetir, por lo que se puede usar el mismo algoritmo.
Tipos de árbol Binario
Árbol Lleno
Todos los nodos tienen dos hijos (menos las hojas) y el último nivel siempre está completo.
graph TB A --- B --- D B --- E A --- C --- F C --- G
Árbol Completo
Los nodos hojas del último nivel, no están todos, no está el último nivel lleno.
- El Subárbol Izquierdo casi siempre tiene más nodos que el derecho.
graph TB A --- B --- D --- H D --- I B --- E --- J E --- K A --- C --- F C --- G
Árbol Degenerado
Solo tiene hijos de un solo lado, por lo que al extenderse es prácticamente una lista enlazada.
graph TB A --- B --- C --- D --- E C --- N[" "]
Estructura de un Árbol Binario
Para eso necesitamos un pequeño struct
Cpp
struct Nodo{
int dato;
Nodo *der;
Nodo *izq;
La representación gráfica de un árbol binario es la siguiente
- Note como los punteros apuntan a otros Nodos
- Como lo hijos en izquierda y derecha al no apuntar a nada son NULL
