• Miércoles 3 de Junio de 2020, 21:17

Autor Tema:  Como saber si el árbol esta equilibrado o no  (Leído 1365 veces)

rogerfor

  • Miembro activo
  • **
  • Mensajes: 57
    • Ver Perfil
Como saber si el árbol esta equilibrado o no
« en: Domingo 4 de Marzo de 2012, 04:15 »
0
Buenas noches, en el curso de estructuras de datos estamos viendo recorridos de arboles y arboles AVL, el ingeniero nos dio un código para que lo estudiáramos, pero pues me cuesta mucho esto, y quisiera saber si me pueden ayudar sobre como es una funcion para saber si el árbol es equilibrado o no, solo para saberlo que se es que la formula es FE = altura_nododerecho - altura_nodoizquierdo pero no se como implementarlo, les agradezco cualquier ayuda que me puedan dar.
aquí les dejo el código que nos dio. es algo básico aunque algo largo, solo recorre el arbol normal y en preorden y agrega o elimina nodos.

Código: C#
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace Arboles
  7. {
  8.  
  9.  
  10.  
  11.     public class NodoT
  12.     {
  13.         public NodoT NodoIzquierdo;
  14.         public int Informacion;
  15.         public NodoT NodoDerecho;
  16.  
  17.         //Constructor
  18.         public NodoT()
  19.         {
  20.             this.NodoIzquierdo = null;
  21.             this.Informacion = 0;
  22.             this.NodoDerecho = null;
  23.         }
  24.     }
  25.     class Program
  26.     {
  27.         static void Main(string[] args)
  28.         {
  29.             int Opcion = 0;
  30.             NodoT Raiz = null;
  31.             int Dato;
  32.  
  33.  
  34.             do
  35.             {
  36.                 Opcion = Menu();
  37.                 switch (Opcion)
  38.                 {
  39.                     case 1:
  40.                         Console.Write("Valor del Nuevo Nodo: ");
  41.                         Dato = int.Parse(Console.ReadLine());
  42.                         if (Raiz == null)
  43.                         {
  44.                             NodoT NuevoNodo = new NodoT();
  45.                             NuevoNodo.Informacion = Dato;
  46.                             Raiz = NuevoNodo;
  47.                         }
  48.                         else
  49.                         {
  50.                             Insertar(Raiz, Dato);
  51.                         }
  52.                         Console.Clear();
  53.                         break;
  54.  
  55.                     case 2:
  56.                         Recorrer(Raiz);
  57.                         Console.WriteLine("Fin del Recorrido,...");
  58.                         Console.ReadLine();
  59.                         Console.Clear();
  60.                         break;
  61.  
  62.                     case 3:
  63.                         Console.Write("Teclee el Dato a buscar: ");
  64.                         Dato = int.Parse(Console.ReadLine());
  65.                         if (Raiz != null)
  66.                         {
  67.                             BuscarNodo(Raiz, Dato);
  68.                         }
  69.                         else
  70.                         {
  71.                             Console.WriteLine("EROR, Arbol Vacio...");
  72.                         }
  73.                         Console.Clear();
  74.                         break;
  75.  
  76.                     case 4:
  77.                         Console.Write("Teclee el Dato a Eliminar: ");
  78.                         Dato = int.Parse(Console.ReadLine());
  79.                         if (Raiz != null)
  80.                         {
  81.                             EliminarNodo(ref Raiz, Dato);
  82.                         }
  83.                         else
  84.                         {
  85.                             Console.WriteLine("EROR, Arbol Vacio...");
  86.                         }
  87.                         Console.Clear();
  88.                         break;
  89.  
  90.                     case 5:
  91.                         Finalizar();
  92.                         break;
  93.  
  94.                     case 6:
  95.                         RecorrerPreOrden(Raiz);
  96.                         Console.WriteLine("Fin del Recorrido,...");
  97.                         Console.ReadLine();
  98.                         Console.Clear();
  99.                         break;
  100.  
  101.                     default:
  102.                         Console.WriteLine("ERROR, Opción Invalida...");
  103.                         Console.ReadLine();
  104.                         Console.WriteLine("");
  105.                         break;
  106.                 }
  107.             }
  108.             while (Opcion != 5);
  109.         }
  110.  
  111.         static int Menu()
  112.         {
  113.             int Resultado = 0;
  114.             Console.WriteLine("MENU DE ARBOLES");
  115.             Console.WriteLine("");
  116.             Console.WriteLine("1. - Registrar un Nuevo Nodo");
  117.             Console.WriteLine("2. - Mostrar/Recorrer  el Arbol");
  118.             Console.WriteLine("6. - Recorrido pre-orden");
  119.             Console.WriteLine("3. - Buscar un Nodo");
  120.             Console.WriteLine("4. - Eliminar un Nodo");
  121.             Console.WriteLine("5. - Finalizar programa");
  122.             Console.WriteLine("");
  123.             Console.WriteLine("Opcion: ");
  124.  
  125.             Resultado = int.Parse(Console.ReadLine());
  126.             Console.WriteLine("");
  127.             return Resultado;
  128.         }
  129.  
  130.         //Insertar un arbol binario
  131.         static void Insertar(NodoT Raiz, int Dato)
  132.         {
  133.             if (Dato < Raiz.Informacion)
  134.             {
  135.                 if (Raiz.NodoIzquierdo == null)
  136.                 {
  137.                     NodoT NuevoNodo = new NodoT();
  138.                     NuevoNodo.Informacion = Dato;
  139.                     Raiz.NodoIzquierdo = NuevoNodo;
  140.                 }
  141.                 else
  142.                 {
  143.                     Insertar(Raiz.NodoIzquierdo, Dato); //Llamada recursiva
  144.                 }
  145.             }
  146.            
  147.             else
  148.             {
  149.                 if (Dato > Raiz.Informacion)
  150.                 { if(Raiz.NodoDerecho == null)
  151.                 {
  152.                     NodoT NuevoNodo = new NodoT();
  153.                     NuevoNodo.Informacion = Dato;
  154.                     Raiz.NodoDerecho =NuevoNodo;
  155.                 }
  156.                 else
  157.                 {
  158.                     //Llamada recursiva por lado derecho
  159.                     Insertar(Raiz.NodoDerecho, Dato);
  160.                 }
  161.               }
  162.                 else
  163.                 {
  164.                     //El nodo no existe en el arbol
  165.                     Console.WriteLine("Nodo Existente, Imposible Insertar");
  166.                     Console.ReadLine();
  167.                 }
  168.             }
  169.         }
  170.  
  171.         //Metodo de recorrido
  172.         static void BuscarNodo(NodoT Raiz, int Dato)
  173.         {
  174.             if (Dato < Raiz.Informacion)
  175.             {
  176.                 if (Raiz.NodoIzquierdo == null) //buscar por el sub-arbol izquierdo
  177.                 {
  178.                     Console.WriteLine("ERROR, No se encuentra el Nodo...");
  179.                     Console.ReadLine();
  180.                 }
  181.                 else
  182.                 {
  183.                     BuscarNodo(Raiz.NodoIzquierdo, Dato);
  184.                 }
  185.             }
  186.             else
  187.             {
  188.                 if(Dato>Raiz.Informacion)
  189.                 {
  190.                     if(Raiz.NodoDerecho==null)//Buscar por sub-arbol derecho)
  191.                     {
  192.                         Console.WriteLine("ERROR, No se encuentra el Nodo...");
  193.                         Console.ReadLine();
  194.                     }
  195.                     else
  196.                     {
  197.                         BuscarNodo(Raiz.NodoDerecho, Dato);
  198.                     }
  199.                 }
  200.                 else
  201.                 {
  202.                     //El nodo se encontro
  203.                     Console.WriteLine("Nodo Localizado en el Arbol...");
  204.                     Console.ReadLine();
  205.                 }
  206.             }
  207.         }
  208.  
  209.         //Metodo Eliminar
  210.         static void EliminarNodo(ref NodoT Raiz, int Dato)
  211.         {
  212.             if(Raiz!=null)
  213.             {
  214.                 if (Dato < Raiz.Informacion)
  215.                 {
  216.                     EliminarNodo(ref Raiz.NodoIzquierdo, Dato);
  217.                 }
  218.                 else
  219.                 {
  220.                     if(Dato> Raiz.Informacion)
  221.                     {
  222.                         EliminarNodo(ref Raiz.NodoDerecho, Dato);
  223.                     }
  224.                     else
  225.                     {
  226.                         NodoT NodoEliminar = Raiz; //Si lo encontro
  227.                             if(NodoEliminar.NodoDerecho== null)
  228.                             {
  229.                                 Raiz=NodoEliminar.NodoIzquierdo;
  230.                             }
  231.                             else
  232.                             {
  233.                                 if(NodoEliminar.NodoIzquierdo == null)
  234.                                 {
  235.                                     Raiz=NodoEliminar.NodoDerecho;
  236.                                 }
  237.                                 else
  238.                                 {
  239.                                     NodoT AuxiliarNodo =null;
  240.                                     NodoT Auxiliar = Raiz.NodoIzquierdo;
  241.                                     bool bandera = false;
  242.                                     while(Auxiliar.NodoDerecho!=null)
  243.                                     {
  244.                                         AuxiliarNodo= Auxiliar;
  245.                                         Auxiliar = Auxiliar.NodoDerecho;
  246.                                         bandera=true;
  247.                                     }
  248.                                     Raiz.Informacion = Auxiliar.Informacion;
  249.                                     NodoEliminar = Auxiliar;
  250.                                     if(bandera==true)
  251.                                     {
  252.                                         AuxiliarNodo.NodoDerecho = Auxiliar.NodoIzquierdo;
  253.                                     }
  254.                                     else
  255.                                     {
  256.                                         Raiz.NodoIzquierdo = Auxiliar.NodoIzquierdo;
  257.                                     }
  258.              
  259.  
  260.                }
  261.             }
  262.         }
  263.     }
  264. }
  265.             else
  266.             {
  267.                 Console.WriteLine("ERROR, El nodo no se encuentra en el arbol...");
  268.                 Console.ReadLine();
  269.             }
  270.         }
  271.  
  272.  
  273.         //Metodo de Finailizacion
  274.         static void Finalizar()
  275.         {
  276.             Console.WriteLine("Fin del programa, presiona cualquier tecla para continuar...");
  277.             Console.ReadLine();
  278.         }
  279.  
  280.  
  281.         //
  282.         static void Recorrer(NodoT Raiz)
  283.         {
  284.             if (Raiz != null)
  285.             {
  286.                 Recorrer(Raiz.NodoIzquierdo);
  287.                 Console.Write("{0}, ", Raiz.Informacion);
  288.                 Recorrer(Raiz.NodoDerecho);
  289.             }
  290.         }
  291.  
  292.         //Recorrido preorden
  293.         static void RecorrerPreOrden(NodoT Raiz)
  294.         {
  295.             if (Raiz != null)
  296.             {
  297.                 Console.Write("{0}, ", Raiz.Informacion);
  298.                 RecorrerPreOrden(Raiz.NodoIzquierdo);
  299.                 RecorrerPreOrden(Raiz.NodoDerecho);
  300.             }
  301.         }
  302.  
  303.        
  304.  
  305.  
  306.     }//fin program
  307.  
  308. }//fin namespace
  309.