Soluciones Práctica de Árboles PDF

Preview

Summary

ESTRUCTURAS DE DATOS TIPOÁRBOLSOLUCIÓN A LOS PROBLEMAS DELCAPÍTULOLicda. Gabriela C. de Hislop2. Dada la siguiente estructura de árbol representada mcalcule las longitudes de camino interno y externo de ese árbol anidación de paréntesis,(A (B (D, E(I, J), F, G(K(M, N))), C(H(l)))Solución:3. Calcule ...

Description

ESTRUCTURAS DE DATOS TIPO ÁRBOL SOLUCIÓN A LOS PROBLEMAS DEL CAPÍTULO

Licda. Gabriela C. de Hislop

Árboles en General 1. Los árboles se pueden representar de diferentes formas. Dada la siguiente estructura de árbol representada como anidación de paréntesis: (A(B(E(K), F), C(G(L, M(N))), D(H, I(O,P,Q,R), J))) Calcule lo siguiente:     

Grado del árbol Grado del nodo G Altura del árbol Nodos terminales u hojas Nodos interiores

Solución:

Grado del árbol: 4 Grado del nodo G: 2 Altura del árbol:5 Nodos terminales: K, F, L, N, H, O, P, Q, R, J Nodos intermedios: B, C, D, E, G, I, M

2. Dada la siguiente estructura de árbol representada mediante anidación de paréntesis, calcule las longitudes de camino interno y externo de ese árbol. (A (B (D, E(I, J), F, G(K(M, N))), C(H(l))) Solución:

3. Calcule cuál es el grado de nodo T, si T es padre del nodo P y éste tiene 4 hermanos. Solución: Grado de T = 5

Árboles Binarios 4. Dados los siguientes árboles binarios representados como anidación de paréntesis:  (K(B(A, F(D, )),W(M(L, O( ,P)), Z)))  (25(20(10(8, )),23(21, )), 90(80(62(47(32, ), ), ),100)) Escriba los recorridos preorden, inorden y postorden de cada uno de ellos.

Solución:

Preorden o prefijo: K, B, A, F, D, W, M, L, O, P, Z Postorden o postfijo: A, D, F, B, L, P, O, M, Z, W, K Inorden, sufijo o infijo: A, B, D, F, K, L, M, O, P, W, Z

5. Considérese el árbol siguiente:  ¿Cuál es su altura?  ¿Está el árbol equilibrado? ¿Por qué?  Listar todos los nodos hoja.  ¿Cuál es el predecesor inmediato (padre) del nodo U?  Listar los hijos del nodo R.  Listar los sucesores del nodo R.

Solución: a) Altura del árbol = 4 b) ¿Está equilibrado? Si ¿Por qué? Porque para cada nodo se cumple que la altura de sus árboles izquierdo y derecho, difieren a lo más en una unidad. c) Nodos hoja = W, T, X, V d) Padre de U = R e) Hijos de R = U, V f) Sucesores de R = U, V, X

6. Explicar por qué cada una de las siguientes estructuras no es un árbol binario: .

Solución: a)

El nodo B excede en una unidad el número máximo de nodos permitidos para un carbol binario.

b)

El nodo D tiene dos padres, lo cual es contrario a lo establecido.

c)

El mismo caso que en (b), el nodo F tiene dos padres.

7. ¿Cuál es el máximo número de nodos de un árbol binario de altura h? Solución: 2h – 1. Así, un árbol lleno, de altura 5, por ejemplo, tiene 31 nodos.

8. ¿Cuál es el máximo número de nodos en el nivel 8 de un árbol binario lleno? ¿y en el nivel 14? Solución: El número máximo de nodos en el nivel n de un árbol se determina mediante la fórmula 2n-1. En el primer caso, entonces, siendo n=8, el número de nodos será 28-1= 27 = 128 y en el segundo caso, 214-1=213=8,192.

9. ¿Cuántos árboles binarios distintos se puede tener con 4 nodos? Solución:

10.Dadas las siguientes secuencias de nodos obtenidas por los recorridos preorden, inorden y postorden, dibuje el correspondiente árbol binario.  Preorden: P-R-A-C-H-T-O-M  Inorden: A-R-H-C-P-O-T-M  Postorden: A-H-C-R-O-M-T-P Solución:

11. El recorrido preorden de un cierto árbol binario produce AD F G H K LPQ R WZ y el recorrido enorden produce G F H K D LA W R Q P Z Dibujar el árbol binario.

Representación de Árboles Generales como Árboles Binarios 12.Dados los siguientes árboles generales, uno representado en forma de grafo, inciso (a), y otro representado como anidación de paréntesis, inciso (b), conviértalos a árboles binarios. a)

b) (A(B(E,F(K)),C(G(L,M(Q,R),N)),D(H,I(O(S),P)))) D

Solución: (a)

A .

B

U

D

C B A

U

T

H H B

C

T

R

R

O H H

O

P

Q

S

P

Q

S

A (b) C

B

K H

L

A

E B

M

Q

F

I

O

N

P

S

R

D

C

B

H

G

F

E

D

G

H

I A

K H

L

M

N

O

P

Q

R

S

E B

B

C

G

F

K H

D

H

L

M

Q

I

N

R

O

S

P

13.Dado el siguiente bosque, conviértalo en árbol binario.

Solución:

Paso 1.

H

Paso 2. Giro 45

I

Q

L

J

M

R

K

A

S

B C

T

N

O

W

U

D E

V

G

Y

Z

F...