Arbol Binario Consola C#

//ClaseArbolBinarioBusqueda


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Arbol_Binario_Consola
{
    class ClaseArbolBinarioBusqueda
    {
        // Declaración privada  de la raíz del ABB
        private ClaseNodoArbolBinarioBusqueda raiz;

        // Constructor
        public ClaseArbolBinarioBusqueda()
        {
            Raiz = null;  // Inicializa el ABB vacío
        }

        // Propiedad pública para acceder a la raíz
        public ClaseNodoArbolBinarioBusqueda Raiz
        {
            get { return (raiz); }
            set { raiz = value; }
        }

        // Método público para detectar si el ABB está vacío
        public bool EstaVacio()
        {
            if (Raiz == null)
                return (true);
            else
                return (false);
        }

        // Método público que recibe como argumento el Nodo que se desea insertar
        public bool Insertar(ClaseNodoArbolBinarioBusqueda Nodo)
        {
            ClaseNodoArbolBinarioBusqueda NuevoNodo;

            if (EstaVacio())  // Si el ABB está vacío
            {
                // Creación del NuevoNodo
                NuevoNodo = new ClaseNodoArbolBinarioBusqueda();
                NuevoNodo = Nodo;
                Raiz = NuevoNodo;  // Establecer la Raíz
                return (true);  // Inserción exitosa
            }
            else
            {
                ClaseNodoArbolBinarioBusqueda NodoActual = Raiz;
                ClaseNodoArbolBinarioBusqueda Padre = null;

                // Inicia el recorrido del ABB hasta llegar a una hoja
                while (NodoActual != null)
                {
                    // Verifica si está duplicado
                    if (NodoActual.Dato == Nodo.Dato)
                        return (false);  // No se insertó ... duplicado

                    // Verifica el subárbol que debe recorrer
                    if (Nodo.Dato < NodoActual.Dato)
                    {
                        Padre = NodoActual;  // Recorre el subárbol izquierdo
                        NodoActual = NodoActual.HijoIzq;
                    }
                    else
                    {
                        Padre = NodoActual;  // Recorre el subárbol derecho
                        NodoActual = NodoActual.HijoDer;
                    }
                }

                // Creación del nuevo nodo
                NuevoNodo = new ClaseNodoArbolBinarioBusqueda();
                NuevoNodo = Nodo;

                if (Nodo.Dato < Padre.Dato)
                    Padre.HijoIzq = NuevoNodo;  // Se inserta por la Izquierda
                else
                    Padre.HijoDer = NuevoNodo;  // Se inserta por la Derecha

                return (true);  // Inserción exitosa
            }
        }

        // Método público que recibe como argumento el Nodo que se desea eliminar
        public bool Eliminar(ClaseNodoArbolBinarioBusqueda Nodo)
        {
            if (EstaVacio()) // Verifica si el ABB está vacío
                return (false); // No se eliminó... está vacío

            ClaseNodoArbolBinarioBusqueda NodoActual = Raiz, Padre = null;

            // Búsqueda del nodo que se desea eliminar
            while (NodoActual.Dato != Nodo.Dato)
            {
                if (Nodo.Dato < NodoActual.Dato)
                {
                    Padre = NodoActual;
                    NodoActual = NodoActual.HijoIzq;  // Recorre el subárbol izquierdo
                }
                else
                {
                    if (Nodo.Dato > NodoActual.Dato)
                    {
                        Padre = NodoActual;
                        NodoActual = NodoActual.HijoDer; // Recorre el subárbol derecho
                    }
                }
               
                if (NodoActual == null)
                    return (false);  // No se eliminó ... no existe el nodo
            }

            // Se encontró el nodo que se desea eliminar

            // Caso 1: Si el NodoActual no tiene hijo derecho entonces su hijo izquierdo se convierte en
            // el nodo apuntado por su Padre
            if (NodoActual.HijoDer == null)
            {
                if (Padre == null)
                    Raiz = NodoActual.HijoIzq;
                else
                {
                    if (Padre.Dato > NodoActual.Dato)
                        Padre.HijoIzq = NodoActual.HijoIzq;
                    else
                    {
                        if (Padre.Dato < NodoActual.Dato)
                            Padre.HijoDer = NodoActual.HijoIzq;
                    }
                }
            }
            else
            {
                // Caso 2: Si el hijo derecho del NodoActual no tiene hijo izquierdo entonces el hijo derecho
                // del NodoActual reemplaza al NodoActual

                if (NodoActual.HijoDer.HijoIzq == null)
                {
                    NodoActual.HijoDer.HijoIzq = NodoActual.HijoIzq;
                    if (Padre == null)
                        Raiz = NodoActual.HijoDer;
                    else
                    {
                        if (Padre.Dato > NodoActual.Dato)
                            Padre.HijoIzq = NodoActual.HijoDer;
                        else
                        {
                            if (Padre.Dato < NodoActual.Dato)
                                Padre.HijoDer = NodoActual.HijoDer;
                        }
                    }
                }
                else
                {
                    // Caso 3: Si el hijo derecho del NodoActual tiene hijo izquierdo se reemplaza el
                    // NodoActual con el hijo menor del subárbol derecho

                    // Inicia la búsqueda del nodo ubicado más a la izquierda de la rama derecha

                    ClaseNodoArbolBinarioBusqueda NodoMenor = NodoActual.HijoDer.HijoIzq, PadreDelNodoMenor = NodoActual.HijoDer;

                    while (NodoMenor.HijoIzq != null)
                    {
                        PadreDelNodoMenor = NodoMenor;
                        NodoMenor = NodoMenor.HijoIzq;
                    }

                    // El subárbol izquierdo de su padre se convierte en el subárbol derecho del NodoMenor
                    PadreDelNodoMenor.HijoIzq = NodoMenor.HijoDer;

                    // Asigna los hijos del NodoMenor a los hijos del NodoActual
                    NodoMenor.HijoIzq = NodoActual.HijoIzq;
                    NodoMenor.HijoDer = NodoActual.HijoDer;

                    if (Padre == null)
                        Raiz = NodoMenor;
                    else
                    {
                        if (Padre.Dato > NodoActual.Dato)
                            Padre.HijoIzq = NodoMenor;
                        else
                        {
                            if (Padre.Dato < NodoActual.Dato)
                                Padre.HijoDer = NodoMenor;
                        }
                    }
                }
            }
            return (true);
        }

        // Método público que recibe como argumento el Nodo que se desea buscar
        public bool Buscar(ClaseNodoArbolBinarioBusqueda Nodo)
        {
            if (EstaVacio())
                return (false);  // No se encontró... el ABB está vacío

            // Inicia la búsqueda del Nodo en la Raíz
            ClaseNodoArbolBinarioBusqueda NodoActual = Raiz;

            while (NodoActual != null)
            {
                if (NodoActual.Dato == Nodo.Dato)
                    return (true);  // Búsqueda exitosa
                else
                    if (Nodo.Dato > NodoActual.Dato)
                        NodoActual = NodoActual.HijoDer; // Recorre el subárbol derecho
                    else
                        NodoActual = NodoActual.HijoIzq;  // Recorre el subárbol izquierdo
            }
            return (false);  // No se encontró el nodo
        }

        // Método público recursivo para recorrer el ABB en modo PreOrden
        public void PreOrden(ClaseNodoArbolBinarioBusqueda NodoActual, ref string Resultado)
        {
            if (NodoActual != null)
            {
                Resultado = Resultado + "-> " + NodoActual.Dato.ToString();  // Visita el NodoActual
                PreOrden(NodoActual.HijoIzq, ref Resultado); // Llamada recursiva para recorrer PreOrden el subárbol izquierdo
                PreOrden(NodoActual.HijoDer, ref Resultado);// Llamada recursiva para recorrer PreOrden el subárbol derecho
            }
        }

        // Método público recursivo para recorrer el ABB en modo InOrden
        public void InOrden(ClaseNodoArbolBinarioBusqueda NodoActual, ref string Resultado)
        {
            if (NodoActual != null)
            {
                InOrden(NodoActual.HijoIzq, ref Resultado); // Llamada recursiva para recorrer InOrden el subárbol izquierdo
                Resultado = Resultado + "-> " + NodoActual.Dato.ToString();  // Visita el NodoActual
                InOrden(NodoActual.HijoDer, ref Resultado); // Llamada recursiva para recorrer InOrden el subárbol derecho
            }
        }

        // Método público recursivo para recorrer el ABB en modo PostOrden
        public void PostOrden(ClaseNodoArbolBinarioBusqueda NodoActual, ref string Resultado)
        {
            if (NodoActual != null)
            {
                PostOrden(NodoActual.HijoIzq, ref Resultado); // Llamada recursiva para recorrer PostOrden el subárbol izquierdo
                PostOrden(NodoActual.HijoDer, ref Resultado); // Llamada recursiva para recorrer PostOrden el subárbol derecho
                Resultado = Resultado + "-> " + NodoActual.Dato.ToString();  // Visita el NodoActual
            }
        }


        // Método público recursivo para vaciar el Árbol Binario de Búsqueda
        public void Vaciar()
        {
            if (!EstaVacio())  // Si no está vacío ...
            {
                // Se invoca el método recursivo para recorrer el ABB y eliminar cada uno de sus nodos
                // (iniciando en la Raiz)
                RecorrerYBorrar(Raiz);

                Raiz = null; // Se inicializa el ABB vacío
            }
        }

        // Método recursivo privado para recorrer el ABB y eliminar cada nodo
        private void RecorrerYBorrar(ClaseNodoArbolBinarioBusqueda NodoActual)
        {
            if (NodoActual != null)
            {
                RecorrerYBorrar(NodoActual.HijoIzq); // Llamada recursiva para recorrer PostOrden el subárbol izquierdo
                RecorrerYBorrar(NodoActual.HijoDer); // Llamada recursiva para recorrer PostOrden el subárbol derecho
                Eliminar(NodoActual);  // Elimina el NodoActual
            }
        }

    }
}


/////////////////////ClaseNodoArbolBinarioBusqueda



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Arbol_Binario_Consola
{
    class ClaseNodoArbolBinarioBusqueda
    {
        private ClaseNodoArbolBinarioBusqueda hijoizq;
        private int dato;
        private ClaseNodoArbolBinarioBusqueda hijoder;

        // Constructor
        public ClaseNodoArbolBinarioBusqueda()
        {
            HijoDer = null;
            HijoIzq = null;
        }

        // Propiedad pública para acceder al dato
        public int Dato
        {
            get { return (dato); }
            set { dato = value; }
        }

        // Propiedad pública para acceder al hijo izquierdo
        public ClaseNodoArbolBinarioBusqueda HijoIzq
        {
            get { return (hijoizq); }
            set { hijoizq = value; }
        }

        // Propiedad pública para acceder al hijo derecho
        public ClaseNodoArbolBinarioBusqueda HijoDer
        {
            get { return (hijoder); }
            set { hijoder = value; }
        }

    }
}

/////////////////////////program

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Arbol_Binario_Consola

{

    class Program

    {

        static ClaseArbolBinarioBusqueda ArbolBinarioBusqueda = new ClaseArbolBinarioBusqueda();

        static void Main(string[] args)

        {

            int opcion = 0;

            ClaseNodoArbolBinarioBusqueda Nodo;

            Nodo = new ClaseNodoArbolBinarioBusqueda();  Nodo.Dato = 90; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 50; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 150; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 20; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 75; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 95; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 175; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 5; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 25; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 66; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 80; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 92; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 111; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 166; ArbolBinarioBusqueda.Insertar(Nodo);

            Nodo = new ClaseNodoArbolBinarioBusqueda(); Nodo.Dato = 200; ArbolBinarioBusqueda.Insertar(Nodo);

        

            do

            {

                Console.Clear();

                Console.WriteLine("ÁRBOLES BINARIOS DE BÚSQUEDA\n");

                Console.WriteLine("1.- Insertar nodo");

                Console.WriteLine("2.- Eliminar nodo");

                Console.WriteLine("3.- Buscar nodo");

                Console.WriteLine("4.- Recorrido Pre-Orden");

                Console.WriteLine("5.- Recorrido In-Orden");

                Console.WriteLine("6.- Recorrido Post-Orden");

                Console.WriteLine("7.- Vaciar");

                Console.WriteLine("0.- Salir");

                Console.Write("\n¿Opción? ");

                opcion = int.Parse(Console.ReadLine());

                switch (opcion)

                {

                    case 1: InsertarNodo(); break;

                    case 2: EliminarNodo(); break;

                    case 3: BuscarNodo(); break;

                    case 4: RecorrerPreOrden(); break;

                    case 5: RecorrerInOrden(); break;

                    case 6: RecorrerPostOrden(); break;

                    case 7: VaciarArbol(); break;

                }

            } while (opcion != 0);

        }

        // Método para capturar un dato e insertarlo en el árbol binario de búsqueda

        static void InsertarNodo()

        {

            // Declaración del objeto local

            ClaseNodoArbolBinarioBusqueda Nodo = new ClaseNodoArbolBinarioBusqueda();

            Console.Clear();

            Console.WriteLine("INSERTAR DATO EN EL ÁRBOL BINARIO DE BÚSQUEDA");

            Console.Write("\nNúmero ? ");

            Nodo.Dato = int.Parse(Console.ReadLine());  // Captura del dato del nodo que se desea insertar

            if (ArbolBinarioBusqueda.Insertar(Nodo)) //Se invoca el método para insertar el nodo en el árbol binario de búsqueda

                Console.WriteLine("\nDato insertado en el Árbol Binario de Búsqueda");

            else

                Console.WriteLine("\nNo se insertó el dato (duplicado)");

            Console.ReadKey();

        }

        // Método para capturar un dato, buscarlo y eliminarlo del árbol binario de búsqueda

        static void EliminarNodo()

        {

            // Declaración del objeto local

            ClaseNodoArbolBinarioBusqueda Nodo = new ClaseNodoArbolBinarioBusqueda();

            Console.Clear();

            Console.WriteLine("ELIMINAR DATO DEL ÁRBOL BINARIO");

            Console.Write("\nNúmero ? ");

            Nodo.Dato = int.Parse(Console.ReadLine());  // Captura del dato del nodo que se desea eliminar

            if (ArbolBinarioBusqueda.Eliminar(Nodo)) //Se invoca el método para insertar el nodo en el ABB

                Console.WriteLine("\nDato eliminado del Árbol Binario de Búsqueda");

            else

                Console.WriteLine("\nNo se eliminó el dato (no existe)");

            Console.ReadKey();

        }

        // Método para buscar un dato en el árbol binario de búsqueda

        static void BuscarNodo()

        {

            // Declaración del objeto local

            ClaseNodoArbolBinarioBusqueda Nodo = new ClaseNodoArbolBinarioBusqueda();

            Console.Clear();

            Console.WriteLine("BUSCAR DATO EN EL ÁRBOL BINARIO");

            Console.Write("\nNúmero ? ");

            Nodo.Dato = int.Parse(Console.ReadLine()); // Captura del dato del nodo que se desea buscar

            if (ArbolBinarioBusqueda.Buscar(Nodo)) // Se invoca el método para buscar el nodo en el ABB

                Console.WriteLine("\nEl Dato sí está almacenado en el Árbol Binario de Búsqueda");

            else

                Console.WriteLine("\nNo se encontró el dato (no existe)");

            Console.ReadKey();

        }

        static void RecorrerPreOrden()

        {

            string Resultado = " ";  // Cadena que almacena los nodos visitados

            Console.Clear();

            Console.WriteLine("RECORRIDO PRE-ORDEN DEL ÁRBOL BINARIO DE BÚSQUEDA\n");

            if (!ArbolBinarioBusqueda.EstaVacio())

            {

                // Se ejecuta el método para recorrer los nodos almacenados en el árbol binario de búsqueda

                ArbolBinarioBusqueda.PreOrden(ArbolBinarioBusqueda.Raiz, ref Resultado);

            }

            else

                Resultado = "Árbol Binario de Búsqueda vacío ...";

            Console.WriteLine(Resultado+"\n");  // Despliega el Resultado

            Console.ReadKey();

        }

        static void RecorrerInOrden()

        {

            string Resultado = ""; // Cadena que almacena los nodos visitados

            Console.Clear();

            Console.WriteLine("RECORRIDO IN-ORDEN DEL ÁRBOL BINARIO DE BÚSQUEDA\n");

            if (!ArbolBinarioBusqueda.EstaVacio())

            {

                // Se ejecuta el método para recorrer los nodos almacenados en el árbol binario de búsqueda

                ArbolBinarioBusqueda.InOrden(ArbolBinarioBusqueda.Raiz, ref Resultado);

            }

            else

                Resultado = "Árbol Binario de Búsqueda vacío ...";

            Console.WriteLine(Resultado); // Despliega la cadena con los nodos visitados

            Console.ReadKey();

        }

        static void RecorrerPostOrden()

        {

            string Resultado = "";  // Cadena que almacena los nodos visitados

            Console.Clear();

            Console.WriteLine("RECORRIDO POST-ORDEN DEL ÁRBOL BINARIO DE BÚSQUEDA\n");

            if (!ArbolBinarioBusqueda.EstaVacio())

            {

                // Se ejecuta el método para recorrer los nodos almacenados en el árbol binario de búsqueda

                ArbolBinarioBusqueda.PostOrden(ArbolBinarioBusqueda.Raiz, ref Resultado);

            }

            else

                Resultado = "Árbol Binario de Búsqueda vacío ...";

            Console.WriteLine(Resultado);  // Despliega la cadena con los nodos visitados

            Console.ReadKey();

        }

        static void VaciarArbol()

        {

            Console.Clear();

            Console.WriteLine("VACIAR EL ÁRBOL BINARIO DE BÚSQUEDA\n");

            // Se ejecuta el método para recorrer el ABB y eliminar cada uno de sus nodos e 

            // inicializarlo vacío

            ArbolBinarioBusqueda.Vaciar();

            Console.WriteLine("Se eliminaron todos los nodos del ABB (Árbol vaciado)");

            Console.ReadKey();

        }

    }

}