Download Árboles Binarios de Búsqueda

Árboles Binarios
* Recorridos
* Tipo
ESTRUCTURA DE DATOS II
Ing. Freddy Melgar Algarañaz
Recorridos


Recorrer el árbol es “pasar por” o “visitar”
todos los nodos del mismo.
Recorridos típicos:



Preorden
Inorden
Postorden
(R-I-D)
(I-R-D)
(I-D-R)
Recorrido Preorden

Proceso:



Visita el nodo raíz del
árbol.
Recorre el preorden el
subárbol izquierdo del
nodo raíz.
Recorre el preorden el
subárbol derecho del
nodo raíz.
21
33
13
10
18
25
40
Recorrido en Preorden
21, 13, 10, 18, 33, 25, 40

Aplicación: Generar
una réplica del árbol.
Recorrido Inorden

Proceso:




Recorre en inorden el
subárbol izquierdo.
Visita la raíz del árbol.
Recorre en inorden el
subárbol derecho.
Aplicación: Desplegar
en orden creciente los
elementos del árbol si
este es un ABB.
21
33
13
10
18
25
40
Recorrido en Inorden
10, 13, 18, 21, 25, 33, 40
Recorrido Postorden

Proceso:



Recorre en postorden
el subárbol izquierdo.
Recorre en postorden
el subárbol derecho.
Visita la raíz del árbol.
21
33
13
10
18
25
40
Recorrido en Postorden

Aplicación: Liberar los
nodos de un árbol.
10, 18, 13, 25, 40, 33, 21
Ejemplo....
12
21
7
4
Recorrido en Preorden
25
16
9
12, 7, 4, 2, 9, 8, 11, 21, 16, 19, 25
Recorrido en Inorden
2
8
11
19
2, 4, 7, 8, 9, 11, 12, 16, 19, 21, 25
Recorrido en Postorden
2, 4, 8, 11, 9, 7, 19, 16, 25, 21, 12
Ejemplo....
#
8
@
A
2
Recorrido en Preorden
%
#, @, 2, $, 8, A, 5, %
Recorrido en Inorden
$
5
2, $, @, #, 5, A, 8, %
Recorrido en Postorden
$, 2, @, 5, A, %, 8, #
Dados 2 recorridos, construir el árbol
Dado los siguientes recorridos:
Recorrido en Preorden
Paso
1
Paso
2
$, %, A, &, #
A, %, &
$
$
#
A
$, %, A, &, #
Recorrido en Inorden
$, %, A, &, #
Paso
3
Paso
4
$, %, A, &, #
$
A, %, &, $, #
%
#
$
&
%
A
Paso
5
A
$, %, A, &, #
$
El Preorden también indica cuál es
el siguiente valor a procesar
#
%
A
&
&
$, %, A, &, #
El Preorden indica que la raíz es: $
El Inorden indica quién está a la
izquierda y quién a la derecha
%
#
&
#
Dados 2 recorridos, construir el árbol
Dado los siguientes recorridos:
Recorrido en Postorden
Paso
1
Paso
2
A, &, %, #, $
A, %, &
A, &, %, #, $
A, %, &
$
#
$
#
A, &, %, #, $
Recorrido en Inorden
Paso
3
Paso
4
A, &, %, #, $
$
A, %, &, $, #
A
%
&
$
#
El Postorden indica que la raíz es: $
El Inorden indica quién está a la
izquierda y quién a la derecha
A, &, %, #, $
A
#
%
&
Paso
5
A, &, %, #, $
$
El Postorden también indica cuál
es el siguiente valor a procesar
#
%
A
&
1. Visitar raiz
2. Preorden al Subarbol Izq.
3. Preorden al Subarbol Der.
Recorrido PREORDEN
G
1
D
K
2
8
B
E
H
M
3
6
9
12
A
C
F
J
L
4
5
7
10
13
I
11
G-D
G-D-B-A-C-E
G-D-B-A-C
G-D-B-A
G-D-B
G-D-B-A-C-E-F
G-D-B-A-C-E-F-K
G-D-B-A-C-E-F-K-H
G-D-B-A-C-E-F-K-H-J
G-D-B-A-C-E-F-K-H-J-I
G-D-B-A-C-E-F-K-H-J-I-M
G-D-B-A-C-E-F-K-H-J-I-M-L
1. Inorden al Subarbol Izq.
2. Visitar raiz
3. Inorden al Subarbol Der.
Recorrido INORDEN
G
7
D
K
4
11
B
E
H
M
2
5
10
13
A
C
F
J
L
1
3
6
9
12
I
8
G-D
G-D-B-A-C-E
G-D-B-A-C
G-D-B-A
G-D-B
G-D-B-A-C-E-F
G-D-B-A-C-E-F-K
G-D-B-A-C-E-F-K-H
G-D-B-A-C-E-F-K-H-J
G-D-B-A-C-E-F-K-H-J-I
G-D-B-A-C-E-F-K-H-J-I-M
A-B-C-D-E-F-G-I-J-H-K-L-M
1. Postorden al Subarbol Izq.
2. Postorden al Subarbol Der.
3. Visitar raiz
Recorrido POSTORDEN
G
13
D
K
6
12
B
E
H
M
3
5
9
11
A
C
F
J
L
1
2
4
8
10
I
7
G-D
G-D-B-A-C-E
G-D-B-A-C
G-D-B-A
G-D-B
G-D-B-A-C-E-F
G-D-B-A-C-E-F-K
G-D-B-A-C-E-F-K-H
G-D-B-A-C-E-F-K-H-J
G-D-B-A-C-E-F-K-H-J-I
G-D-B-A-C-E-F-K-H-J-I-M
A-C-B-F-E-D-I-J-H-L-M-K-G
Árbol Binario Lleno

Un árbol de altura h, esta lleno si



Todas sus hojas esta en el nivel h
Los nodos de altura menor a h tienen siempre
2 hijos
Recursiva

Si T esta vacío,


Entonces T es un árbol binario lleno de altura 0
Si no esta vacío, y tiene h>0

Esta lleno si los subárboles de la raíz, son ambos
árboles binarios llenos de altura h-1
Árbol Binario Completo

◦
◦

Un árbol de altura h esta completo si:
Es un árbol en el que todos sus nodos,
excepto los del ultimo nivel, tienen dos
hijos.
Número de nodos en un árbol binario
completo = 2h –1 (en el ejemplo h = 4, 
15) esto nos ayuda a calcular el nivel de
árbol necesario para almacenar los datos
de una aplicación.
Si un árbol esta lleno, también esta
completo.
Otros

Un árbol equilibrado es cuando:


La diferencia de altura entre los subárboles de
cualquier nodo es máximo 1
Un árbol binario equilibrado totalmente:

Los subárboles izquierdo y derecho de cada
nodo tienen las misma altura: es un árbol lleno

Un árbol completo es equilibrado

Un árbol lleno es totalmente equilibrado
Árboles Distintos
Dos o más árboles son distintos cuando:
•Tienen el mismo contenido, pero estructura diferente
•Tienen la misma estructura, pero contenido diferente
Árboles Similares
Dos árboles son
similares,
cuando
tienen la misma
estructura (forma),
pero
contenido
diferente.
Árboles Equivalentes
Dos árboles son
equivalentes
cuando
son
similares (tienen la
misma estructura o
forma), y el mismo
contenido.