Árbol.
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto.
Árbol Binario
Este tipo de árbol permite almacenar información ordenada. Reglas a cumplir:
- Cada nodo del árbol puede tener 0, 1 ó 2 hijos.
- Los descendientes izquierdos deben tener un valor menor al padre.
- Los descendientes derechos deben tener un valor mayor al padre.ones simples. Pero las características que implican no lo son tanto.
Ejemplo código de árbol binario:
using System;
using System.Collections.Generic;
using System.Text;
namespace ArbolBinario
{
class Arbol
{
int info;
Arbol izq, der;
public Arbol raiz = null;
public Arbol()
{
info = 0;
izq = null;
der = null;
}
public void Insertar(int X)
{
Arbol temp= new Arbol();
int bandera = 0;
Arbol hoja = new Arbol();
hoja.info = X;
hoja.izq = null;
hoja.der = null;
if (raiz == null)
raiz = hoja;
else
{
temp = raiz;
while (bandera != 1)
{
if (hoja.info < temp.info)
{
if (temp.izq == null)
{
temp.izq = hoja;
bandera = 1;
}
else
temp = temp.izq;
}
else
{
if (temp.der == null)
{
temp.der = hoja;
bandera = 1;
}
else
temp = temp.der;
}
}
}
}
public void Preorden(Arbol temp)
{
if (temp != null)
{
Console.WriteLine("{0}", temp.info);
if (temp.izq != null)
Preorden(temp.izq);
if (temp.der != null)
Preorden(temp.der);
}
else
Console.WriteLine("El arbol esta vacio.");
}
public void Enorden(Arbol temp)
{
if (temp != null)
{
if (temp.izq != null)
Enorden(temp.izq);
Console.WriteLine("{0}", temp.info);
if (temp.der != null)
Enorden(temp.der);
}
else
Console.WriteLine("El arbol esta vacio.");
}
public void Posorden(Arbol temp)
{
if (temp != null)
{
if (temp.izq != null)
Posorden(temp.izq);
if (temp.der != null)
Posorden(temp.der);
Console.WriteLine("{0}", temp.info);
}
else
Console.WriteLine("El arbol esta vacio.");
}
public void Eliminar()
{
Arbol p, q, r, s, t;
int X;
bool encontrado = false;
p = raiz;
q = null;
if (p != null)
{
Console.WriteLine("Cual nodo deseas eliminar?");
X = int.Parse(Console.ReadLine());
while (p != null && encontrado == false)
{
if (p.info == X)
{
encontrado = true;
Console.WriteLine("El nodo {0} sera eliminado del arbol binario", p.info);
}
else
{
q = p;
if (X < p.info)
p = p.izq;
else
p = p.der;
}
}
if (encontrado == true)
{
if (p.izq == null)
r = p.der;
else
{
if (p.der == null)
r = p.izq;
else
{
t = p;
r = p.der;
s = r.izq;
while (s != null)
{
t = r;
r = s;
s = r.izq;
}
if (t != p)
{
t.izq = r.der;
r.der = p.der;
}
r.izq = p.izq;
}
}
if (q == null)
raiz = r;
else
{
if (p == q.izq)
q.izq = r;
else
q.der = r;
}
}
else
Console.WriteLine("El nodo {0} no esta en el arbol binario",X);
}
else
Console.WriteLine("El arbol binario esta vacio.");
}
public void BusqRecursiva(Arbol temp, int X)
{
if (temp == null)
Console.WriteLine("No esta el nodo {0} en el arbo binario.",X);
else
{
if (X == temp.info)
Console.WriteLine("El nodo {0} si esta en el arbol binario.", X);
else
{
if (X < temp.info)
BusqRecursiva(temp.izq,X);
else
BusqRecursiva(temp.der, X);
}
}
}
public void BusqIterativa(Arbol temp, int X)
{
bool encontrado = false;
while (temp != null && encontrado == false)
{
if (X == temp.info)
encontrado = true;
else
{
if (X < temp.info)
temp = temp.izq;
else
temp = temp.der;
}
}
if (encontrado == false)
Console.WriteLine("El nodo {0} No esta en el arbol binario.", X);
else
Console.WriteLine("El nodo {0} si esta en el arbo binario.",X);
}
}
class Program
{
static void Main(string[] args)
{
Arbol A = new Arbol();
int opcion, X;
do
{
Console.Clear();
Console.WriteLine("Menu\n");
Console.WriteLine("1.- Insertar.");
Console.WriteLine("2.- Recorrido en Preorden");
Console.WriteLine("3.- Recorrido Enorden.");
Console.WriteLine("4.- Recorrido en Posorden.");
Console.WriteLine("5.- Eliminar nodos");
Console.WriteLine("6.- Busqueda recursiva de nodos.");
Console.WriteLine("7.- Busqueda iterativa de nodos.");
Console.WriteLine("8.- Salir.\n");
Console.WriteLine("Que opcion desea realizar?\n");
opcion = int.Parse(Console.ReadLine());
Console.Clear();
switch (opcion)
{
case 1:
Console.Write("Introduzca nuevo valor: ");
X = int.Parse(Console.ReadLine());
A.Insertar(X);
break;
case 2:
A.Preorden(A.raiz);
Console.ReadLine();
Console.Clear();
break;
case 3:
A.Enorden(A.raiz);
Console.ReadLine();
Console.Clear();
break;
case 4:
A.Posorden(A.raiz);
Console.ReadLine();
Console.Clear();
break;
case 5:
A.Eliminar();
Console.ReadLine();
Console.Clear();
break;
case 6:
Console.WriteLine("Que numero desea buscar?");
X = int.Parse(Console.ReadLine());
A.BusqRecursiva(A.raiz, X);
Console.ReadLine();
Console.Clear();
break;
case 7:
Console.WriteLine("Que numero desea buscar?");
X = int.Parse(Console.ReadLine());
A.BusqIterativa(A.raiz, X);
Console.ReadLine();
Console.Clear();
break;
case 8:
break;
default:
Console.WriteLine("Opcion Incorrecta.");
break;
}
} while (opcion != 8);
}
}
}
