arboles binarios


|

Índice















Abarloes:
Un arbol es un conjunto de nodos que cumplen con las relaciones padre, hijo y hermano.
Arboles binarios
Un arbol binario es aquel cuyos nodos pueden tener a lo más dos hijos.
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 apuntadoresque 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
Un árbol estrictamente binario cuyas hojas están 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 arbolcasi 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.
Partes de un árbol
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 propiadescendencia.
Llamamos padre al nodo del cual proviene el nodo hijo. Existe un nodo que no tiene padre y le llamamos raiz del arbol.
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.



Ejemplos



Ejemplo con código

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;
}
Método radixEn informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.
La mayor parte de los ordenadoresdigitales representan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente. Existen dos clasificaciones de radix sort: el de dígito menos significativo (LSD) y el de dígito más significativo (MSD). Radix sort LSD procesa lasrepresentaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo. Radix sort MSD trabaja en sentido contrario.
Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos. Radix sort LSD usa típicamente el siguiente orden: clavescortas aparecen antes que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija. Una secuencia...