Hilos

Solo disponible en BuenasTareas
  • Páginas : 18 (4344 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de diciembre de 2010
Leer documento completo
Vista previa del texto
Definición de Árboles

Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz.
•Un árbol de tipo T como una estructura homogenea, que es la concatenacion de un elemento tipo T junto con un número finito de árboles disjuntos, llamados subárboles

Algunas Caracteristicas y propiedades de los arboles

•Todoarbol que no este vacio, tiene un nodo unico raiz
•Si un nodo X es apuntado por el nodo Y. Se dice que X es hijo de Y
•X es antesesor de Y si el nodo X apunta al nodo Y. X es padre de Y
•Todos los nodos que son descendientes directos(hijos) de un mismo nodo(padre), son hermanos.
•Si un nodo no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja
•Todo nodo que no es raiz, nihoja se conoce como nodo interior.
•Grado es el numero de descendientes directos de un nodo, grado de un arbol es el maximo grado de todos los nodos del arbol
•Nivel es el numero de arcos que deben recorrerse para lleagar a un nodo. Raiz tiene nivel 1
•Altura del arbol es el maximo número de niveles de todos los nodos del árbol.

Árboles Binarios

•Un arbol binario cada nodo puede tenercomo maximo dos subarboles y siempre es necesario distinguir entre el subarbol izquierdo y el subarbol derecho
•Arbol binario tipo T es una estructura homogenea que es la concatenacion de un elemento tipo T, llamado raiz, con dos arboles binarios disjuntos, llamados subarbol izquierdo y subarbol derecho.
•Se pueden aplicar para representar un arbol genealogico o para representar expresionesalgebraicas construidas con operadores binarios

•Distintos. Cuando sus estructuras son diferentes
•Similares. Cuando sus estructuras son identicas pero la informacion que contiene cada arbol es diferente.
•Equivalentes. Cuando son similares y ademas la informacion es identica entre los dos arboles.

•Se dice que un árbol binario está lleno si es un árbol binario de profundidad k que tiene (2^k) -1 nodos.    Un árbol binario lleno es aquel que contiene el número máximo de posibles nodos. Como en estos casos no existen subárboles vacíos excepto para los nodos terminales.
•Un árbol binario con n nodos y profundidad k se dice que es completo si y sólo si sus nodos se corresponden con los nodos numerados de 1 a n en el árbol binario lleno de profundidad k. Definimos un árbol binario completo(ABC) como un A.B.lleno pero con sus hojas dispuestas de tal manera que las hojas del nivel más bajo están situadas tan a la izquierda como sea posible.

Estructuras de datos Heap (montículo)

•Un árbol completo, es aquel en el que todos los niveles, con excepción del último, tiene sus nodos completos. Un arbol perfectamente equilibrado hasta el penultimo nivel, y en el ultimo nivel los nodosse encuentran agrupados a la izquierda .
•Un Heap es un árbol binario completo a izquierda, que permite implementar una cola con prioridad, y donde los elementos se almacenan cumpliendo la propiedad de que la clave de un nodo siempre es mayor (o menor) que la clave de cualquiera de sus hijos. Lo que nos asegura que la raíz del árbol, en un Heap, siempre es el elemento mayor (o menor) de laestructura.

•El acceso a los elementos del Heap en un arreglo, se hace a través de algunas operaciones aritméticas básicas:
Left(i)    : return 2*i   .- Obtiene el hijo izquierdo del elemento i.
Right(i)  : return 2*i +1 .- Obtiene el hijo derecho del elemento i.
Parent(i): return floor(i/2) .- Obtiene el padre del elemento i.


•Crear un arbol binario

Carga(nodo)
1.- Leerinformacion(info)
2.- Hacer nodo^.info=info
3.- Escribir “Existe nodo por la izquierda?”
4.- Leer repuesta
5.- Si respuesta es afirmativa
entonces
crea(otro)
hacer nodo^.izq=otro
regresar a carga(nodo^.izq)//llamada recursiva
sino
hacer nodo^.izq=Nil
6.- fin del paso 5
7.- 3.- Escribir “Existe nodo por la derecha?”
8.- Leer repuesta
9.- Si respuesta es afirmativa
entonces...
tracking img