Arboles Binarios
Páginas: 8 (1759 palabras)
Publicado: 5 de mayo de 2013
Árboles
1
Definición
2
Un árbol dirigido es una estructura:
Jerárquica porque los componentes están a distinto nivel.
Organizada porque importa la forma en que esté
dispuesto el contenido.
Dinámica porque su forma, tamaño y contenido pueden
variar durante la ejecución.
Un árbol puede ser:
vacío,
Una raíz + subárboles.
Representación de unÁrbol. diagramas de Venn
Mediante
3
a
b
c
d
e
f
a
Mediante círculos y flechas
b
Mediante paréntesis anidados:
( a ( b (e,f), c, d ) )
e
c
f
d
Conceptos Básicos
Si hay un camino de A hasta B, se dice que A
es antecesor de B, y que B es sucesor de A.
Padre es el antecesor inmediato de un nodo
Hijo, cualquiera de susdesc}ientes
inmediatos.
Descendiente de un nodo, es cualquier
sucesor de dicho nodo.
Hermano de un nodo, es otro nodo con el
mismo padre.
Generación, es un conjunto de nodos con la
misma profundidad.
4
Conceptos Básicos (cont.)
5
Raíz es el nodo que no tiene ningún predecesor
(sin padre).
Hoja es el nodo que no tiene sucesores (sin hijos)(Terminal). Los que tienen predecesor y sucesor
se llaman nodos interiores.
Rama es cualquier camino del árbol.
Bosque es un conjunto de árboles
desconectados.
Nivel o profundidad de un nodo, es la longitud
del camino desde la raíz hasta ese nodo.
El nivel puede de}irse como 0 para la raíz y nivel
(predecesor)+1 para los demás nodos.
Conceptos Básicos (cont.)
Los nodos de la mismageneración tienen el
mismo nivel.
Grado de un nodo, es el número de flechas que
salen de ese nodo (hijos). El número de las que
entran siempre es uno.
Grado de un árbol, es el mayor grado que puede
hallarse en sus nodos.
Longitud del camino entre 2 nodos: es el número
de arcos que hay entre ellos.
6
Conceptos Básicos (cont.)
7
Raíz
hijo
Padre
Hermanohoja
Subárbol
Nivel de profundidad = 7
Grado de un nodo = 3
Grado del árbol = 3
Tipos de árboles
8
Un árbol ordenado: Es aquel en el que las ramas de
los nodos están ordenadas.
Los de grado 2 se llaman árboles binarios.
Cada árbol binario tiene un subárbol izquierda y
subárbol derecha.
+
A
^
B
3.5
/
C
D
Tipos de árboles (cont.)
9Árboles de expresión
Representan un orden de ejecución
*
+
+
*
A
+
B
E
*
C
(A* B) + C * D + E
-
D
7
12
9
(7 + 12) * (-9) -171
Tipos de árboles (cont.)
10
Árboles similares: Los que tienen la misma
estructura (forma)
a
1
2
3
6
4
8
b
5
7
9
c
e
d
f
h
g
i
Árboles Equivalentes: Son los árbolessimilares y
sus nodos contienen la misma información.
Árboles n-ario: Es un árbol ordenado cuyos
nodos tiene N subárboles, y donde cualquier
número de subárboles puede ser árboles vacíos
Tipos de árboles (cont.)
11
Árbol binario completo:
Es un árbol en el que todos sus nodos, excepto los del ultimo
nivel, tienen dos hijos.
Número de nodos en un árbol binario completo= 2 –1 (en
el ejemplo h = 4, 15) esto nos ayuda a calcular el nivel de
árbol necesario para almacenar los datos de una
aplicación.
h
Árboles Binarios
de Búsqueda
(ABB)
UDEM OT 2005
12
Árboles Binarios de
Búsqueda
Un árbol es un ABB si
éste es binario y sus
nodos son subárboles
de búsqueda binarios y
contienen información
ordenada de tal que
todos los elementos ala
izquierda de la raíz son
menores a la raíz y
todos lo elementos a la
derecha de la raíz son
mayores a la raíz.
13
Características de un ABB
14
Todos los nodos a la izquierda son menores al padre.
Todos los nodos a la derecha son mayores al padre.
Y solo pueden tener 2 hijos a lo mucho.
50
90
40
26
8
45
34
42
110
85
68
88...
1
Definición
2
Un árbol dirigido es una estructura:
Jerárquica porque los componentes están a distinto nivel.
Organizada porque importa la forma en que esté
dispuesto el contenido.
Dinámica porque su forma, tamaño y contenido pueden
variar durante la ejecución.
Un árbol puede ser:
vacío,
Una raíz + subárboles.
Representación de unÁrbol. diagramas de Venn
Mediante
3
a
b
c
d
e
f
a
Mediante círculos y flechas
b
Mediante paréntesis anidados:
( a ( b (e,f), c, d ) )
e
c
f
d
Conceptos Básicos
Si hay un camino de A hasta B, se dice que A
es antecesor de B, y que B es sucesor de A.
Padre es el antecesor inmediato de un nodo
Hijo, cualquiera de susdesc}ientes
inmediatos.
Descendiente de un nodo, es cualquier
sucesor de dicho nodo.
Hermano de un nodo, es otro nodo con el
mismo padre.
Generación, es un conjunto de nodos con la
misma profundidad.
4
Conceptos Básicos (cont.)
5
Raíz es el nodo que no tiene ningún predecesor
(sin padre).
Hoja es el nodo que no tiene sucesores (sin hijos)(Terminal). Los que tienen predecesor y sucesor
se llaman nodos interiores.
Rama es cualquier camino del árbol.
Bosque es un conjunto de árboles
desconectados.
Nivel o profundidad de un nodo, es la longitud
del camino desde la raíz hasta ese nodo.
El nivel puede de}irse como 0 para la raíz y nivel
(predecesor)+1 para los demás nodos.
Conceptos Básicos (cont.)
Los nodos de la mismageneración tienen el
mismo nivel.
Grado de un nodo, es el número de flechas que
salen de ese nodo (hijos). El número de las que
entran siempre es uno.
Grado de un árbol, es el mayor grado que puede
hallarse en sus nodos.
Longitud del camino entre 2 nodos: es el número
de arcos que hay entre ellos.
6
Conceptos Básicos (cont.)
7
Raíz
hijo
Padre
Hermanohoja
Subárbol
Nivel de profundidad = 7
Grado de un nodo = 3
Grado del árbol = 3
Tipos de árboles
8
Un árbol ordenado: Es aquel en el que las ramas de
los nodos están ordenadas.
Los de grado 2 se llaman árboles binarios.
Cada árbol binario tiene un subárbol izquierda y
subárbol derecha.
+
A
^
B
3.5
/
C
D
Tipos de árboles (cont.)
9Árboles de expresión
Representan un orden de ejecución
*
+
+
*
A
+
B
E
*
C
(A* B) + C * D + E
-
D
7
12
9
(7 + 12) * (-9) -171
Tipos de árboles (cont.)
10
Árboles similares: Los que tienen la misma
estructura (forma)
a
1
2
3
6
4
8
b
5
7
9
c
e
d
f
h
g
i
Árboles Equivalentes: Son los árbolessimilares y
sus nodos contienen la misma información.
Árboles n-ario: Es un árbol ordenado cuyos
nodos tiene N subárboles, y donde cualquier
número de subárboles puede ser árboles vacíos
Tipos de árboles (cont.)
11
Árbol binario completo:
Es un árbol en el que todos sus nodos, excepto los del ultimo
nivel, tienen dos hijos.
Número de nodos en un árbol binario completo= 2 –1 (en
el ejemplo h = 4, 15) esto nos ayuda a calcular el nivel de
árbol necesario para almacenar los datos de una
aplicación.
h
Árboles Binarios
de Búsqueda
(ABB)
UDEM OT 2005
12
Árboles Binarios de
Búsqueda
Un árbol es un ABB si
éste es binario y sus
nodos son subárboles
de búsqueda binarios y
contienen información
ordenada de tal que
todos los elementos ala
izquierda de la raíz son
menores a la raíz y
todos lo elementos a la
derecha de la raíz son
mayores a la raíz.
13
Características de un ABB
14
Todos los nodos a la izquierda son menores al padre.
Todos los nodos a la derecha son mayores al padre.
Y solo pueden tener 2 hijos a lo mucho.
50
90
40
26
8
45
34
42
110
85
68
88...
Leer documento completo
Regístrate para leer el documento completo.