Download Árboles binarios

M.I.A Daniel Alejandro García López
ÁRBOLES BINARIOS
Los árboles ordenados de grado 2 son de especial interés puesto que
representan una de las estructuras de datos más importantes en
computación, conocida como árboles binarios.
En un árbol binario cada nodo puede tener como máximo dos
subárboles; y siempre es necesario distinguir entre el subárbol izquierdo
y el subárbol derecho.
Los árboles binarios tienen múltiples aplicaciones. Se les puede utilizar
para representar una estructura en la cual es posible tomar decisiones
con dos opciones en distintos puntos de un proceso, para representar un
árbol genealógico(construido en forma ascendente y donde se muestran
los ancestros de un individuo dado).
A) Árboles binarios de búsqueda.
27
14
47
7
59
32
50
11
77
B) Representación de una expresión algebraica.
+
*
´3.5
A
B
/
C
D
C)Árbol genealógico.
Osvaldo Cario
Battistuti
Jose Cario
Scandallo
Antonio Cario
Godoy
Maria Scandallo
Miscoria
Maria Battistuti
Valiente
Roberto Battistuti
Mazzotti
Maria Valiente
Martin
ÁRBOLES BINARIOS DISTINTOS, SIMILARES Y EQUIVALENTES
ÁRBOLES BINARIOS DISTINTOS:
Dos árboles binarios son distintos cuando sus estructuras son diferentes.En
la figura, se presentan dos ejemplos de árboles binarios disitntos.
A)
B
A
A
B)
B
A
A
C
B
B
D
C
D
ÁRBOLES BINARIOS SIMILARES:
Dos árboles binarios son similares cuando sus estructuras son idénticas,
pero la información que contienen sus nodos difiere entre sí. En la figura
se presentan dos ejemplos de árboles binarios similares.
A)
A
V
B
B)
F
A
P
C
B
T
R
D
S
ÁRBOLES BINARIOS EQUIVALENTES:
Los árboles binarios equivalentes se definen como aquellos que son
similares y además los nodos contienen la misma información. La figura
contiene dos ejemplos de árboles binarios equivalentes.
A
A)
A
B
B
B)
A
A
C
C
B
B
D
D
A)
A
B)
A
B
L
X
C
N
D
C)
D)
A
A
C
C
B
B
D
D
-El árbol de la figura C es distinto de los árboles de la figura A,B
-Los árboles de la figura A, B y D son similares.
- Los árboles de la figura A y D son equivalentes.
ÁRBOLES BINARIOS COMPLETOS
Se define un árbol binario completo como un árbol en el que todos sus
nodos, excepto los del último nivel, tienen dos hijos; el subárbol
izquierdo y el subárbol derecho. En la figura se presentan dos ejemplos
de árboles binarios completos.
A
A) DE ALTURA 3:
B
C
D
E
F
G
A
B) DE ALTURA 4:
B
C
D
H
E
I
J
F
K
L
G
M
N
O
Se puede calcular el número de nodos de un árbol binario completo de altura h
aplicando la siguiente fórmula:
NÚMERO DE NODOSABC = 2h - 1
Donde ABC significa árbol binario completo, y h la altura del
árbol.
Así, por ejemplo, un árbol binario completo de altura 5 tendrá
31 nodos, de altura 9 tendrá 511 nodos y un árbol de 17 tendrá
131071 nodos.
Cabe aclarar que existen algunos autores que definen un árbol
binario completo de otra forma; y otros que utlizan el término
lleno para referirse a completos.



1Deben enlazarse los hijos de cada nodo en
forma horizontal
2 debe enlazarse en forma vertical el nodo
padre con el hijo que se encuentra más a la
izquierda, además debe eliminarse el
vinculo de ese padre con el resto de sus
hijos
Debe rotarse el diagrama resultante
aproximadamente 45 grados hacia la
izquierda.
A
A
B
C
B
D
E
G
F
H
D
I
J
C
K
E
F
G
H
J
K
L
L
A
B
D
I
C
E
G
F
J
H
L
K
I