ARBOLES BINARIOS
Los árboles
binarios en C# son estructuras de datos jerárquicas donde cada nodo tiene, como
máximo, dos hijos: izquierdo y derecho. Son fundamentales para organizar
información de forma no secuencial y optimizar procesos de búsqueda y
ordenamiento.
CODIGO:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication9
{
using System;
// Clase Nodo del árbol
public class Nodo
{
public int valor;
public Nodo izquierdo;
public Nodo derecho;
public Nodo(int valor)
{
this.valor = valor;
izquierdo = null;
derecho = null;
}
}
// Clase principal del Árbol
Binario de Búsqueda
public class ArbolBinarioBusqueda
{
private Nodo raiz;
public ArbolBinarioBusqueda()
{
raiz = null;
}
// Insertar un nuevo valor
public void Insertar(int
valor)
{
raiz = InsertarRec(raiz,
valor);
}
private Nodo InsertarRec(Nodo
raiz, int valor)
{
// Si el nodo está vacío,
crear nuevo nodo
if (raiz == null)
{
raiz = new Nodo(valor);
return raiz;
}
// Ir a la izquierda si
el valor es menor
if (valor <
raiz.valor)
raiz.izquierdo =
InsertarRec(raiz.izquierdo, valor);
// Ir a la derecha si el
valor es mayor
else if (valor > raiz.valor)
raiz.derecho = InsertarRec(raiz.derecho, valor);
return raiz;
}
// Buscar un valor en el
árbol
public bool Buscar(int valor)
{
return BuscarRec(raiz,
valor);
}
private bool BuscarRec(Nodo
raiz, int valor)
{
// Árbol vacío o valor
encontrado
if (raiz == null || raiz.valor == valor)
return raiz != null;
// Buscar en subárbol izquierdo si valor es menor
if (valor <
raiz.valor)
return
BuscarRec(raiz.izquierdo, valor);
// Buscar en subárbol
derecho si valor es mayor
return
BuscarRec(raiz.derecho, valor);
}
// Eliminar un nodo
public void Eliminar(int
valor)
{
raiz = EliminarRec(raiz,
valor);
}
private Nodo EliminarRec(Nodo
raiz, int valor)
{
if (raiz == null) return
raiz;
if (valor < raiz.valor)
raiz.izquierdo =
EliminarRec(raiz.izquierdo, valor);
else if (valor > raiz.valor)
raiz.derecho = EliminarRec(raiz.derecho, valor);
else
{
// Nodo con un solo
hijo o sin hijos
if (raiz.izquierdo == null)
return
raiz.derecho;
else if
(raiz.derecho == null)
return raiz.izquierdo;
// Nodo con dos
hijos: obtener el inorder successor
raiz.valor =
MinimoValor(raiz.derecho);
// Eliminar el
inorder successor
raiz.derecho =
EliminarRec(raiz.derecho, raiz.valor);
}
return raiz;
}
private int MinimoValor(Nodo
raiz)
{
int minimo = raiz.valor;
while (raiz.izquierdo != null)
{
minimo =
raiz.izquierdo.valor;
raiz =
raiz.izquierdo;
}
return minimo;
}
// Recorrido Inorden
(izquierda-raíz-derecha)
public void Inorden()
{
InordenRec(raiz);
Console.WriteLine();
}
private void InordenRec(Nodo
raiz)
{
if (raiz != null)
{
InordenRec(raiz.izquierdo);
Console.Write(raiz.valor
+ " ");
InordenRec(raiz.derecho);
}
}
// Recorrido Preorden
(raíz-izquierda-derecha)
public void Preorden()
{
PreordenRec(raiz);
Console.WriteLine();
}
private void PreordenRec(Nodo
raiz)
{
if (raiz != null)
{
Console.Write(raiz.valor
+ " ");
PreordenRec(raiz.izquierdo);
PreordenRec(raiz.derecho);
}
}
// Recorrido Postorden
(izquierda-derecha-raíz)
public void Postorden()
{
PostordenRec(raiz);
Console.WriteLine();
}
private void PostordenRec(Nodo
raiz)
{
if (raiz != null)
{
PostordenRec(raiz.izquierdo);
PostordenRec(raiz.derecho);
Console.Write(raiz.valor
+ " ");
}
}
// Altura del árbol
public int Altura()
{
return
AlturaRec(raiz);
}
private int AlturaRec(Nodo
raiz)
{
if (raiz == null)
return -1;
return 1 + Math.Max(AlturaRec(raiz.izquierdo),
AlturaRec(raiz.derecho));
}
// Verificar si el árbol está
vacío
public bool EstaVacio()
{
return raiz == null;
}
}
// Programa principal para probar
el árbol
class Program
{
static void Main(string[]
args)
{
ArbolBinarioBusqueda
arbol = new ArbolBinarioBusqueda();
// Insertar valores
int[] valores = { 50, 30,
70, 20, 40, 60, 80 };
Console.WriteLine("Insertando
valores: ");
foreach (int val in valores)
{
arbol.Insertar(val);
Console.Write(val + "
");
}
Console.WriteLine("\n");
// Recorridos
Console.WriteLine("===
RECORRIDOS ===");
Console.Write("Inorden: "); arbol.Inorden();
Console.Write("Preorden:
"); arbol.Preorden();
Console.Write("Postorden:");
arbol.Postorden();
// Búsquedas
Console.WriteLine("\n===
BÚSQUEDAS ===");
Console.WriteLine("Buscar
40: " + (arbol.Buscar(40) ? "ENCONTRADO" : "NO
ENCONTRADO"));
Console.WriteLine("Buscar
90: " + (arbol.Buscar(90) ? "ENCONTRADO" : "NO
ENCONTRADO"));
// Altura
Console.WriteLine("\nAltura
del árbol: " + arbol.Altura());
// Eliminar nodo
Console.WriteLine("\nEliminando
nodo 20...");
arbol.Eliminar(20);
Console.Write("Nuevo
Inorden: "); arbol.Inorden();
Console.ReadKey(); //
Pausa para ver resultados;
}
}
}
No hay comentarios.:
Publicar un comentario