Download Árboles y Árboles Binarios

Árboles y Árboles Binarios
Tomado del Libro de José Helo
Adaptaciones propias en Python
Concepto de árbol
• Un árbol es una
estructura jerárquica
sobre un conjunto de
objetos llamados nodos.
• La jerarquía entre los
nodos se establece por
medio de conectores
llamados ramas.
• Existe un nodo especial
llamado raíz o nodo
padre.
1
3
raiz
9
15
19
10
42
Concepto de árbol
• Hijos: son los descendientes
directos de un nodo. 3, 9 y
10 son hijos de 1.
• Descendientes:
corresponden a los hijos
mas los descendientes de
los hijos. Los descendientes
de 1 son 3, 9, 15, 19, 42 y
10.
• Ancestros: el padre de un
nodo más los ancestros del
padre. Los ancestros de 19
son 9 y 1.
1
3
raiz
9
15
19
10
42
Recorrido en un árbol - RID
• Raíz Izquierda Derecha
(RID): imprime la raíz y
luego todos los
subárboles de izquierda
a derecha, utilizando el
mismo recorrido.
• El recorrido IDR del
árbol ejemplo es 1 3 9
15 19 42 10
1
3
9
15
19
10
42
Recorrido en un árbol - IDR
• Izquierda Derecha Raíz
(IDR): imprime los
subárboles utilizando el
mismo recorrido, de
izquierda a derecha y
luego la raíz.
• El recorrido IDR del
árbol ejemplo es 3 15
19 42 9 10 1
1
3
9
15
19
10
42
Altura de un Árbol
• La altura de un árbol
vacío es 0.
• La altura de un árbol T
no vacío es 1 + máxima
altura de sus árboles
hijos.
Altura=3
Implementación de Árboles en Python
• Arbol(1, 3, Arbol(9, 15, 19, 42), 10)
– [1, 3, [9, 15, 19, 42], 10]
• Arbol(1,2,3,4,5)
– [1, 2, 3, 4, 5]
• Arbol()
– []
Clase Árbol
Versión recursiva
Árboles Binarios
• Es una clase especial de
árbol en donde existen a lo
más dos subárboles. Los
subárboles reciben los
nombres de sub-árbol
izquierdo y sub-árbol
derecho e interesa su
posición. El nodo raíz recibe
el nombre de nodo padre y
sus nodos asociados se
denominan hijo izquierdo e
hijo derecho. Los nodos
que no tienen hijos se
llaman hojas o nodos
terminales. Los nodos que
tienen hijos se llaman
nodos no terminales.
1
4
8
2
5
7
Recorridos en árboles binarios
Izquierda Raiz Derecha (IRD):
1
4 1 8
Raiz Izquierda Derecha (RID):
4
8
1 4 8
Izquierda Derecha Raiz (IDR):
4 8 1
Recorridos en árboles binarios
Izquierda Raiz Derecha (IRD):
4 5 2 7 1 8
Raiz Izquierda Derecha (RID):
1 4 2 5 7 8
Izquierda Derecha Raiz (IDR):
5 7 2 4 8 1
Clase Árbol Binario
Arbol Binario Ordenado
• Es una clase especial de
árbol binario en donde
todos los elementos
menores a la raíz se
encuentran en el subárbol
izquierdo y los elementos
mayores se encuentran el
subárbol derecho.
• Un recorrido IRD en este
tipo de árboles produce
una secuencia ordenada.
20
10
8
25
15
11
17
[20 [ 10 8 [15 11 17] ] 25]
Implementación con inserciones inplace