Download - ÁRBOLES
![Page 1: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/1.jpg)
ÁRBOLES
Curso de Introducción a la Computación
![Page 2: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/2.jpg)
Árboles binariosUn árbol binario es un conjunto de elementos que o está vacío o está dividido en tres subconjuntos desarticulados.
El primer subconjunto tiene un solo elemento llamado raíz del árbol.
Los otros son en si mismos árboles binarios, llamados subárboles izquierdo y derecho del árbol original.
Raiz
Subárbol izquierdo
Subárbol derecho
![Page 3: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/3.jpg)
Representación y operaciones
Supondremos al árbol consistente en nodos con tres campos: info, left y right.
El campo info contiene la información útil, left es un apuntador a subárbol izquierdo y right es un apuntador al subárbol derecho.
Las operaciones básicas con árboles son: maketree, setleft y setright.
La función maketree(x) construye un árbol binario que consiste de un solo nodo con campo de información x y regresa el apuntador a dicho árbol.
![Page 4: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/4.jpg)
Algoritmo para construir un árbol binario
FUNCION MAKETREE(X: INFOTYPE) REGRESA NODOPTR
1. P GETNODE
2. INFO(P) X
3. LEFT(P) NIL
4. RIGHT(P) NIL
5 REGRESA P
![Page 5: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/5.jpg)
Rutinas SetLeft y SetRight
SUBRUTINA SETLEFT( P:NODEPTR, X:INFOTYPE)
1. SI LEFT(P) <> NIL ENTONCES
a. ERROR "YA EXISTE
EL SUBARBOL IZQUIERDO"
2. LEFT(P) MAKETREE(X)
SUBRUTINA SETRIGHT(P: NODEPTR, X:INFOTYPE)
1. SI RIGHT(P) <> NIL ENTONCES
a. ERROR "YA EXISTE EL
SUBARBOL DERECHO"
2. RIGHT(P) MAKETREE(X)
![Page 6: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/6.jpg)
Algoritmo para construir un árbol binario ordenado.
SUBRUTINA PLACE(P:NODEPTR,X:INFOTYPE)
1. SI P=NIL ENTONCES
a. P MAKETREE(X)
2. SINO
a. SI X<INFO(P) ENTONCES
1. PLACE(LEFT(P),X)
b. SI X>INFO(P) ENTONCES
1. PLACE(RIGHT(P),X)
c. SI X=INFO(P) ENTONCES
1. WRITE "ELEMENTO REPETIDO"
![Page 7: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/7.jpg)
Recorrido de árboles
Otra operación común es recorrer un árbol binario: esto es, pasar a través del árbol, enumerando cada uno de los nodos una vez. A esto se le llama visitar cada nodo. Existen al menos tres formas de recorrer un árbol:
•En preorden
•En entreorden
•En posorden
![Page 8: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/8.jpg)
Recorrido en preorden1. Visitar primero la raíz.
2. Visitar el subarbol izquierdo en preorden.
3. Visitar el subarbol derecho en preorden.
Algoritmo :
SUBRUTINA PRETRAV(TREE:NODEPTR)
1. SI TREE<>NIL ENTONCES
a. ESCRIBE INFO(TREE)
b. PRETRAV(LEFT(TREE))
c. PRETRAV(RIGHT(TREE))
![Page 9: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/9.jpg)
Recorrido en entreorden1. Visitar el subarbol izquierdo en entreorden.
2. Visitar primero la raíz.
3. Visitar el subarbol derecho en entreorden.
Algoritmo:
SUBRUTINA INTRAV(TREE:NODEPTR)
1. SI TREE<>NIL ENTONCES
a. INTRAV(LEFT(TREE))
b. ESCRIBE INFO(TREE)
c. INTRAV(RIGHT(TREE))
![Page 10: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/10.jpg)
Recorrido en posorden
1. Visitar el subarbol izquierdo en posorden.
2. Visitar el subarbol derecho en posorden.
3. Visitar primero la raíz.
Algoritmo:
SUBRUTINA POSTTRAV(TREE:NODEPTR)
1. SI TREE<>NIL ENTONCES
a. POSTTRAV(LEFT(TREE))
b. POSTTRAV(RIGHT(TREE))
c. ESCRIBE INFO(TREE)
![Page 11: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/11.jpg)
Algunas definiciones
Árbol estrictamente binario – todos los nodos que no son hojas tienen subárbol izquierdo y derecho no vacíos.
Profundidad – es el máximo nivel de cualquier hoja del árbol.
Árbol binario completo – todos las hojas están en el último nivel.
Árbol binario cuasi-completo – para un árbol de d niveles todos las hojas están en los niveles d o d–1 y para todo nodo nd con un descendiente derecho en el nivel d, todos los descendientes izquierdos de nd que sean hojas también estrán en el nivel d.
![Page 12: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/12.jpg)
a
b c
d
g
e
f
a
b c
d ge f
h i j k
a
b c
d ge f
h i
a
b c
d ge f
h i h
![Page 13: ÁRBOLES](https://reader031.vdocumento.com/reader031/viewer/2022020200/56813de4550346895da7bb29/html5/thumbnails/13.jpg)
Diversas representaciones de árbolesg
d h
a
c
m
l q
Mediante paréntesis
(g(d(a.(c..)).)(h.(m(l..)(q(n..).))))
n
Mediante niveles a c dg h l m n q