En los ejercicios 6 al 10, represente la expresión como un árbol binario y escriba sus formas de prefijo y posfijo.
6. (A * B ) * (C - D)
7. ((A−C)∗ D) /(A+(B+ D))
8. (A∗ B +C ∗ D)−(A/B −(D+ E))
9. (((A+ B)∗C + D)∗ E)−((A+ B)∗C − D)
10. (A∗ B −C/D+ E)+(A− B−C − D∗ D)/(A+ B +C)
En los ejercicios 11 al 15, represente la expresión en posfijo como un árbol binario y escriba la forma de prefijo, la forma usual de entrefijo y la forma de entrefijo con paréntesis completos de la expresión.
11. AB + C-
12. ABC +-
13. ABCD +* /E-
14. ABC**CDE+/-
15. AB+CD*EF/--A*
16. ABC+-
17. AB+C-
18. AB+CD*AA/--B*
19. ABC**ABC++-
20. ABAB*+*D*
21. ADBCD*-+*
22. Demuestre, por ejemplo, que los árboles binarios distintos con vértices A, B y C pueden tener la misma lista de preorden A B C .
23. Demuestre que hay un árbol binario único con seis vértices cuya lista de vértices de preorden es A B C E F D y cuya lista de vértices de entreorden es A C F E B D.
24. Escriba un algoritmo que reconstruya el árbol binario dados sus ordenamientos de preorden e entreorden.
25. Dé ejemplos de árboles binarios diferentes, B1 y B2, cada uno con dos vértices, donde la lista de vértices de preorden de B1 es igual a la lista de preorden de B2 y la lista de vértices de postorden de B1 es igual a la lista de postorden de B2.
26. Sean P1 y P2 permutaciones de A B C D E F. ¿Existe un árbol binario con vértices A, B, C, D, E y F cuya lista de preorden sea P1 y cuya lista de entreorden sea P2? Explique.
27. Escriba un algoritmo recursivo que imprima el contenido de los vértices terminales de un árbol binario de izquierda a derecha.
28. Escriba un algoritmo recursivo que intercambie todos los hijos izquierdos y derechos de un árbol binario.
29. Escriba un algoritmo recursivo que inicialice cada vértice de un árbol binario con el número de sus descendientes.
En los ejercicios 30 y 31, toda expresión implica sólo los operandos A, B, . . . , Z y las operaciones +, −, *, /.
30. Dé una condición necesaria y suficiente para que una cadena de símbolos sea una expresión en posfijo válida.
31. Escriba un algoritmo que, dada la representación por árbol binario de una expresión, produzca la forma de entrefijo con paréntesis completos de la expresión.
32. Escriba un algoritmo que imprima los caracteres y sus códigos dado un árbol de codificación de Huffman (vea el ejemplo 9.1.8). Suponga ga que cada vértice terminal almacena un carácter y su frecuencia.
Sea G = (V, E) un gráfica no dirigida simple. Una cubierta de los vértices de G es un subconjunto V de V tal que para cada arista (v, w) ∈E, ya sea v∈V o w∈V . El tamaño de la cubierta de vértices V es el número de vértices en V . Una cubierta de vértices óptima es una cubierta de vértices de tamaño mínimo. Un conjunto ajeno de aristas para G es un subconjunto E de E tal que para cada par de aristas distintas e1=(v1, w1)y e=(v2, w2) en E , se tiene
{v1, w1}∩{v2, w2}=∅
33. Pruebe que para cada n, existe una gráfica conexa con n vértices que tiene una cubierta de vértices de tamaño 1.
34. Demuestre que el tamaño de una cubierta de vértices óptima de la gráfica completa con n vértices es n−1.
35. El tamaño de una cubierta de vértices óptima de una gráfica con n vértices, ¿puede ser igual a n? Explique su respuesta.
36. Escriba un algoritmo que encuentre una cubierta de vértices óptima de un árbol T=(V, E) cuyo tiempo en el peor caso es (|E|).
37. Demuestre que si V es cualquier cubierta de vértices de una gráfica G y E es cualquier conjunto ajeno de aristas de G, entonces |E |≤|V |.
38. Dé un ejemplo de una gráfica conexa en la que para cada cubierta de vértices V y cada conjunto ajeno de aristas E , se tiene |E | < |V |. Pruebe que su ejemplo tiene la propiedad requerida.
39. Muestre cómo un árbol binario con n aristas se puede codificar como una cadena de n+1 unos y n+1 ceros donde, si se lee de izquierda a derecha, el número de ceros nunca excede al número de unos. Demuestre que cada cadena de este tipo representa un árbol binario. Sugerencia: Considere un recorrido preorden del árbol binario en el que un 1 significa que una arista está presente, y un 0 significa que una arista está ausente. Agregue un uno adicional al principio de la cadena, y elimine el último cero.
