Herramientas de usuario
algoritmos-oia:grafos:arboles
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa | |||
|
algoritmos-oia:grafos:arboles [2018/01/05 18:52] santo |
algoritmos-oia:grafos:arboles [2018/01/05 18:58] (actual) santo [Árboles] |
||
|---|---|---|---|
| Línea 31: | Línea 31: | ||
| Para un árbol con raíz, tienen sentido las siguiente definiciones: | 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 profundidades 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$. | ||
| Línea 39: | Línea 39: | ||
| **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 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. | + | **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í siguiendo hasta considerar todos los nodos posibles. 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. | + | **Desdenciente** de un nodo $x$: es un nodo $y$ que forma parte del subárbol de $x$. A veces se suele considerar a un nodo descendiente de sí mismo. |
| + | |||
| + | **Ancestro** de un nodo $x$: es un nodo $y$ tal que $x$ es descendiente de $y$. A veces se suele considerar a un nodo ancestro de sí mismo. | ||
| + | |||
| + | **Ancestro común de un conjunto de nodos**: Es un nodo que es ancestro de todos los nodos dados. Es decir, todos los nodos del conjunto forman parte del subárbol del nodo que llamamos ancestro común. La raíz es siempre un ancestro común de cualquier conjunto de nodos. En general es interesante conocer el **ancestro común más bajo** de dos nodos, que se obtiene tomando, de todos los ancestros comunes, aquel que sea el "más bajo", o sea el que está a mayor profundidad. | ||
| ===== Cómo recorrer árboles ===== | ===== Cómo recorrer árboles ===== | ||
algoritmos-oia/grafos/arboles.1515178350.txt.gz · Última modificación: 2018/01/05 18:52 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
