CLR: .Net / Mono / Boo / Otros CLR > C#

 Como saber si el árbol esta equilibrado o no

(1/1)

rogerfor:
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# ---using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Arboles{       public class NodoT    {        public NodoT NodoIzquierdo;        public int Informacion;        public NodoT NodoDerecho;         //Constructor        public NodoT()        {            this.NodoIzquierdo = null;            this.Informacion = 0;            this.NodoDerecho = null;        }    }    class Program    {        static void Main(string[] args)        {            int Opcion = 0;            NodoT Raiz = null;            int Dato;              do            {                Opcion = Menu();                switch (Opcion)                {                    case 1:                        Console.Write("Valor del Nuevo Nodo: ");                        Dato = int.Parse(Console.ReadLine());                        if (Raiz == null)                        {                            NodoT NuevoNodo = new NodoT();                            NuevoNodo.Informacion = Dato;                            Raiz = NuevoNodo;                        }                        else                        {                            Insertar(Raiz, Dato);                        }                        Console.Clear();                        break;                     case 2:                        Recorrer(Raiz);                        Console.WriteLine("Fin del Recorrido,...");                        Console.ReadLine();                        Console.Clear();                        break;                     case 3:                        Console.Write("Teclee el Dato a buscar: ");                        Dato = int.Parse(Console.ReadLine());                        if (Raiz != null)                        {                            BuscarNodo(Raiz, Dato);                        }                        else                        {                            Console.WriteLine("EROR, Arbol Vacio...");                        }                        Console.Clear();                        break;                     case 4:                        Console.Write("Teclee el Dato a Eliminar: ");                        Dato = int.Parse(Console.ReadLine());                        if (Raiz != null)                        {                            EliminarNodo(ref Raiz, Dato);                        }                        else                        {                            Console.WriteLine("EROR, Arbol Vacio...");                        }                        Console.Clear();                        break;                     case 5:                        Finalizar();                        break;                     case 6:                        RecorrerPreOrden(Raiz);                        Console.WriteLine("Fin del Recorrido,...");                        Console.ReadLine();                        Console.Clear();                        break;                     default:                        Console.WriteLine("ERROR, Opción Invalida...");                        Console.ReadLine();                        Console.WriteLine("");                        break;                }            }            while (Opcion != 5);        }         static int Menu()        {            int Resultado = 0;            Console.WriteLine("MENU DE ARBOLES");            Console.WriteLine("");            Console.WriteLine("1. - Registrar un Nuevo Nodo");            Console.WriteLine("2. - Mostrar/Recorrer  el Arbol");            Console.WriteLine("6. - Recorrido pre-orden");            Console.WriteLine("3. - Buscar un Nodo");            Console.WriteLine("4. - Eliminar un Nodo");            Console.WriteLine("5. - Finalizar programa");            Console.WriteLine("");            Console.WriteLine("Opcion: ");             Resultado = int.Parse(Console.ReadLine());            Console.WriteLine("");            return Resultado;        }         //Insertar un arbol binario        static void Insertar(NodoT Raiz, int Dato)        {            if (Dato < Raiz.Informacion)            {                if (Raiz.NodoIzquierdo == null)                {                    NodoT NuevoNodo = new NodoT();                    NuevoNodo.Informacion = Dato;                    Raiz.NodoIzquierdo = NuevoNodo;                }                else                {                    Insertar(Raiz.NodoIzquierdo, Dato); //Llamada recursiva                }            }                        else            {                if (Dato > Raiz.Informacion)                { if(Raiz.NodoDerecho == null)                {                    NodoT NuevoNodo = new NodoT();                    NuevoNodo.Informacion = Dato;                    Raiz.NodoDerecho =NuevoNodo;                }                else                {                    //Llamada recursiva por lado derecho                    Insertar(Raiz.NodoDerecho, Dato);                }              }                else                {                    //El nodo no existe en el arbol                    Console.WriteLine("Nodo Existente, Imposible Insertar");                    Console.ReadLine();                }            }        }         //Metodo de recorrido        static void BuscarNodo(NodoT Raiz, int Dato)        {            if (Dato < Raiz.Informacion)            {                if (Raiz.NodoIzquierdo == null) //buscar por el sub-arbol izquierdo                {                    Console.WriteLine("ERROR, No se encuentra el Nodo...");                    Console.ReadLine();                }                else                {                    BuscarNodo(Raiz.NodoIzquierdo, Dato);                }            }            else            {                if(Dato>Raiz.Informacion)                {                    if(Raiz.NodoDerecho==null)//Buscar por sub-arbol derecho)                    {                        Console.WriteLine("ERROR, No se encuentra el Nodo...");                        Console.ReadLine();                    }                    else                    {                        BuscarNodo(Raiz.NodoDerecho, Dato);                    }                }                else                {                    //El nodo se encontro                    Console.WriteLine("Nodo Localizado en el Arbol...");                    Console.ReadLine();                }            }        }         //Metodo Eliminar        static void EliminarNodo(ref NodoT Raiz, int Dato)        {            if(Raiz!=null)            {                if (Dato < Raiz.Informacion)                {                    EliminarNodo(ref Raiz.NodoIzquierdo, Dato);                }                else                {                    if(Dato> Raiz.Informacion)                    {                        EliminarNodo(ref Raiz.NodoDerecho, Dato);                    }                    else                    {                        NodoT NodoEliminar = Raiz; //Si lo encontro                            if(NodoEliminar.NodoDerecho== null)                            {                                Raiz=NodoEliminar.NodoIzquierdo;                            }                            else                            {                                if(NodoEliminar.NodoIzquierdo == null)                                {                                    Raiz=NodoEliminar.NodoDerecho;                                }                                else                                {                                    NodoT AuxiliarNodo =null;                                    NodoT Auxiliar = Raiz.NodoIzquierdo;                                    bool bandera = false;                                    while(Auxiliar.NodoDerecho!=null)                                    {                                        AuxiliarNodo= Auxiliar;                                        Auxiliar = Auxiliar.NodoDerecho;                                        bandera=true;                                    }                                    Raiz.Informacion = Auxiliar.Informacion;                                    NodoEliminar = Auxiliar;                                    if(bandera==true)                                    {                                        AuxiliarNodo.NodoDerecho = Auxiliar.NodoIzquierdo;                                    }                                    else                                    {                                        Raiz.NodoIzquierdo = Auxiliar.NodoIzquierdo;                                    }                              }            }        }    }}            else            {                Console.WriteLine("ERROR, El nodo no se encuentra en el arbol...");                Console.ReadLine();            }        }          //Metodo de Finailizacion        static void Finalizar()        {            Console.WriteLine("Fin del programa, presiona cualquier tecla para continuar...");            Console.ReadLine();        }          //        static void Recorrer(NodoT Raiz)        {            if (Raiz != null)            {                Recorrer(Raiz.NodoIzquierdo);                Console.Write("{0}, ", Raiz.Informacion);                Recorrer(Raiz.NodoDerecho);            }        }         //Recorrido preorden        static void RecorrerPreOrden(NodoT Raiz)        {            if (Raiz != null)            {                Console.Write("{0}, ", Raiz.Informacion);                RecorrerPreOrden(Raiz.NodoIzquierdo);                RecorrerPreOrden(Raiz.NodoDerecho);            }        }               }//fin program }//fin namespace 

Navegación

[0] Índice de Mensajes