temas variados
Páginas: 9 (2085 palabras)
Publicado: 8 de mayo de 2013
Introducción
El siguiente trabajo trata sobre la estructura de datos no lineales llamada árbol. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos, y tablas de contenidos. Vamos a profundizar en un tipo especial de árbol llamado árbol binario, la cual puede ser implementado fácilmente enla computadora; aunque en un árbol puede parecer muy restrictivo. También se va a ampliar sobre árboles más generales y puntos con relación a los árboles binarios; entre estos tenemos a la terminología, los árboles binarios complementos, árboles binarios de búsqueda, búsqueda e inserción en árboles binarios de búsqueda, árboles generales, representación de árboles generales en la computadora ycorrespondencia entre los árboles generales y árboles binarios.
Concepto de Árboles.
En ciencias de la computación, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, siexiste un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.
El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemploregistros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.
Árboles Binarios
Un árbol binario T se define como un conjunto finito de elementos, llamados nodos, de forma que:
T es vacío ( en cuyo caso se llama árbol nulo o árbol vació) o
T contiene un nododistinguido R, llamado raíz de T, y los restantes nodos de T forman un par ordenado de árboles binarios disjuntos T1 y T2.
Si T contiene una raíz R, los dos árboles T1 y T2 se llaman, respectivamente, subárboles izquierdo y derecho de la raíz R. Si T1 no es vació , entonces su raíz se llama sucesor izquierdo de R; y análogamente, si T2 no es vació, su raíz se llama sucesor derecho de R.
Observe que :B es un sucesor izquierdo y C un sucesor derecho del nodo A.
El subárbol izquierdo de la raíz A consiste en los nodos B, D, E y F, y el subárbol derecho de A consiste en los nodos C , G, H, J, K y L.
Figura (1)
Cualquier nodo N de un árbol binario T tiene 0, 1 ó 2 sucesores. Los nodos A,B,C y H tienen dos sucesores, los nodos R y J sólo tienen un sucesor , y los nodos D,F, G,L y K notienen sucesores. Los nodos sin sucesores se llaman nodos terminales.
La definición anterior del árbol binario T es recursiva, ya que T se define en términos de los subárboles binarios T1 y T2. Esto significa, en particular, que cada nodo N de T contiene un subárbol izquierdo y uno derecho. Más aun, si N es un nodo terminal, ambos árboles están vacíos.
Dos árboles binarios T y T’ se dicen queson similares si tienen la misma estructura o, en otras palabras, si tienen la misma forma. Los árboles se dice que son copias si son similares y tienen los mismos contenidos en sus correspondientes nodos.
Terminología
Frecuentemente se usa una terminología de relaciones familiares para describir las relaciones entre los nodos de un árbol T. En particular, suponga que N es un nodo de T con unsucesor izquierdo S1 y un sucesor derecho S2. Entonces N se llama padre de S1 y S2. Análogamente, S1 se llama el hijo izquierdo de N y S2 el hijo derecho de N. Es mas, S1 y S2 se dice que son hermanos. Cada nodo N de un árbol binario T, excepto la raíz, tiene un único padre, llamado predecesor de N.
Los términos descendientes y antecesor tienen su significado usual. Así, un nodo L se dice...
El siguiente trabajo trata sobre la estructura de datos no lineales llamada árbol. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos, y tablas de contenidos. Vamos a profundizar en un tipo especial de árbol llamado árbol binario, la cual puede ser implementado fácilmente enla computadora; aunque en un árbol puede parecer muy restrictivo. También se va a ampliar sobre árboles más generales y puntos con relación a los árboles binarios; entre estos tenemos a la terminología, los árboles binarios complementos, árboles binarios de búsqueda, búsqueda e inserción en árboles binarios de búsqueda, árboles generales, representación de árboles generales en la computadora ycorrespondencia entre los árboles generales y árboles binarios.
Concepto de Árboles.
En ciencias de la computación, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, siexiste un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.
El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemploregistros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.
Árboles Binarios
Un árbol binario T se define como un conjunto finito de elementos, llamados nodos, de forma que:
T es vacío ( en cuyo caso se llama árbol nulo o árbol vació) o
T contiene un nododistinguido R, llamado raíz de T, y los restantes nodos de T forman un par ordenado de árboles binarios disjuntos T1 y T2.
Si T contiene una raíz R, los dos árboles T1 y T2 se llaman, respectivamente, subárboles izquierdo y derecho de la raíz R. Si T1 no es vació , entonces su raíz se llama sucesor izquierdo de R; y análogamente, si T2 no es vació, su raíz se llama sucesor derecho de R.
Observe que :B es un sucesor izquierdo y C un sucesor derecho del nodo A.
El subárbol izquierdo de la raíz A consiste en los nodos B, D, E y F, y el subárbol derecho de A consiste en los nodos C , G, H, J, K y L.
Figura (1)
Cualquier nodo N de un árbol binario T tiene 0, 1 ó 2 sucesores. Los nodos A,B,C y H tienen dos sucesores, los nodos R y J sólo tienen un sucesor , y los nodos D,F, G,L y K notienen sucesores. Los nodos sin sucesores se llaman nodos terminales.
La definición anterior del árbol binario T es recursiva, ya que T se define en términos de los subárboles binarios T1 y T2. Esto significa, en particular, que cada nodo N de T contiene un subárbol izquierdo y uno derecho. Más aun, si N es un nodo terminal, ambos árboles están vacíos.
Dos árboles binarios T y T’ se dicen queson similares si tienen la misma estructura o, en otras palabras, si tienen la misma forma. Los árboles se dice que son copias si son similares y tienen los mismos contenidos en sus correspondientes nodos.
Terminología
Frecuentemente se usa una terminología de relaciones familiares para describir las relaciones entre los nodos de un árbol T. En particular, suponga que N es un nodo de T con unsucesor izquierdo S1 y un sucesor derecho S2. Entonces N se llama padre de S1 y S2. Análogamente, S1 se llama el hijo izquierdo de N y S2 el hijo derecho de N. Es mas, S1 y S2 se dice que son hermanos. Cada nodo N de un árbol binario T, excepto la raíz, tiene un único padre, llamado predecesor de N.
Los términos descendientes y antecesor tienen su significado usual. Así, un nodo L se dice...
Leer documento completo
Regístrate para leer el documento completo.