Estructuras de datos Un arbol es un conjunto de nodos que cumplen con las relaciones padre, hijo y hermano. Llamamos hijos de un nodo a todos los nodos que podemos llegar directamente por medio de un apuntador hacia ellos y descendencia a todos los que pudieramos llegar a traves de los hijos y su propia descendencia. Llamamos padre al nodo del cual proviene el nodo hijo. Existe un nodo que no tiene padre y le llamamos raiz del arbol. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos Llamamos hermanos a todos los nodos que tienen el mismo padre. Llamamos hoja al nodo que no tiene hijos. Podemos definir un árbol de manera recursiva diciendo que un árbol sin nodos esta vacío. Un arbol es un nodo llamado raiz cuyos hijos son tambien arboles(vacios o no). Notemos que una lista es un arbol cuyos nodos solo tienen un hijo. Un arbol binario es aquel cuyos nodos pueden tener a lo más dos hijos. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

1

Estructuras de datos Un arbol cuyos nodos tienen 0 o 2 hijos se llama estrictamente binario. Si algún nodo tiene un solo hijo ya no lo es. Llamamos nivel al numero de apuntadores que se tienen que recorrer para llegar a un nodo a partir la raiz, asi el nodo raiz esta en el nivel 0 y sus hijos en el nivel 1. La profundidad de un árbol es igual al mayor nivel de sus hojas Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos Un árbol estrictamente binario cuyas hojas estan todas en el mismo nivel se llama arbol binario completo. Un arbol estrictamente binario cuyas hojas estan a lo más en dos niveles diferentes se llama arbol casi completo y se dice que el arbol esta balanceado. Los arboles binarios son muy importantes en las operaciones de busqueda y para ello deben mantenerse balanceados. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

2

Estructuras de datos raiz 1

2

4

3

5

6

7

El nodo 1 es el nodo raiz. Los nodos 2 y 3 son el hijo izquierdo y el hijo derecho del nodo raiz. Los nodos 4, 5, 6 y 7 son las hojas del arbol.

El padre del nodo 5 es 2 y del nodo 7 es 3. Los nodos 2 y 3 son hermanos. La profundidad del arbol es 2.

Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos El arbol de la lamina anterior tambien es un arbol estrictamente binario y ademas completo. Para mayores ejemplos de arboles binarios y su clasificación consultar el libro de Tenenbaum en el capítulo de arboles.

Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

3

Estructuras de datos Para implementar un arbol binario es necesario crear primero una clase Nodo_Arbol capaz de almacenar cualquier dato y que tenga dos apuntadores a los hijos izquierdo y derecho. template class Nodo_Arbol: public Nodo{ public: Nodo_Arbol(T); T GetDato(){ return Nodo::GetDato();} Nodo_Arbol* GetDer(){ return (Nodo_Arbol *)GetSiguiente();}//cast de Nodo * a Nodo_Arbol * void SetDer(Nodo_Arbol *d){SetSiguiente((Nodo *)d);}//cast de Nodo_Arbol * a Nodo * Nodo_Arbol* GetIzq(){ return izq;} void SetIzq(Nodo_Arbol *d){izq = d;} private: Nodo_Arbol *izq; }; template Nodo_Arbol::Nodo_Arbol(T x): Nodo(x){ //manda a llamar al constructor de Nodo izq = NULL; }

Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos La implementación de Nodo_Arbol usa herencia y hereda las caracteristicas de Nodo, es decir usa las propiedades y la interfaz de la clase Nodo que se uso para crear Listas. Para tener una nomenclatura consistente se renombro el apuntador siguiente para convertirlo en der, y se añadio el apuntador al nodo izq. Para ello fue necesario hacer conversiones de tipos o cast. Estas conversiones deben manejarse con cuidado para evitar referencias erroneas a la memoria. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

4

Estructuras de datos La otra opción es crear la clase Nodo_Arbol desde cero como se explico en clase. Es decir se crea una clase que contenga espacio para almacenar un dato y los apuntadores der e izq hacia nodos del arbol. La interfaz resultaria muy parecida a la de los nodos de la clase Lista. Para evitar la conversión entre objetos de un tipo a otro puede llegar a preferirse este metodo, sobre todo tomando en cuenta la simplicidad de la clase Nodo_Arbol. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos Ahora podemos pasar a analizar las operaciones que se pueden hacer con un árbol. Inserta(ELEMENTO x, Nodo_Arbol t) inserta el elemento x en el arbol t. La regla es que todos los nodos se insertan como hojas, no puede haber nodos repetidos y todos los descendientes izquierdos de un nodo son menores a el y los derechos son mayores a ese mismo nodo. A un arbol de este tipo le llamamos arbol de busqueda binaria. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

5

Estructuras de datos Anula(Nodo_Arbol *t) convierte el arbol t en un arbol vacío. El proceso de eliminación comienza en las hojas. Recorrer_en_orden(Nodo_Arbol *t) recorre los nodos del arbol de acuerdo a la siguiente regla recursiva: Recorrer_en_orden(SUBARBOL_IZQ); Raiz; Recorrer_en_orden(SUBARBOL_DER); Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos Recorrer_en_preorden(Nodo_Arbol *t) recorre los nodos del arbol de acuerdo a la siguiente regla recursiva: Raiz; Recorrer_en_preorden(SUBARBOL_IZQ); Recorrer_en_preorden(SUBARBOL_DER); Recorrer_en_postorden(Nodo_Arbol *t) recorre los nodos del arbol de acuerdo a la siguiente regla recursiva: Recorrer_en_postorden(SUBARBOL_IZQ); Recorrer_en_postorden(SUBARBOL_DER); Raiz; Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

6

Estructuras de datos ELEMENTO Get_Dato(Nodo_Arbol *nd) devuelve el dato almacenado en el nodo nd. Nodo_Arbol *GetIzq(Nodo_Arbol *nd) devuelve un apuntador al hijo izquierdo del nodo nd. Nodo_Arbol *GetDer(Nodo_Arbol *nd) devuelve un apuntador al hijo derecho del nodo nd. BOOL SetDer(Nodo_Arbol *nd, ELEMENTO x) devuelve verdadero si pudo insertar un nuevo nodo conteniendo a x como hijo derecho del nodo nd. BOOL SetDer(Nodo_Arbol *nd, ELEMENTO x) igual que SetDer pero como hijo izquierdo del nodo nd. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos Nodo_Arbol *Padre(Nodo_Arbol *nd) devuelve un apuntador al padre del nodo nd. Nodo_Arbol *Hermano(Nodo_Arbol *nd) devuelve un apuntador al hermano del nodo nd. BOOL EsIzq(Nodo_Arbol *nd) devuelve verdadero si el nodo nd es hijo izquierdo. BOOL EsDer(Nodo_Arbol *nd) devuelve verdadero si el nodo nd es hijo derecho. BOOL EsHoja(Nodo_Arbol *nd) devuelve verdadero si el nodo nd es hoja. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

7

Estructuras de datos La siguiente secuencia de inserciones generara el arbol de la siguiente figura. 6, 3, 9, 10, 5, 7, 2. raiz aux 6

3

2

9

5

7

10

Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos El recorrido en orden del mismo seria: 2, 3, 5, 6, 7, 9, 10. El recorrido en preorden seria: 6, 3, 2, 5, 9, 7, 10. El recorrido en postorden seria: 2, 5, 3, 7, 10, 9, 6. Una llamada a Get_Dato(aux) devolveria 3. Una llamada a Padre(aux) devolveria un apuntador al nodo raiz. Una llamada a Hermano(aux) devolveria un apuntador al nodo que contiene al 9. Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

8

Estructuras de datos Un procedimiento inserta quedaria como sigue: template BOOL Arbol::Inserta2(T x, Nodo_Arbol *ptr){ if(ptr == NULL){//Arbol vacio raiz = creanodo(x); return VERDADERO; } else{//arbol no vacio if(x > ptr->GetDato())//El dato es mayor que el de el nodo actual if(ptr->GetDer() == NULL){//hijo derecho esta vacio ptr->SetDer(creanodo(x)); return VERDADERO; } else//el hijo derecho no esta vacio return Inserta2(x, ptr->GetDer()); if(x < ptr->GetDato())//El dato es menor que el de el nodo actual if(ptr->GetIzq() == NULL){//hijo izquierdo esta vacio ptr->SetIzq(creanodo(x)); return VERDADERO; } else//hijo izquierdo no esta vacio return Inserta2(x, ptr->GetIzq()); return FALSO; } }

Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

Estructuras de datos Un procedimiento Anula quedaria como sigue: template void Arbol::Anula(){ Nodo_Arbol *aux1, *aux2; while(raiz != NULL){//mientras el arbol no este vacio aux1 = raiz;//aux1 seria el nodo a eliminar while(!EsHoja(aux1)){//minetras aux1 no sea una hoja aux2 = aux1;//aux2 es el padre de aux1 if (aux1->GetIzq() != NULL)//buscar hoja izquierda aux1 = aux1->GetIzq(); else77buscar hoja derecha aux1 = aux1->GetDer(); } if (aux1 == raiz){//caso especial, la raiz no tiene padrre delete aux1; raiz = NULL; break; } if(aux2->GetIzq() == aux1)// es aux1 hijo izquierdo? aux2->SetIzq(NULL);//apuntar hijo izquierdo a NULL else aux2->SetDer(NULL);//apuntar hijo derecho a NULL delete aux1;//eliminar aux1 } }

Ing. Ing.Jorge JorgeA. A.Hernández HernándezP.: P.:Arboles Arboles

9