Diferencias

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

--- algoritmos-oia:grafos:arboles [2017/12/08 21:25]
sebach
+++ algoritmos-oia:grafos:arboles [2018/01/05 18:52]
santo
@@ Línea 20: / Línea 20: @@
-Algo interesante que podemos hacer en todos los árboles es establecer un nodo **raíz**. Si establecemos un nodo como raíz, por ejemplo si setemos la raíz como el nodo $1$ ó $2$ en el árbol de recién, convendría (y se suele) dibujarlos así respectivamente:
+Algo interesante que podemos hacer en todos los árboles es establecer un nodo **raíz**. Si establecemos un nodo como raíz, por ejemplo si elegimos como raíz al nodo $1$ ó $2$ en el árbol de recién, convendría (y se suele) dibujarlos así respectivamente:
 {{:algoritmos-oia:graph_1_.png?300 |}} {{:algoritmos-oia:graph_2_.png?300 |}}
+Es decir, se ubica la raíz arriba de todo, y luego los nodos se dibujan más abajo, en la medida en que están más lejos de la raíz.
 \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\
@@ Línea 30: / Línea 31: @@
 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 =====

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página