estructura de arbol
-
Upload
bliys -
Category
Technology
-
view
147 -
download
0
Transcript of estructura de arbol
![Page 1: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/1.jpg)
ESTRUCTURA DE DATOS
ARBOLES
![Page 2: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/2.jpg)
¿QUE ES ?
• UN ÁRBOL ES UN CONJUNTO, DE VÉRTICES Y ARCOS QUE SATISFACEN CIERTOS
REQUERIMIENTOS. UN VÉRTICE ES UN OBJETO SIMPLE (CONOCIDO TAMBIÉN COMO NODO)
QUE PUEDE TENER UN NOMBRE, ADEMÁS DE CIERTA INFORMACIÓN; UN ARCO ES LA UNIÓN
ENTRE DOS VÉRTICES.
![Page 3: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/3.jpg)
INTRODUCCIÓN
• LAS ESTRUCTURAS ARRAY Y LISTAS SON ESTRUCTURAS DE DATOS LINEALES.
A CADA ELEMENTO LE CORRESPONDÍA SIEMPRE UN SIGUIENTE ELEMENTO.
• LOS ARBOLES Y GRAFOS SON ESTRUCTURAS DE DATOS NO LINEALES PUESTO
QUE PUEDEN TENER DIFERENTES SIGUIENTES ELEMENTOS, Y TAMBIÉN SE
CONOCEN COMO ESTRUCTURAS MULTI - ENLAZADAS
![Page 4: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/4.jpg)
TERMINOLOGIAS
• UNA RUTA, EN UN ÁRBOL, ES UNA LISTA DE DIFERENTES VÉRTICES EN LA QUE
LOS VÉRTICES CONSECUTIVOS SE CONECTAN POR MEDIO DE ARCOS DENTRO
DEL ÁRBOL.
• EXISTE EXACTAMENTE UNA RUTA ENTRE LA RAÍZ Y UN NODO
![Page 5: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/5.jpg)
TERMINOLOGIAS
• CADA NODO EXCEPTO LA RAÍZ , TIENE EXACTAMENTE UN NODO ARRIBA DE EL
(PADRE) ASÍ, LOS NODOS QUE SE ENCUENTRAN DIRECTAMENTE ABAJO DE
ALGÚN NODO SE DENOMINA (HIJO)
![Page 6: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/6.jpg)
TERMINOLOGIAS
• NODO HIJO: CUALQUIERA DE LOS
NODOS APUNTADOS POR UNO DE
LOS NODOS DEL ÁRBOL. EN EL
EJEMPLO, 'L' Y 'M' SON HIJOS DE
'G'.
• NODO PADRE: NODO QUE
CONTIENE UN PUNTERO AL NODO
ACTUAL. EN EL EJEMPLO, EL NODO
'A' ES PADRE DE 'B', 'C' Y 'D'
![Page 7: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/7.jpg)
CARACTERÍSTICA
• CADA NODO SÓLO PUEDE SER APUNTADO POR OTRO NODO, ES DECIR, CADA NODO SÓLO TENDRÁ UN PADRE. ESTO HACE QUE ESTOS ÁRBOLES ESTÉN
FUERTEMENTE JERARQUIZADOS, Y ES LO QUE EN REALIDAD LES DA LA
APARIENCIA DE ÁRBOLES
• TODOS LOS NODOS CONTENGAN EL MISMO NÚMERO DE PUNTEROS, ES DECIR, USAREMOS LA MISMA ESTRUCTURA PARA TODOS LOS NODOS DEL ÁRBOL. ESTO HACE QUE LA ESTRUCTURA SEA MÁS SENCILLA, Y POR LO TANTO
TAMBIÉN LOS PROGRAMAS PARA TRABAJAR CON ELLOS.
![Page 8: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/8.jpg)
POSICIÓN DENTRO DEL ÁRBOL
• NODO RAÍZ: NODO QUE NO TIENE PADRE. ESTE ES EL NODO QUE USAREMOS
PARA REFERIRNOS AL ÁRBOL. EN EL EJEMPLO, ESE NODO ES EL 'A'.
• NODO HOJA: NODO QUE NO TIENE HIJOS. EN EL EJEMPLO HAY VARIOS: 'F',
'H', 'I', 'K', 'L', 'M', 'N' Y 'O'.
• NODO RAMA: SON LOS NODOS QUE NO PERTENECEN A NINGUNA DE LAS
DOS CATEGORÍAS ANTERIORES. EN EL EJEMPLO: 'B', 'C', 'D', 'E', 'G' Y 'J'.
![Page 9: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/9.jpg)
CARACTERÍSTICAS DEL ÁRBOL, EN RELACIÓN A SU
TAMAÑO:
SE REPRESENTA EN CUATRO CONCEPTOS :
• ORDEN
• GRADO
• NIVEL
• ALTURA
![Page 10: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/10.jpg)
ORDEN
• ES EL NÚMERO POTENCIAL DE HIJOS QUE PUEDE TENER CADA ELEMENTO DE
ÁRBOL. DE ESTE MODO, DIREMOS QUE UN ÁRBOL EN EL QUE CADA NODO
PUEDE APUNTAR A OTROS DOS ES DE ORDEN DOS, SI PUEDE APUNTAR A TRES
SERÁ DE ORDEN TRES, ETC.
![Page 11: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/11.jpg)
GRADO
• EL NÚMERO DE HIJOS QUE TIENE EL ELEMENTO CON MÁS HIJOS DENTRO DEL
ÁRBOL. EN EL ÁRBOL DEL EJEMPLO, EL GRADO ES TRES, YA QUE TANTO 'A'
COMO 'D' TIENEN TRES HIJOS, Y NO EXISTEN ELEMENTOS CON MÁS DE TRES
HIJOS.
![Page 12: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/12.jpg)
NIVEL
• SE DEFINE PARA CADA ELEMENTO DEL ÁRBOL COMO LA DISTANCIA A LA RAÍZ,
MEDIDA EN NODOS. EL NIVEL DE LA RAÍZ ES CERO Y EL DE SUS HIJOS UNO. ASÍ
SUCESIVAMENTE. EN EL EJEMPLO, EL NODO 'D' TIENE NIVEL 1, EL NODO 'G'
TIENE NIVEL 2, Y EL NODO 'N', NIVEL 3.
![Page 13: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/13.jpg)
ALTURA
• LA ALTURA DE UN ÁRBOL SE DEFINE COMO EL NIVEL DEL NODO DE MAYOR
NIVEL. COMO CADA NODO DE UN ÁRBOL PUEDE CONSIDERARSE A SU VEZ
COMO LA RAÍZ DE UN ÁRBOL, TAMBIÉN PODEMOS HABLAR DE ALTURA DE
RAMAS. EL ÁRBOL DEL EJEMPLO TIENE ALTURA 3, LA RAMA 'B' TIENE ALTURA 2,
LA RAMA 'G' TIENE ALTURA 1, LA 'H' CERO, ETC.
![Page 14: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/14.jpg)
EJEMPLO
• UN ÁRBOL BINARIO SENCILLO DE
TAMAÑO 9, 4 NIVELES Y ALTURA 3
(ALTURA = MÁXIMO NIVEL - 1),
CON UN NODO RAÍZ CUYO VALOR
ES 2.
![Page 15: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/15.jpg)
ÁRBOL BINARIO
• ES UNA ESTRUCTURA DE DATOS EN LA CUAL CADA NODO SIEMPRE TIENE UN
HIJO IZQUIERDO Y UN HIJO DERECHO. NO PUEDEN TENER MÁS DE DOS HIJOS
(DE AHÍ EL NOMBRE "BINARIO"). SI ALGÚN HIJO TIENE COMO REFERENCIA A
NULL, ES DECIR QUE NO ALMACENA NINGÚN DATO, ENTONCES ESTE ES
LLAMADO UN NODO EXTERNO.
![Page 16: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/16.jpg)
TIPOS DE ARBOLES BINARIOS
• UN ÁRBOL BINARIO LLENO ES UN ÁRBOL EN EL QUE CADA NODO TIENE CERO
O DOS HIJOS, ES DECIR SU FACTOR DE EQUILIBRIO ES 0
• UN ÁRBOL BINARIO PERFECTO ES UN ÁRBOL BINARIO LLENO EN EL QUE TODAS
LAS HOJAS (VÉRTICES CON CERO HIJOS) ESTÁN A LA MISMA PROFUNDIDAD
(DISTANCIA DESDE LA RAÍZ, TAMBIÉN LLAMADA ALTURA).
![Page 17: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/17.jpg)
RECORRIDOS SOBRE ÁRBOLES BINARIOS
• RECORRIDOS EN PROFUNDIDAD
• RECORRIDO EN PREORDEN
• RECORRIDO EN POSTORDEN
• RECORRIDO EN ENORDEN
• RECORRIDOS EN AMPLITUD (O POR NIVELES)
![Page 18: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/18.jpg)
RECORRIDOS EN PROFUNDIDAD
• EL MÉTODO DE ESTE RECORRIDO ES TRATAR DE ENCONTRAR DE LA CABECERA
A LA RAÍZ EN NODO DE UNIDAD BINARIA. AHORA PASAMOS A VER LA
IMPLEMENTACIÓN DE LOS DISTINTOS RECORRIDOS:
![Page 19: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/19.jpg)
RECORRIDO EN PREORDEN
• EN ESTE TIPO DE RECORRIDO SE REALIZA CIERTA ACCIÓN (QUIZÁS
SIMPLEMENTE IMPRIMIR POR PANTALLA EL VALOR DE LA CLAVE DE ESE NODO)
SOBRE EL NODO ACTUAL Y POSTERIORMENTE SE TRATA EL SUBÁRBOL
IZQUIERDO Y CUANDO SE HAYA CONCLUIDO, EL SUBÁRBOL DERECHO.
![Page 20: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/20.jpg)
RECORRIDO EN POSTORDEN
• EN ESTE CASO SE TRATA PRIMERO EL SUBÁRBOL IZQUIERDO, DESPUÉS EL
DERECHO Y POR ÚLTIMO EL NODO ACTUAL. OTRA FORMA PARA ENTENDER EL
RECORRIDO CON ESTE MÉTODO SERIA SEGUIR EL ORDEN: NODO IZQUIERDA,
NODO DERECHA, NODO RAÍZ. EN EL ÁRBOL DE LA FIGURA EL RECORRIDO EN
POSTORDEN SERÍA: 2, 5, 11, 6, 7, 4, 9, 5 Y 2.
![Page 21: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/21.jpg)
RECORRIDO EN ENORDEN
• EN ESTE CASO SE TRATA PRIMERO EL SUBÁRBOL IZQUIERDO, DESPUÉS EL NODO
ACTUAL Y POR ÚLTIMO EL SUBÁRBOL DERECHO.
![Page 22: estructura de arbol](https://reader034.fdocumento.com/reader034/viewer/2022050922/55a03b961a28ab6d218b4646/html5/thumbnails/22.jpg)
RECORRIDOS EN AMPLITUD O NIVELES
• EN ESTE CASO EL RECORRIDO SE REALIZA EN ORDEN POR LOS DISTINTOS
NIVELES DEL ÁRBOL. ASÍ, SE COMENZARÍA TRATANDO EL NIVEL 1, QUE SOLO
CONTIENE EL NODO RAÍZ, SEGUIDAMENTE EL NIVEL 2, EL 3 Y ASÍ
SUCESIVAMENTE.