Lo que sea
Páginas: 5 (1042 palabras)
Publicado: 1 de diciembre de 2011
Á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 nodo distinguido 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 no tienen 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 T1y 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 que son 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 suscorrespondientes 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 un sucesor 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 diceque 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 descendiente de un nodo N ( y N se dice antecesor de L) si existe una sucesión de hijos desde N hasta L. En particular, L se dice descendiente izquierdo o derecho de N dependiendo de sipertenece al subárbol izquierdo o al derecho de N.
También se usa esa terminología de teoría de grafos y de horticultura para un árbol binario T. específicamente, la línea dibujada entre un nodo N de T y un sucesor suyo se llama ariste, y una secuencia de aristas consecutivas se denomina camino. Un nodo terminal se llama hoja y un camino que termina en una hoja se llama rama.
Cada nodo de unárbol binario T tiene asignado un número de nivel, de la forma que sigue. A la raíz R del árbol T se le asigna el numero de nivel 0, y al resto de los nodos se le asigna un numero de nivel que es mayor en 1 que el numero de nivel de su padre. Más aun, aquellos nodos con el mismo número de nivel se dice que pertenecen a la misma generación.
La profundidad o altura (o altura) de un árbol T es elnúmero máximo de nodos de una rama de T. Equivale a 1 más que el mayor numero de nivel de T.
Dos árboles binarios T y T’ se dice que son 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.
La terminología de relaciones familiares, de teoríade grafos y horticultura se usa para los árboles generales de la misma forma que para los árboles binarios. En particular, si N es un nodo con sucesores S 1, S 2,…, S m, se dice que N es el padre de los S i , los S i son hijos de N y los S i son hermanos unos de otros.
El termino "árbol" aparece, con significados ligeramente diferentes, en muchas áreas diferentes de las matemáticas y de la...
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 nodo distinguido 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 no tienen 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 T1y 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 que son 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 suscorrespondientes 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 un sucesor 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 diceque 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 descendiente de un nodo N ( y N se dice antecesor de L) si existe una sucesión de hijos desde N hasta L. En particular, L se dice descendiente izquierdo o derecho de N dependiendo de sipertenece al subárbol izquierdo o al derecho de N.
También se usa esa terminología de teoría de grafos y de horticultura para un árbol binario T. específicamente, la línea dibujada entre un nodo N de T y un sucesor suyo se llama ariste, y una secuencia de aristas consecutivas se denomina camino. Un nodo terminal se llama hoja y un camino que termina en una hoja se llama rama.
Cada nodo de unárbol binario T tiene asignado un número de nivel, de la forma que sigue. A la raíz R del árbol T se le asigna el numero de nivel 0, y al resto de los nodos se le asigna un numero de nivel que es mayor en 1 que el numero de nivel de su padre. Más aun, aquellos nodos con el mismo número de nivel se dice que pertenecen a la misma generación.
La profundidad o altura (o altura) de un árbol T es elnúmero máximo de nodos de una rama de T. Equivale a 1 más que el mayor numero de nivel de T.
Dos árboles binarios T y T’ se dice que son 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.
La terminología de relaciones familiares, de teoríade grafos y horticultura se usa para los árboles generales de la misma forma que para los árboles binarios. En particular, si N es un nodo con sucesores S 1, S 2,…, S m, se dice que N es el padre de los S i , los S i son hijos de N y los S i son hermanos unos de otros.
El termino "árbol" aparece, con significados ligeramente diferentes, en muchas áreas diferentes de las matemáticas y de la...
Leer documento completo
Regístrate para leer el documento completo.