6 1 Arboles 6 1 1 Componentes y Propiedades pptx - Lupiwi Chan

Vista previa del material en texto

6.1 Arboles.
6.1.1 Componentes y 
propiedades
Un árbol es una estructura no lineal de datos 
ampliamente usada que imita la forma de un 
conjunto de nodos conectados
no dirigido conexo que no contiene circuito
Ejemplo: 
En el árbol i)
b, c, d, f, g, i, son nodos hoja 
a, e, h, son nodos rama.
Existen algunas propiedades que señalaremos con relación a los árboles.
1) Existen un único paseo entre dos vértices cuales quiera en un 
árbol.
2) El número de vértices es mayor que el número de aristas en un 
árbol.
3) Un árbol con dos o más vértices tiene al menos una hoja.
Existen además otros resultados sobre la caracterización de 
árboles.
1) Un grafo en el cual existe un único paseo entre cada par de 
vértices es un árbol.
2) Un grafo conexo con e = v - 1 es un árbol.
3) Un grafo con e = v - 1 que no tiene circuitos es un árbol.
Componentes (raíz, hoja, padre, 
hijo, descendientes, 
ancestros)Altura: Es el máximo número de niveles de todos los nodos del 
árbol. Equivale al nivel más alto de los nodos más 1.
Ancestros: los padres y los abuelos de un nodo hijo. 
Descendientes: Hijos de los hijos.
Grado del Árbol: Es el máximo grado de todos los nodos del árbol.
Hermano: Dos nodos serán hermanos si son descendientes 
directos de un mismo nodo.
Nivel: Es el número de arcos que deben ser recorridos para 
llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
Nodo Hermano: Dos nodos serán hermanos si son 
descendientes directos de un mismo nodo.
Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal 
a aquellos nodos que no tienen ramificaciones (hijos).
Nodo Interior: Es un nodo que no es raíz ni hoja.
Nodo Raíz: Es el único nodo del árbol que no tiene padre es decir 
no es hijo de ningún elemento. Este es el nodo que usaremos 
para referirnos al árbol.
Nodo: Son los Vértices o elementos del Árbol.
Orden: Es el número potencial de hijos que puede tener cada 
elemento de árbol.
Peso: Es el número de nodos del árbol sin contar la raíz 
Rama: Es el camino desde el nodo raíz a una hoja.
Propiedades 
ArbolesTodo árbol que no es vacío, tiene un único nodo raíz.
Un nodo X es descendiente directo de un nodo Y, si el nodo X es 
apuntado por el nodo Y. en este caso es común utilizar la 
expresión X es hijo de Y.
Un nodo X es antecesor directo de un nodo Y, si el nodo X 
apunta al nodo Y. en este caso es común utilizar la expresión X 
es padre de Y.
Se dice que todos los nodos que son descendientes directos 
(hijos) de un mismo nodo (padre), son hermanos.
Todo nodo que no tiene ramificaciones (hijos), se conoce con 
el nombre de terminal u hoja.
Todo nodo que no es raíz, ni terminal u hoja se conoce con el 
nombre de interior.
Grado es el número de descendientes directos de un 
determinado nodo. Grado del árbol es el máximo grado de todos 
los nodos del árbol, es decir, el grado más alto entre todos los 
nodos.
Nivel es el número de arcos que deben ser recorridos para llegar 
a un determinado nodo. Por definición la raíz tiene nivel 1.
Altura del árbol es el máximo número de niveles de todos los 
nodos del árbol.
A continuación se presenta un ejemplo 
para clarificar estos conceptos:
1.-8 es la raíz del árbol.
2.- 3 es hijo de 8.
10 es hijo de 8.
1 es hijo de 3. 
14 es hijo de 10. 
13 es hijo de 14.
3.- 8 es padre de 3.
3 es padre de 6.
6 es padre de 7.
10es padre de 14.
14 es padre de 13.
8.-
4.- 3 y 10 son hermanos.
1 y 6 son hermanos.
4 y 7 son hermanos.
5.- 1, 4, 7, 13 son nodos terminales u hojas.
6.- 6, 14, 10,3 son nodos interiores.
7.- El grado del nodo 8 es 2.
El grado del nodo 3 es 
2. El grado del nodo 6
es 2. El grado del nodo 14 
es 1. El grado del nodo 1
es 0. El grado del árbol es 
3.El nivel del nodo 8 es 1.
El nivel del nodo 3 es 2. El 
nivel del nodo 6 es 3. El 
nivel del nodo 10 es 2.
El nivel del nodo 13 es 4.