//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();
}
}
}