6 2 Árbol con Peso_6 2 1 Recorrido de un Árbol - Lupiwi Chan

Vista previa del material en texto

6. 2.ARBOLES DE PESO.
6. 2.1. RECORRIDO DE 
UN ARBOL 
6.2 ÁRBOLES CON PESO
• El peso de un árbol en un nodo dado es el 
número de nodos en el árbol sin contarse 
el mismo. 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 el peso de la raíz.
• Un árbol con peso es un grafo donde cada 
lado tiene un número asociado o peso.
• Normalmente, al peso de un lado se le 
designa por w(e). 
• La suma de todos los pesos de todos los 
lados de un grafo con peso se llama el peso 
del grafo
EJEMPLO
• Peso total del grafo = 19
• Hay diferentes formas de saber 
el peso de un árbol las cuales 
están las siguientes: el peso está 
dado por el número de nodo 
dado en el árbol sin contarse el 
mismo, también es la longitud 
del camino más largo del nodo a 
una hoja, el peso de la raíz, o el 
peso de un árbol es un grafo 
donde cada lado tiene un 
número asociado o peso.
• Un arbol con peso es un grafo 
donde cada lado tienen un 
numero asociado o peso. 
Normalmente al peso de un lado 
se le designa por w(e) . La suma 
de todos los ´pesos de todo los 
lados de un gafo con peso de 
llama el peso de un grafo
• Dado un grafo conexo, un árbol recubierto mínimo de 
ese grafo es un subgrafo que tiene que ser un árbol y 
contener todos los vértices del grafo inicial. Cada 
arista tiene asignado un peso proporcional entre ellos, 
que es un número representativo de algún objeto, 
distancia, etc... , y se usa para asignar un peso total al 
árbol recubierto mínimo computando la suma de 
todos los pesos de las aristas del árbol en cuestión. Un 
árbol recubridor mínimo o un árbol expandido 
mínimo es un árbol recubridor que pesa menos o 
igual que otros árboles recubridores.
• Todo grafo tiene un bosque recubridor mínimo. En el 
caso de un empate, porque podría haber más de un 
árbol recubridor mínimo; en particular, si todos los 
pesos son iguales, todo árbol recubridor será mínimo. 
De todas formas, si cada arista tiene un peso distinto 
existirá sólo un árbol recubridor mínimo
6.2.1 recorrido de un árbol
• El recorrido del árbol se refiere al proceso de 
la visita (el examen y / o actualización) de 
cada nodo de una estructura de datos de 
árbol , tal vez, de una manera sistemática. 
Estos recorridos están clasificados por el 
orden en el que se visitan los nodos
• En la ciencia de la computación, el recorrido 
de arboles se refiere al proceso de visitar de 
una manera sistemática, exactamente una 
vez cada nodo en una estructura de datos de 
árbol( exactamente y/o actualizado los datos 
en los nodos). Tales recorridos están 
clasificados por el orden en el cual son 
visitados los nodos 
Pre orden: (raíz, izquierdo, derecho).
• Para recorrer un árbol binario no vacío en 
preorden, hay que realizar las siguientes 
operaciones recursivamente en cada nodo, 
comenzando con el nodo de raíz:
• 1. Visite la raíz
• 2. Atraviese el sub-árbol izquierdo
• 3. Atraviese el sub-árbol derecho
• Inorden: (izquierdo, raíz, 
derecho).
• Para recorrer un árbol binario no 
vacío en inorden (simétrico), hay 
que realizar las siguientes 
operaciones recursivamente en 
cada nodo:
• 1. Atraviese el sub-árbol izquierdo
• 2. Visite la raíz
• 3. Atraviese el sub-árbol derecho
• Postorden: (izquierdo, derecho, 
raíz).
• Para recorrer un árbol binario no vacío 
en postorden, hay que realizar las 
siguientes operaciones recursivamente 
en cada nodo:
• 1. Atraviese el sub-árbol izquierdo
• 2. Atraviese el sub-árbol derecho
• 3. Visite la raíz
• recorre la raíz. En los tres, se recorre primero 
el sub-árbol izquierdo y luego el derecho En 
general, la diferencia entre pre orden, 
inorden y postorden es cuándo se.
• 
• • En pre orden, la raíz se recorre antes que 
los recorridos de los subárboles izquierdo y 
derecho
• • En inorden, la raíz se recorre entre los 
recorridos de los árboles izquierdo y 
derecho, y
• • En postorden, la raíz se recorre después de 
los recorridos por el subárbol izquierdo y el 
derecho