Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:arboles [2017/12/08 13:22]
sebach creado
+++ algoritmos-oia:grafos:arboles [2017/12/26 19:13]
sebach ↷ Page moved from algoritmos-oia:arboles to algoritmos-oia:grafos:arboles
@@ Línea 30: / Línea 30: @@
 Para un árbol con raíz, tienen sentido las siguiente definiciones:
-Altura o Profundidad de un nodo: Es la longitud del camino entre el nodo y la raíz. En el árbol de raíz $1$, las alturas de los nodos $1$, $5$,  $3$ son $0$, $1$, $2$ respectivamente.
+**Altura o Profundidad de un nodo**: Es la longitud del camino entre el nodo y la raíz. En el árbol de raíz $1$, las alturas de los nodos $1$, $5$,  $3$ son $0$, $1$, $2$ respectivamente.
-Hojas: Son los nodos desde los cuales es imposible ir a otro nodo más alejado de la raíz sin "subir" (acercarnos a la raíz). En el árbol de raíz $1$, las hojas son los nodos $3$, $4$ y $6$.
+**Hojas**: Son los nodos desde los cuales es imposible ir a otro nodo más alejado de la raíz sin "subir" (acercarnos a la raíz). En el árbol de raíz $1$, las hojas son los nodos $3$, $4$ y $6$.
-Padre de un nodo: Es el nodo que está inmediatamente arriba de él, es decir que es adyacente al nodo, y está en el camino entre el nodo y la raíz. La raíz no tiene padre. En el árbol de raíz $1$, el padre de $6$ es $5$ y el de $5$ es $1$.
+**Padre de un nodo**: Es el nodo que está inmediatamente arriba de él, es decir que es adyacente al nodo, y está en el camino entre el nodo y la raíz. La raíz no tiene padre. En el árbol de raíz $1$, el padre de $6$ es $5$ y el de $5$ es $1$.
-Hijos de un nodo: Son los nodos adyacentes a él que tienen altura mayor a él. Las hojas no tienen hijos. En el árbol de raíz $1$, el único de $2$ es $3$, y los hijos de $1$ son $2$, $5$ y $4$.
+**Hijos de un nodo**: Son los nodos adyacentes a él que tienen altura mayor a él. Las hojas no tienen hijos. En el árbol de raíz $1$, el único de $2$ es $3$, y los hijos de $1$ son $2$, $5$ y $4$.
-Subárbol dado por un nodo: Es el árbol que queda formado por el nodo dado, sus hijos, los hijos de sus hijos, y así hasta llegar a las hojas. La raíz del subárbol es el nodo dado. El subárbol de una hoja es simplemente ese mismo nodo. En el árbol de raíz $1$, el subárbol del nodo $5$ son sólo los nodos $5$ y $6$ con la arista que los une.
+**Subárbol de un nodo dado**: Es el árbol que queda formado por el nodo dado, sus hijos, los hijos de sus hijos, y así hasta llegar a las hojas. La raíz del subárbol es el nodo dado. El subárbol de una hoja es simplemente ese mismo nodo. En el árbol de raíz $1$, el subárbol del nodo $5$ son sólo los nodos $5$ y $6$ con la arista que los une.
+**Ancestro común de nodos**: Es un nodo que contiene a todos los nodos dados en su subárbol. La raíz es un ancestro común de todos los nodos. En general es interesante conocer el **ancestro común más bajo** de dos nodos, que es simplemente el ancenstro común "más bajo", o sea de mayor altura, de todos los ancestros de los nodos dados.
+===== Cómo recorrer árboles =====
+Bueno, una manera de recorrerlo es simplemente con BFS o DFS, marcando los visitados y todo igual a como hacíamos antes, ya que eso funciona para cualquier grafo.
+Otra manera de recorrerlo es desde la raíz hacia abajo, con una función [[algoritmos-oia:recursion|recursiva]] que se mueva a todos los vecinos del nodo excepto a su padre, que será un parámetro de la función.
+Entonces el código quedaría:
+<code cpp>
+void recorrer(int nodo, int padre){
+    for(int i=0; i<grafo[nodo].size(); i++){
+        if(grafo[nodo][i]!=padre){
+            // Codigo aca o despues de llamar a la funcion, que haga algo
+            recorrer(grafo[nodo][i], nodo); // Ahora el padre del nodo al que vamos es el nodo actual
+        }
+    }
+}
+// Para empezar en la raíz sin que se evite ningún nodo, es común hacer:
+recorrer(raiz, -1);
+</code>

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página