Altillo.com > Exámenes > ORT > Programación II

1. Dado un árbol binario de búsqueda cuyas claves son enteros pares y positivos.
SE PIDE:
a) Definir la estructura en Pascal (parte declarativa: CONST, TYPE y VAR).
b) Desarrollar un procedimiento con los parámetros necesarios y suficientes, que reciba el puntero a la raíz del árbol y agregue un hijo a los nodos con un solo hijo, con clave igual a la del padre más o menos 1 según se agregue a izquierda o derecha respectivamente.
Ejemplo: 
        (14)
        /    \
    (8)    (30)
        \   /
    (12) (16)
                \
                (18)

producirá:
           (14)
          /      \
      (8)       (30)
      /  \        /    \
  [7] (12) (16) [31]
               /    \
           [15] (18) 

c) ¿Cómo recorrió el árbol?
d) ¿Pudo utilizar otros recorridos para resolver el ejercicio?
En caso afirmativo: ¿Cuáles? - Justificar.
En caso negativo: ¿Por qué?

2. Dado las siguientes declaraciones y el procedimiento FDIC972:
Type
  parb = ^t_nodo;
  t_nodo = Record
                      dato: String[2];
                      can: Integer;
                      izq, der: parb;
                 End;
Function Eshoja (a:parb):Boolean;
Begin
  eshoja := (a<>Nil) and (a^.izq = Nil) and (a^.der = Nil);
End;
Procedure FDIC972 (arbol:parb);
Begin
  If arbol <> nil Then
    If Eshoja (arbol^.izq) Then
      arbol^.can := arbol^.can + 1
    Else
      FDIC972(arbol^.izq);
        If Eshoja (arbol ^.der) Then
          arbol^.can := arbol^.can + 1
        Else
          FDIC972(arbol^.der);
End;
<< SE PIDE >>:
a) Realizar el seguimiento del procedimiento FDIC972 cuando se lo llama con el puntero a la raíz del siguiente árbol binario:
                            (20 | 0)
                            /         \
                  (10 | 0)          (30 | 0)
                  /         \          /          \
        (4 | 0)      (15 | 0) (25 | 0) (40 | 0)
                                                 /
                                        (35 | 0) 
IMPORTANTE :Mostrar gráficamente cómo se modifica el árbol y en qué momento se produce cada modificación.
Usar la notación FDIC972(^10) para indicar llamado al procedimiento con el puntero al nodo que contiene 10.
b) Sin realizar nuevamente el seguimiento, indicar cómo quedaría el siguiente árbol luego de ejecutar el procedimiento FDIC972 con el puntero a su raíz.
                            (50 | 0)
                            /         \
                  (30 | 0)         (80 | 0)
                   /                   /         \
            (15 | 0)         (60 | 0) (90 | 0)