Download Árboles y Árboles Binarios
Document related concepts
Transcript
Á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