Manejo de arboles binarios

pascal:
Uses Crt;

Type Arbol = ^Nodo;
     Nodo = Record
            Info: Integer;
            Izq,Der: Arbol;
            End;

Var A: Arbol;
    N: Integer;
    Opc: Char;

Procedure Insertar(Var A: Arbol; N: Integer);
Begin
     If A = Nil Then
      Begin
      New(A);
      A^.Info := N;
      A^.Izq := Nil;
      A^.Der := Nil;
      End
       Else
        If N < A^.Info Then Insertar(A^.Izq,N)
          Else Insertar(A^.Der,N);
End;

Procedure In_orden(A: Arbol);
Begin
     If A <> Nil Then
      Begin
      In_Orden(A^.Izq);
      WriteLn(A^.Info);
      In_Orden(A^.Der);
      End;
End;

Function Busqueda (A: Arbol; N: Integer): Boolean;
Begin
     Busqueda:= False;
     If A <> Nil Then
      If A^.Info = N Then Busqueda:= True
         Else
          If N < A^.info Then Busqueda:= Busqueda(A^.Izq,N)
            Else Busqueda:= Busqueda(A^.Der,N);
End;

Function Menor (A: Arbol): Integer;
Var I1: Integer;
Min: Integer;
Begin
Min:= A^.Info;
I1:= 0;
If (A^.Izq <> Nil) Then
 Begin
 I1:= Menor(A^.Izq);
 If I1 < Min Then Min:= I1;
 End;
If (A^.Der <> Nil) Then
 Begin
 I1:= Menor(A^.Der);
 If I1 < Min Then Min:= I1;
 End;
Menor:= Min;
End;

Procedure Eliminar(Var A: Arbol; N: Integer);

Procedure Borrar(Var A,Aux: Arbol);
Begin
If A^.Der <> Nil Then
 Borrar(A^.Der,Aux)  Else
  Begin
   Aux^.Info:= A^.Info;
   Aux:= A;
   A:= A^.izq;
  End;
End;

Var Aux: Arbol;
Begin
If N < A^.Info Then Eliminar(A^.Izq,N) Else
 If N > A^.Info Then Eliminar(A^.Der,N) Else
  Begin
  Aux:= A;
  If Aux^.Der = Nil Then A:= Aux^.Izq
   Else
    If Aux^.Izq = Nil Then A:= Aux^.Der
      Else Borrar(Aux^.Izq,Aux);
  End;
End;

Begin
     A:= Nil;
     Repeat
           ClrScr;
           WriteLn('1- Agregar elemento al arbol');
           WriteLn('2- Mostrar el arbol ordenado');
           WriteLn('3- Saber si un n£mero est  en el arbol');
           WriteLn('4- Eliminar un elemento del arbol');
           WriteLn('5- Obtener el menor elemento');
           WriteLn('6- Salir');
           write('Opci¢n: ');
           Opc:= ReadKey;
           If Opc = '1' Then
            Begin
             ClrScr;
             Write('Ingrese un n£mero: ');
             ReadLn(n);
             Insertar(a,n);
            End;
           If Opc = '2' Then
           Begin
            ClrScr;
            WriteLn('Estos son los elementos ordenados: ');
            In_Orden(a);
            WriteLn;
            Write('Presione cualquier tecla para continuar...');
            ReadKey;
           End;
           If Opc = '3' Then
            Begin
            ClrScr;
            Write('Ingrese un n£mero: ');
            ReadLn(n);
            If Busqueda(a,n) Then WriteLn('El elemento est  en el arbol.')
              Else WriteLn('El elemento no est  en el  rbol.');
            WriteLn;
            Write('Presione cualquier tecla para continuar...');
            ReadKey;
            End;
           If Opc = '4' Then
            Begin
            ClrScr;
            Write('Ingrese el elemento a borrar: ');
            ReadLn(n);
            If Busqueda(a,n) Then
             Begin
              Eliminar(a,n);
              WriteLn('El elemento fue eliminado.');
             End Else WriteLn('El elemento no est  en el  rbol.');
            WriteLn;
            Write('Presione cualquier tecla para continuar...');
            ReadKey;
            End;
           If Opc = '5' Then
           Begin
            ClrScr;
            If A = Nil Then WriteLn('No hay elementos en el arbol.') Else
            WriteLn('El menor es: ',Menor(A));
            ReadKey;
           End;
     Until (Opc = '6');
End.

6 Responses to “Manejo de arboles binarios”

  1. JLSantillan Says:
    November 24th, 2007 at 4:41 pm

    Hola, pasaba por aca buscando codigo para mi laboratorio de programacion en la universidad. Al ver la funcion menor veo que tambien hacen recursion por el lado derecho, lo cual me parece raro si hablamos de arboles de busqueda binarios. Creo que mas sentido haria...

    pascal:
    Function Menor (A: Arbol): Integer;
    Var
    Begin
    If (A`.Izq = NIL) then { No hay nodos por el lado izquierdo }
       Menor := A^.Info
    Else
       Menor := Menor(A^.izq);
    End;

    Pues se me hace de mas sentido la busqueda solo por la izquierda, espero no equivocarme xD
    Saludos, y gracias por el codigo!

  2. admin Says:
    November 24th, 2007 at 4:45 pm

    Gracias por tu aportación JLSantillan. Sinceramente estoy algo desconectado de esto de los algoritmos desde hace unos años, pero si alguien para por aquí y necesita de estos ejemplos, espero sirva de mucho tu información.

    Gracias ;) Suerte con tu laboratorio de programación.

  3. JLSantillan Says:
    November 24th, 2007 at 5:20 pm

    seccion:
    ***********************************

    pascal:
    Function Menor (A: Arbol): Integer;
    Var
    Begin

    ***********************************
    El codigo lo escribi de inspiracion propio y falto remover el Var, ya que no declaro variables :P

  4. admin Says:
    November 24th, 2007 at 5:22 pm

    Gracias JLSantillan, se te agradece ;)

  5. PocaLuz Says:
    December 5th, 2007 at 11:32 am

    A veces las soluciones iterativas son mas eficientes y claras; para las funciones mayor y menor...:

    pascal:
    {para hacerlo mas general devuelve un puntero}

    Function Menor(A:arbol):arbol;
    Begin
        if (Anil) then
            while (A˄.izqnil) do
                A:=A˄.izq;

        Menor:=A;
    End;

  6. Crackman87 Says:
    December 25th, 2007 at 6:23 pm

    El codigo de la funcion menor escrita originalmente es correcto ya que los procedimientos y funciones son de arboles binarios, en cuanto a los algoritmos de JLSantillan y PocaLuz, estan hechos para arboles binarios de busqueda, en los que su elemento mas pequeño estará siempre en la rama izquierda en el nivel mas bajo posible. Pero repito en arboles binarios a secas esto no tiene porque suceder...

    Por cierto gracias por el codigo...

¿Ya le viste algún error? Dejanos tu correción ;-)

Antes de comentar: Gran parte de los ejercicios propuestos no tienen librerías debido a que Wordpress elimina los tags HTML. Si sabes/tienes/conoces las librerías que hacen falta, déjalo en los comentarios.

Otro punto antes de comentar, Si vas a sugerir un segmento de código en algún lenguaje debes hacerlo así:

De esta manera el código sale coloreado.

Otro punto importante para muchos que sienten que se les ignora: Todos los comentarios los reviso y en su debido momento los apruebo, pero ojo con el último párrafo.

Para poner los símbolos de las librerías sin que desaparezcan, debes escribir los símbolos de mayor > y menor qué < con su entidad HTML correspondiente, así como el símbolo de &

Mis Algoritmos se reserva el derecho de alterar, publicar o no los comentarios así como cambiar estas reglas de uso.

Si estas de acuerdo, adelante puedes comentar :)

P.D. No le hago tareas a nadie, mejor hagan la mía :P