using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Configuration;
using System.Data;
using System.Data.OleDb;
namespace ArbolBinario
{
class Program
{
static void Main(string[] args)
{
OleDbConnection MyConnection = new OleDbConnection(ConfigurationManager.AppSettings["AccessConnection"].ToString());
string x = string.Empty;
string value= string.Empty;
string[] List = new string[6];
do
{
Console.Write("\n\nMenú \n 1)Mostrar árbol binario \n 2)Creación de nodos \n 3)Eliminación de nodo \n 4)Mostrar Recorridos \n 0)Salir \n\n");
x = Console.ReadLine();
switch (x)
{
case "1":
ShowBinaryTree(MyConnection);
break;
case "2":
int NumberOfNodes = NumberOfNodesBinaryTree(MyConnection);
if (NumberOfNodes == 0)
{
Console.Write("\n\nCreación de nodo raíz \n Escriba el valor que va a contener raiz:");
value= Console.ReadLine();
while (string.IsNullOrEmpty(value))
{
Console.Write("Ingrese un valor válido:");
value = Console.ReadLine();
}
if (InsertNewNodeBinaryTree(value.ToUpper(), 0, 0, 1,0, MyConnection) > 0)
{
Console.Write("\n\n Nodo raíz creado");
}
else
{
Console.Write("\n\n Error!!");
}
}
else if (NumberOfNodes > 0)
{
Console.Write("\n\nCreación de nodo hijo \n Escriba el número del nodo al que le quiere agregar un hijo:");
value = Console.ReadLine();
while (string.IsNullOrEmpty(value) || isIntNumber(value) == false || NodeExistBinaryTree(int.Parse(value), MyConnection)==false)
{
Console.Write("Id de nodo inexistente:");
value = Console.ReadLine();
}
List = getNodeBinaryTree(int.Parse(value),MyConnection);
SelectTypeInsertNewNodeBinaryTree(List, MyConnection);
}
else
{
Console.Write("\n\n Error!!");
}
break;
case "3":
Console.Write("\n\nEliminación de nodo \n Escriba el número del nodo que desea eliminar:");
value = Console.ReadLine();
while (string.IsNullOrEmpty(value) || isIntNumber(value) == false || NodeExistBinaryTree(int.Parse(value), MyConnection) == false)
{
Console.Write("Id de nodo inexistente:");
value = Console.ReadLine();
}
List = getNodeBinaryTree(int.Parse(value), MyConnection);
if (List[2].Equals("0") && List[3].Equals("0"))
{
DeleteNodeOrTree(int.Parse(List[0]), int.Parse(List[5]), MyConnection);
}
else
{
Console.Write("\n Imposible eliminar un nodo con hijos!! \n");
}
break;
case "4":
List = getRootNodeBinaryTree(MyConnection);
if (List != null)
{
Console.Write("\n PreOrden: ");
PreOrden(int.Parse(List[0]), MyConnection);
Console.Write("\n InOrden: ");
InOrden(int.Parse(List[0]), MyConnection);
Console.Write("\n PostOrden: ");
PostOrden(int.Parse(List[0]), MyConnection);
}
else
{
Console.Write("\n No hay nodos!! \n ");
}
break;
default:
if (!x.Equals("0")) { Console.Write("Opción invalida!! \n"); }
break;
}
} while (!x.Equals("0"));
}
public static void SelectTypeInsertNewNodeBinaryTree(string[] _list, OleDbConnection _myConnection)
{
string value=string.Empty;
string valueNode = string.Empty;
int level=0;
int identity = 0;
int fl = 0;
if (!_list[2].Equals("0") && !_list[3].Equals("0"))
{
Console.Write("\n\n El nodo " + _list[0] + " ya tiene Hijo Izquierdo e Hijo Derecho");
fl = 0;
}
else if (_list[2].Equals("0") && _list[3].Equals("0"))
{
Console.Write("\n\n Seleccionó el nodo " + _list[0] + " Seleccione nodo a agregar...\n 1) Hijo izquierdo \n 2) Hijo derecho \n 3) Ir al menú superior \n");
value = Console.ReadLine();
while (string.IsNullOrEmpty(value) || (!value.Equals("1") && !value.Equals("2") && !value.Equals("3")))
{
Console.Write("Ingrese un valor válido:");
value = Console.ReadLine();
}
fl = 1;
}
else if (!_list[2].Equals("0") && _list[3].Equals("0"))
{
Console.Write("\n\n Seleccionó el nodo " + _list[0] + " Seleccione nodo a agregar...\n 1) Hijo derecho \n 2) Ir al menú superior \n");
value = Console.ReadLine();
while (string.IsNullOrEmpty(value) || (!value.Equals("1") && !value.Equals("2")))
{
Console.Write("Ingrese un valor válido:");
value = Console.ReadLine();
}
fl = 2;
}
else if (_list[2].Equals("0") && !_list[3].Equals("0"))
{
Console.Write("\n\n Seleccionó el nodo " + _list[0] + " Seleccione nodo a agregar...\n 1) Hijo izquierdo \n 2) Ir al menú superior \n");
value = Console.ReadLine();
while (string.IsNullOrEmpty(value) || (!value.Equals("1") && !value.Equals("2")))
{
Console.Write("Ingrese un valor válido:");
value = Console.ReadLine();
}
fl = 3;
}
switch (fl)
{
case 1:
if (value.Equals("1") || value.Equals("2"))
{
Console.Write("\n Escriba el valor que va a contener el nodo:");
valueNode = Console.ReadLine();
while (string.IsNullOrEmpty(valueNode))
{
Console.Write("Ingrese un valor válido:");
valueNode = Console.ReadLine();
}
level = int.Parse(_list[4]) + 1;
identity = InsertNewNodeBinaryTree(valueNode.ToUpper(), 0, 0, level, int.Parse(_list[0]), _myConnection);
if (value.Equals("1"))
{
updateNodeBinaryTree(int.Parse(_list[0]), identity, "left", _myConnection);
}
else
{
updateNodeBinaryTree(int.Parse(_list[0]), identity, "right", _myConnection);
}
}
break;
case 2:
if (value.Equals("1"))
{
Console.Write("\n Escriba el valor que va a contener el nodo:");
valueNode = Console.ReadLine();
while (string.IsNullOrEmpty(valueNode))
{
Console.Write("Ingrese un valor válido:");
valueNode = Console.ReadLine();
}
level = int.Parse(_list[4]) + 1;
identity = InsertNewNodeBinaryTree(valueNode.ToUpper(), 0, 0, level, int.Parse(_list[0]), _myConnection);
updateNodeBinaryTree(int.Parse(_list[0]), identity, "right", _myConnection);
}
break;
case 3:
if (value.Equals("1"))
{
Console.Write("\n Escriba el valor que va a contener el nodo:");
valueNode = Console.ReadLine();
while (string.IsNullOrEmpty(valueNode))
{
Console.Write("Ingrese un valor válido:");
valueNode = Console.ReadLine();
}
level = int.Parse(_list[4]) + 1;
identity = InsertNewNodeBinaryTree(valueNode.ToUpper(), 0, 0, level, int.Parse(_list[0]), _myConnection);
updateNodeBinaryTree(int.Parse(_list[0]), identity, "left", _myConnection);
}
break;
default:
break;
}
}
public static int updateNodeBinaryTree(int _idNodeFather, int _idNodeChild, string _type, OleDbConnection _myConnection)
{
string Query = string.Empty;
int flag;
try
{
if (_type.Equals("left"))
{ Query = "update Arbol set HijoIzquierdo="+_idNodeChild+" where Id="+_idNodeFather; }
else { Query = "update Arbol set HijoDerecho=" + _idNodeChild + " where Id=" + _idNodeFather; }
OleDbCommand CommandQuery = new OleDbCommand(Query, _myConnection);
OleDbDataAdapter update = new OleDbDataAdapter();
_myConnection.Open();
update.UpdateCommand = CommandQuery;
update.UpdateCommand.ExecuteNonQuery();
_myConnection.Close();
flag = 1;
}
catch { flag = 0; _myConnection.Close(); }
return flag;
}
public static int DeleteNodeOrTree(int _idNode, int _idFatherNode, OleDbConnection _myConnection)
{
string Query = string.Empty;
string[] List = null;
int flag;
try
{
List = getNodeBinaryTree(_idFatherNode, _myConnection);
if (_idNode.Equals("-1")) { Query = "delete from Arbol"; } else { Query = "delete from Arbol where Id=" + _idNode; }
OleDbCommand CommandQuery = new OleDbCommand(Query, _myConnection);
OleDbDataAdapter delete = new OleDbDataAdapter();
_myConnection.Open();
delete.DeleteCommand = CommandQuery;
delete.DeleteCommand.ExecuteNonQuery();
_myConnection.Close();
if (List != null)
{
if (List[2].Equals(_idNode.ToString()) && !List[3].Equals(_idNode.ToString()))
{
Query = "update Arbol set HijoIzquierdo=0 where Id=" + _idFatherNode;
}
else if (!List[2].Equals(_idNode.ToString()) && List[3].Equals(_idNode.ToString()))
{
Query = "update Arbol set HijoDerecho=0 where Id=" + _idFatherNode;
}
OleDbCommand CommandQueryUpdate = new OleDbCommand(Query, _myConnection);
OleDbDataAdapter update = new OleDbDataAdapter();
_myConnection.Open();
update.UpdateCommand = CommandQueryUpdate;
update.UpdateCommand.ExecuteNonQuery();
_myConnection.Close();
}
flag = 1;
}
catch { flag = 0; _myConnection.Close(); }
return flag;
}
public static int InsertNewNodeBinaryTree(string _value, int _leftChild, int _rightChild, int _level, int _father, OleDbConnection _myConnection)
{
string Query = "insert into Arbol (Valor,HijoIzquierdo,HijoDerecho,Nivel,Padre) values ('" + _value + "'," + _leftChild + "," + _rightChild + "," + _level + "," + _father + ")";
int flag=0;
try
{
OleDbCommand CommandQuery = new OleDbCommand(Query, _myConnection);
OleDbDataAdapter add = new OleDbDataAdapter();
_myConnection.Open();
add.InsertCommand = CommandQuery;
add.InsertCommand.ExecuteNonQuery();
Query="Select @@Identity";
OleDbCommand CommandQueryIdentity = new OleDbCommand(Query, _myConnection);
OleDbDataAdapter select = new OleDbDataAdapter();
select.SelectCommand = CommandQueryIdentity;
flag = int.Parse(select.SelectCommand.ExecuteScalar().ToString());
_myConnection.Close();
}
catch { flag = 0; _myConnection.Close(); }
return flag;
}
public static void ShowBinaryTree(OleDbConnection _myConnection)
{
string Query = "Select * from Arbol order by nivel asc, id asc";
try
{
OleDbDataAdapter MyAdapter = new OleDbDataAdapter(Query, _myConnection);
DataSet MyDataSet = new DataSet();
_myConnection.Open();
MyAdapter.Fill(MyDataSet);
if (MyDataSet.Tables[0].Rows.Count > 0)
{
Console.Write("\nId \t Valor \t Hijo Izquierdo \t Hijo Derecho \t Padre \t Nivel\n");
for (int i = 0; i < MyDataSet.Tables[0].Rows.Count; i++)
{
DataRow field = MyDataSet.Tables[0].Rows[i];
Console.Write(field["Id"].ToString() + "\t " + field["Valor"].ToString() + "\t\t" + field["HijoIzquierdo"].ToString() + "\t\t\t" + field["HijoDerecho"].ToString() + "\t " + field["Padre"].ToString() + "\t " + field["Nivel"].ToString() + "\n");
}
}
else
{
Console.Write("\n No hay nodos creados.\n");
}
_myConnection.Close();
}
catch { _myConnection.Close(); }
}
public static int NumberOfNodesBinaryTree(OleDbConnection _myConnection)
{
string Query = "select count(*) as total from Arbol";
int NumberOfNodes = -1;
try
{
OleDbDataAdapter MyAdapter = new OleDbDataAdapter(Query, _myConnection);
DataSet MyDataSet = new DataSet();
_myConnection.Open();
MyAdapter.Fill(MyDataSet);
DataRow field = MyDataSet.Tables[0].Rows[0];
NumberOfNodes = int.Parse(field["total"].ToString());
_myConnection.Close();
}
catch { NumberOfNodes = -1; _myConnection.Close(); }
return NumberOfNodes;
}
public static bool NodeExistBinaryTree(int _idNode, OleDbConnection _myConnection)
{
string Query = "select count(*) as total from Arbol where Id="+_idNode;
bool fl= false;
int NumberOfNodes = 0;
try
{
OleDbDataAdapter MyAdapter = new OleDbDataAdapter(Query, _myConnection);
DataSet MyDataSet = new DataSet();
_myConnection.Open();
MyAdapter.Fill(MyDataSet);
DataRow field = MyDataSet.Tables[0].Rows[0];
NumberOfNodes = int.Parse(field["total"].ToString());
_myConnection.Close();
if (NumberOfNodes == 1) { fl = true; }
}
catch { fl=false; _myConnection.Close(); }
return fl;
}
public static string[] getNodeBinaryTree(int _idNode, OleDbConnection _myConnection)
{
string Query = "Select * from Arbol where Id="+_idNode;
string[] List = null;
try
{
OleDbDataAdapter MyAdapter = new OleDbDataAdapter(Query, _myConnection);
DataSet MyDataSet = new DataSet();
_myConnection.Open();
MyAdapter.Fill(MyDataSet);
if (MyDataSet.Tables[0].Rows.Count == 1)
{
DataRow field = MyDataSet.Tables[0].Rows[0];
List = new string[6];
List[0] = field["Id"].ToString();
List[1] = field["Valor"].ToString();
List[2] = field["HijoIzquierdo"].ToString();
List[3] = field["HijoDerecho"].ToString();
List[4] = field["Nivel"].ToString();
List[5] = field["Padre"].ToString();
}
_myConnection.Close();
}
catch { List = null; _myConnection.Close(); }
return List;
}
public static string[] getRootNodeBinaryTree( OleDbConnection _myConnection)
{
string Query = "Select * from Arbol where Padre=0";
string[] List = null;
try
{
OleDbDataAdapter MyAdapter = new OleDbDataAdapter(Query, _myConnection);
DataSet MyDataSet = new DataSet();
_myConnection.Open();
MyAdapter.Fill(MyDataSet);
if (MyDataSet.Tables[0].Rows.Count == 1)
{
DataRow field = MyDataSet.Tables[0].Rows[0];
List = new string[6];
List[0] = field["Id"].ToString();
List[1] = field["Valor"].ToString();
List[2] = field["HijoIzquierdo"].ToString();
List[3] = field["HijoDerecho"].ToString();
List[4] = field["Nivel"].ToString();
List[5] = field["Padre"].ToString();
}
_myConnection.Close();
}
catch { List = null; _myConnection.Close(); }
return List;
}
public static bool isIntNumber(string _numberText)
{
int Result = 0;
bool numberResult = false;
if (int.TryParse(_numberText, out Result))
{
numberResult = true;
}
return numberResult;
}
public static void PreOrden(int _idNode, OleDbConnection _myConnection)
{
string[] List = null;
if (NodeExistBinaryTree(_idNode, _myConnection))
{
List = getNodeBinaryTree(_idNode, _myConnection);
Console.Write(List[1]);
PreOrden(int.Parse(List[2]), _myConnection);
PreOrden(int.Parse(List[3]), _myConnection);
}
}
public static void InOrden(int _idNode, OleDbConnection _myConnection)
{
string[] List = null;
if (NodeExistBinaryTree(_idNode, _myConnection))
{
List = getNodeBinaryTree(_idNode, _myConnection);
InOrden(int.Parse(List[2]), _myConnection);
Console.Write(List[1]);
InOrden(int.Parse(List[3]), _myConnection);
}
}
public static void PostOrden(int _idNode, OleDbConnection _myConnection)
{
string[] List = null;
if (NodeExistBinaryTree(_idNode, _myConnection))
{
List = getNodeBinaryTree(_idNode, _myConnection);
PostOrden(int.Parse(List[2]), _myConnection);
PostOrden(int.Parse(List[3]), _myConnection);
Console.Write(List[1]);
}
}
}
}
No hay comentarios:
Publicar un comentario