Vectores y matrices

Solo disponible en BuenasTareas
  • Páginas : 5 (1054 palabras )
  • Descarga(s) : 0
  • Publicado : 3 de noviembre de 2011
Leer documento completo
Vista previa del texto
Tipos de árboles binarios
* Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
* Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
* Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura)
*A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de laizquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
ÁRBOLES

Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas.
Un árbol es unaestructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.
Existen diferentes formas de representación de un árbol, entre las más comunes se tienen las siguientes: Mediante círculos y flechas,Mediante paréntesis anidados, Mediante notación decimal de Dewey. Algunas veces se incluye entre los árboles el árbol nulo vacío, el cual, es un árbol sin nodos que se representa mediante la letra .
Cualquier nodo del árbol podría tener un número arbitrario de nodos hijos, a esto se le conoce como un árbol general, como se muestra en la siguiente figura. Si se limita el número de nodos hijospara cada nodo del árbol, digamos a un número n > 2 (llamado la aridad del árbol), entonces el árbol de aridad n es llamado n-ario.
La terminología que por lo regular se utiliza para el manejo de árboles es la siguiente:
-HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
-PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y.También se dice que X es antecesor de Y.
-HERMANO. Dos nodos serán hermanos si son descendientes directos de un mismo nodo.
-HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones.
-NODO INTERIOR. Es un nodo que no es raíz ni terminal.
-GRADO. Es el número de descendientes directos de un determinado nodo.
-GRADO DEL ARBOL Es el máximo grado de todos los nodos delárbol.
-NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
-ALTURA. Es el máximo número de niveles de todos los nodos del árbol.
-PESO. Es el número de nodos del árbol sin contar la raíz.
-LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíztiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.
ORDEN DE LOS NODOS. Generalmente los árboles de un nodo se ordenan de izquierda a derecha. Si no se toma en cuenta el orden de los nodos hijos, entonces se habla de un árbol no ordenado.
ÁRBOLES BINARIOS
Un árbol binario es un árbol de grado 2, en el que todo nodo del árbol tiene un subárbolbinario izquierdo y derecho asociados.
Longitud de Camino (Interno) de un Árbol
La Longitud de Camino Interno (LCI) de un árbol es la suma de los niveles de todos los nodos.
Longitud de camino interno (LCI). Ya dijimos que el nivel del árbol es la distancia que se recorre desde la raíz hasta un nodo particular, contando la raíz como 1. La suma de las distancias que deben recorrerse para llegar...
tracking img