TSU Informatica

ÁRBOL CON RAÍZ: Definición
Sea A un conjunto y T una relación en A. Se dice que T es un árbol si posee un vértice vo en A con la propiedad de que existe una única trayectoria de vo hacia cualquierotro vértice de A pero no existe una trayectoria de vo a vo.
Notación:
Se dice que T es un árbol con raíz y se denota (T, vo)
vo se denomina raíz del árbol T
Cualquier otro elemento de A es unvértice en T.
Observación: T se representa por su Dígrafo
Diseño De Un Árbol Con Raíz
Se ubica a la raíz vo , de la cual se dirá que está en el nivel 0.
Ninguna arista entra a vo pero puedensalir varias, que se trazan hacia abajo. Los vértices terminales de las aristas que comienzan en vo son los vértices del nivel 1
Cada vértice del nivel 1 no tienen otras aristas que entren en él, perocada uno de estos vértices pueden tener varias aristas que salen de él. Se trazan las aristas que salen del nivel 1 hacia abajo y terminan en vértices que estarán en el nivel 2
Y así sucesivamentecon cada nivel….
Ejemplo:

Otras definiciones
El nivel de un nodo está dado por el número de aristas que deben ser recorridos para llegar a él desde el vértice raíz.
La altura de un árbol es elnivel más grande del mismo.
Un vértice X se dice padre de otro vértice Y cuando existe una trayectoria de longitud 1 que sale de X y termina en Y, el que a su vez se dice hijo de X. Por ejemplo vose dice padre de todos los vértices del nivel 1
Los vértices hijos del mismo padre se dicen hermanos
Un vértice X se dice descendiente de otro Y cuando existe una trayectoria de cualquierlongitud que comienza en X y termina en Y. En ese caso se dice que Y es antecesor de X
Un vértice se dice hoja cuando no tiene hijos
Un árbol se dice ordenado cuando los hijos de cada vértice estánlinealmente ordenados de izquierda a derecha
Propiedades de los árboles
Teorema # 1
Sea (T, vo) un árbol con raíz. Entonces:
a) No existen ciclos en T.
b) vo es la única raíz en T.
c) Cada...