arboles
Páginas: 6 (1418 palabras)
Publicado: 7 de abril de 2013
LOS ÁRBOLES DENTRO DE LA ESTRUCTURA DE DATOS
I.- FUNDAMENTACIÓN
Un árbol la raíz es el único nodo que no tiene ancestros propios.
Un nodo sin descendientes propios se conoce como una hoja.
Un subárbol de un árbol es un nodo junto con todos sus descendientes.
El peso de un nodo en un árbol es la longitud del camino más largo del nodo a una hoja.
El peso de un árbol es elpeso de la raíz.
La profundidad de un nodo es la longitud del camino único de la raíz al nodo.
La profundidad de un árbol es la profundidad de la hoja más profunda.
Hay dos formas tradicionales de representar un árbol binario en memoria:
Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
Por medio de arreglos.
Sin embargo la más utilizada es laprimera, puesto que es la más natural para tratar este tipo de estructuras.
Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:
El árbolbinario de búsqueda con su estructura en árbol permite que cada nodo apunte a otros dos nodos :uno que le precede en la lista y otro que lo sigue. Los nodos apuntados pueden ser cualesquiera de la lista siempre que satisfagan esta regla básica : El nodo a la izquierda contiene un valor mas pequeño que el nodo que el nodo que le apunta y el nodo a la derecha contiene un valor mas grande.
Comohemos indicado cada árbol binario tiene un único primer elemento llamado la raíz del árbol. En la figura el nodo que contiene una A es el nodo raíz. El nodo raíz puede tener un nodo a su izquierda llamado hijo izquierdo y/o un nodo a su derecha llamado su hijo derecha. Por ejemplo el nodo que contiene J tiene un hijo izquierdo conteniendo una B y un hijo derecho conteniendo una D. El nodo quecontiene una A es llamado el padre de los nodos que contienen una B y D.Cualquier nodo en un árbol binario puede tener 0, 1 , 2 hijos. Un nodo sin hijos se llama hoja .Dos nodos son hermanos si tienen el mismo padre. Los nodos que contienen F y G son ambos hijos del nodo que contiene una C, por tanto son hermanos. Un nodo es un antecesor de ese nodo si es el padre de este, o el padre de algún otroantecesor de ese nodo.
El nivel de un nodo se refiere a su distancia al nodo raíz. Si designamos el nivel de la raíz como 0, los nodos que contienen B y D son nodos de Nivel 1 los nodos conteniendo F ,F , G, H , I ,J son nodos de Nivel 2.
Los campos izquierdo y Derecho que contienen punteros se usaran en los algoritmos para árbol, para enlazar los datos almacenados en el árbol. Estos camposno son accedidos directamente por el usuario del árbol. El campo Info que contiene los nodos que interesan al usuario pueden ser de cualquier tipo de datos.
Cada nodo de un árbol binario puede tener a lo sumo dos hijos; por tanto podemos representar una expresión binaria simple como un árbol binario de dos niveles. La raíz del nodo contiene el operador y los hijos contienen los operandos.Las distintas partes de una expresión complicada tienen diferentes niveles de precedencia de evaluación. Por ejemplo cuando vemos la expresión (A+B)*C sabemos que la expresión (A+B) se evalúa antes que la de multiplicación. Cuando escribimos la expresión infija con el operador entre losoperandos, dependemos de algún esquema de precedencia del operador y del uso de paréntesis para describir unaexpresión de forma precisa . Sin embargo cuándo usamos un árbol binario para representar una expresión, los paréntesis no son necesarios para indicar la precedencia.
Comencemos en el nodo raíz y evaluemos la expresión. La raíz contiene el operador, luego miramos sus hijos para obtener dos operandos como el nodo a la izquierda de la raíz contiene otro operador - sabemos que el subárbol izquierdo...
I.- FUNDAMENTACIÓN
Un árbol la raíz es el único nodo que no tiene ancestros propios.
Un nodo sin descendientes propios se conoce como una hoja.
Un subárbol de un árbol es un nodo junto con todos sus descendientes.
El peso de un nodo en un árbol es la longitud del camino más largo del nodo a una hoja.
El peso de un árbol es elpeso de la raíz.
La profundidad de un nodo es la longitud del camino único de la raíz al nodo.
La profundidad de un árbol es la profundidad de la hoja más profunda.
Hay dos formas tradicionales de representar un árbol binario en memoria:
Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
Por medio de arreglos.
Sin embargo la más utilizada es laprimera, puesto que es la más natural para tratar este tipo de estructuras.
Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:
El árbolbinario de búsqueda con su estructura en árbol permite que cada nodo apunte a otros dos nodos :uno que le precede en la lista y otro que lo sigue. Los nodos apuntados pueden ser cualesquiera de la lista siempre que satisfagan esta regla básica : El nodo a la izquierda contiene un valor mas pequeño que el nodo que el nodo que le apunta y el nodo a la derecha contiene un valor mas grande.
Comohemos indicado cada árbol binario tiene un único primer elemento llamado la raíz del árbol. En la figura el nodo que contiene una A es el nodo raíz. El nodo raíz puede tener un nodo a su izquierda llamado hijo izquierdo y/o un nodo a su derecha llamado su hijo derecha. Por ejemplo el nodo que contiene J tiene un hijo izquierdo conteniendo una B y un hijo derecho conteniendo una D. El nodo quecontiene una A es llamado el padre de los nodos que contienen una B y D.Cualquier nodo en un árbol binario puede tener 0, 1 , 2 hijos. Un nodo sin hijos se llama hoja .Dos nodos son hermanos si tienen el mismo padre. Los nodos que contienen F y G son ambos hijos del nodo que contiene una C, por tanto son hermanos. Un nodo es un antecesor de ese nodo si es el padre de este, o el padre de algún otroantecesor de ese nodo.
El nivel de un nodo se refiere a su distancia al nodo raíz. Si designamos el nivel de la raíz como 0, los nodos que contienen B y D son nodos de Nivel 1 los nodos conteniendo F ,F , G, H , I ,J son nodos de Nivel 2.
Los campos izquierdo y Derecho que contienen punteros se usaran en los algoritmos para árbol, para enlazar los datos almacenados en el árbol. Estos camposno son accedidos directamente por el usuario del árbol. El campo Info que contiene los nodos que interesan al usuario pueden ser de cualquier tipo de datos.
Cada nodo de un árbol binario puede tener a lo sumo dos hijos; por tanto podemos representar una expresión binaria simple como un árbol binario de dos niveles. La raíz del nodo contiene el operador y los hijos contienen los operandos.Las distintas partes de una expresión complicada tienen diferentes niveles de precedencia de evaluación. Por ejemplo cuando vemos la expresión (A+B)*C sabemos que la expresión (A+B) se evalúa antes que la de multiplicación. Cuando escribimos la expresión infija con el operador entre losoperandos, dependemos de algún esquema de precedencia del operador y del uso de paréntesis para describir unaexpresión de forma precisa . Sin embargo cuándo usamos un árbol binario para representar una expresión, los paréntesis no son necesarios para indicar la precedencia.
Comencemos en el nodo raíz y evaluemos la expresión. La raíz contiene el operador, luego miramos sus hijos para obtener dos operandos como el nodo a la izquierda de la raíz contiene otro operador - sabemos que el subárbol izquierdo...
Leer documento completo
Regístrate para leer el documento completo.