Arboles Binarios

Unidad 7 
Árboles Binarios 

•Biblio: “Algoritmos y Estructuras de datos” de Aguilar y Martinez. Unidad 14 y 15 
•Autor: Ing Rolando Simon Titiosky.

Árboles Generales 
Intuitivamente el concepto de árbol implica 
una estructura donde los datos se 
organizan de modo que los elementos de 
información estén relacionados entre sí a 
través de ramas. 

Def i n i c i ó n  r ec u r s i va:  Árbol es un 
conjunto de nodos que: 
•  Es vacío, o bien, 
•  Tiene un nodo raíz del que descienden 
0 o más subárboles.

Árboles Generales 
•  No d o s :  conjunto finito de 
elementos. 
•  Ram as :  conjunto finito de líneas 
dirigidas, que conectan  nodos. 
•  Gr ad o  d el  No d o :  número de 
ramas descendentes con un 
nodo. 
•  Raíz:  primer nodo de un árbol no 
vacío. •  Cam i n o :  secuencia de nodos en 
los que c/nodo es adyacente al 
siguiente. 
–  Solo existe 1 camino entre la Raíz y 
un Nodo cualquier. 
–  La distancia de un Nodo a la Raíz 
determina la rapidez de búsqueda. 

15 
6 
4 

20 
10 

17 

Raiz=15 
Nodos: 15, 6, 20…. 
Ramas(15, 6); (20, 17) 
Grado del 15= G(15)=2 
G(10)=0; G(20)=2

22 

Terminología 
Nivel 0 

A B 

C 

Nivel 1 

• 
• 
• 
• 
• 

D 

E 

F 

G 

Nivel 2

• 
• 
• 

•Padres: A; B y C. 
•Hijos: De A( B y C), de B (D y E) 
•Descendentes de B: D y E 
•Ascendientes de E: B y A. 
• 
•Hermano: {B, C}, {F, G} 
•Hojas: D, E, F, G 
•Altura del Árbol: 3 
•Altura del Subárbol de B: 2 

Pad r e:  tiene Nodos sucesores. 
Hi j o s :  Nodos sucesores. 
Des c en d i ent es :  Hijos de los hijos 
A s c en d i en t es :  los padre y abuelos 
de un nodo hijo. 
Her m an o s :  2 o mas nodos del 
mismo padre. 
Ho j as :  nodo sin hijos . 
Ni v el  d e u n  n o d o :  distancia a la raíz. 
A l t u r a o  p r o f u n d i d ad  d e u n  ár b o l :  
nivel de la hoja del camino más largo 
desde la raíz más uno. 
–  La altura de un árbol vacío es 0. 

Su b árb o l :  cualquier estructura 
conectada por debajo del raíz. 
C/nodo de un árbol es la raíz de un 
subárbol que se define por el nodo y 
todos los descendientes del nodo. 

Equilibrio en Árbol Binario 
•  Factor de Equilibrio: diferencia de altura 
entre los 2 subárboles de un nodo. 
– fe=h  –h . 
d  i
– Árbol Equilibrado: –1izq=ramaIzq; 
(*raíz)–>der=ramaDer; 
} 
raizArbolBinario crearNodo(TipoElemento x) 
{  ArbolBinario a; 
a=(ArbolBinario) malloc(sizeof(Nodo)); 
a.dato=x; 
a.Izq=a.Der=NULL; 
return a; 
} 

a 
null  x 
null  x 

null 
null 

Ejemplo trivial 
ArbolBinario raíz, a1, a2; 
Pila pila; 
nuevoArbol(&a1,NULL, “Maria”,NULL); 
nuevoArbol(&a2,NULL, “Rodrigo”,NULL); 
nuevoArbol(&raiz,a1, “Esperanza”,a2); 
Insertar(&pila, raíz); nuevoArbol(&a1,NULL, “Any”,NULL); 
nuevoArbol(&a2,NULL, “Abel”,NULL); 
nuevoArbol(&raiz,a1, “Jesus”,a2); 
Insertar(&pila, raíz); 
a2=quitar(&pila); 
a1=quitar(&pila); 
nuevoArbol(&raiz,a1, “Esperanza”,a2); 
raiz 

Esperan 
Esperan 
za  
za

Esperra 
Espe a 
nza  
nza

a1 
null  Maria  null 
null  Maria null 

Void nuevoArbol(ArbolBinario* raíz, ArbolBinario ramaIzq, TipoElemento x, 
ArbolBinario ramaDer)

a2 

null  Rodrri  null 
null  Rod i  null 
go  
go

Jesus  
Jesus

null 
null 

Any  null 
Any  null 

null  Abel  null 
null  Abel  null 

Recorrido del Árbol 
•  Recorrer el Árbol significa que cada nodo sea procesado 
una vez y solo una en un secuencia determinada. 
Existen 2 enfoques generales 
–  Rec o r r i d o  en  Pr o f u n d i d ad: el proceso exige alcanzar las 
profundidades de un camino desde la raíz hacia el descendiente 
mas lejano del primer hijo, antes de proseguir con el segundo. 
–  Rec o r r i d o  en  A n c h u r a:  el proceso se realiza horizontalmente 
desde la raíz a todos su hijos antes de pasar con la 
descendencia de alguno de ellos. 

2 

1 

2 

3 

Preorden RID 
Raiz–IZQ–DER 

1 

3 ...