Arboles Bb

Estructuras de datos y
algoritmos
.

Arboles

Nodo
La anatomía de un nodo en un árbol
binario es la siguiente:
A
Puntero
al
subarbo
l
izquierd
o

Puntero
al
subarbo
l
derecho

Árboles
A
B

H

Árbol con 8 nodos

D

C

E

G

F

Arboles

Raiz
Es el nodo que no es apuntado por
ningún otro nodo
A
D

B

H

C

E

G

F

Arboles

Padre
X es el padre de Y si X apunta a Y
A
D

B

H

A es el padre de By
de D

C

E

G

F

B es el padre de H y
C
H no es padre de
nadie
A no es el padre de
H!

Arboles

Hijo
Y es el hijo de X si X apunta a Y
A

B y D son hijos de A
D

B

H

C

E

G

H y C son hijos de B
F

H no es un hijo de A

Arboles

Hoja
Una hoja es un nodo que no tiene hijos
A
D

B

H

C

E

G

F

Arboles

Nodo no terminal
Es un nodo que no es hoja
A
D

B

H

C

E

G

F

Arboles

Camino
Esel conjunto de nodos que se deben
visitar con el propósito de llegar a un
nodo especifico
Un árbol siempre se examina hacia abajo
Los apuntadores derecho e izquierdo de
cualquier nodo apuntan al árbol derecho
o izquierdo que siguen a ese nodo.
Nunca apuntan a los nodos precedentes

Árboles
A
D

B

C

F

E
G

El camino A->D->F
se presenta en el
árbol
El camino
G->E->D->A->B>C no se da en el
caminoArboles

Longitud
Es el número de nodos que se deben
recorrer para pasar de un nodo a otro

Árboles
A
D

B

C

F

E
G

La longitud entre A y G
es 3
La longitud entre A y A
es 0
La longitud entre D y F
es 1

Arboles

Ancestro
Un nodo X es ancestro de Y si existe una
camino ente X y Y

Árboles
A
D

B

C

F

E
G

Es G un ancestro de B?
Es B un ancestro de E?
Es A un ancestro de F?

ArbolesNivel
Cada nodo tiene un nivel dentro de un
árbol binario. Por definición el nodo raíz
tiene un nivel 0 y los demás nodos tiene el
nivel de su padre más 1

Árboles
A
D

B

C

F

E
G

Nivel
0
Nivel
1
Nivel
2
Nivel
3

Arboles

Grado de un nodo
Es el número de hijos
El grado de un nodo terminal siempre es 0
En un árbol binario el grado de cada nodo
varia entre 0 y 2

Árboles
A
D

B

C

F

E
G

El
ElEl
El
0

grado
grado
grado
grado

de
de
de
de

A es 2
D es 2
E es 1
C, G y F es

Arboles

Altura de un árbol
Es el nivel de la hoja o de las hojas que
están más distantes de la raíz

Árboles
A

La altura del árbol es 3

D

B

C

F

E
G

Árboles
A
D

B

C
I

J
K

F

E

H

G

Cuántos nodos tiene. 11
Cuál es el nodo raíz. A
Cuáles son los nodos no
terminales. A,B,D,H,E,J.
Cuáles son las hojas.C,F,I,G,K.
Cuál es el grado del nodo
E. 1
Cuál es el nivel del nodo I.
3
Cuál es la longitud entre
A y K. 4

Arboles

Árbol binario
Un árbol binario es un conjunto finito de
elementos que está vacío o dividido en tres
subconjuntos separados.
El primer subconjunto contiene un elemento
único llamado raíz del árbol. Los otros dos
subconjuntos son por si mismos árboles
binarios y se les conoce comosubárboles
izquierdo y derecho del árbol original.

Árboles
A

E

C
J

Es este un árbol
binario?

D

B

F
G

Arboles

Árbol estrictamente binario
Si cada nodo que no es una hoja en un árbol
binario tiene subárboles izquierdo y derecho
que no están vacíos, se clasifica como árbol
estrictamente binario

Árboles
A
D

B
E
J

F
G

Es este un árbol
estrictamente
binario?

Árboles
A
D

B
E

H
J

F
G

Eseste un árbol
estrictamente
binario?

Arboles

Árbol binario completo
Un árbol que es estrictamente binario y tiene
todas sus hojas en el nivel d, donde d es la
profundad del árbol, es un árbol binario
completo

Árboles
A

Es este un árbol
binario completo?

D

B
E
J

F
G

Árboles
A

H

Es este un árbol
binario completo?

D

B
G

E

F

Arboles

Árbol binario completo
Un árbol binario completotiene 2l nodos en
cada nivel l, donde l varia entre 0 y d
d

totalNodos = 2 + 2 + 2 + .
. .j 0+2 j2d =
= 2d+1 -1
0

•Cuántos

1

2

nodos no terminales tiene un árbol
binario completo?
•Cuál es la profundidad de un árbol binario

Arboles

Árbol de búsqueda binaria
Un árbol binario en el que los elementos
del subárbol izquierdo de un nodo n son
menores que el contenido de n, y que
todos los...