Tarea 3 - Algoritmo básico de búsqueda en Java
- En forma individual, investigar e implementar en Java un algoritmo de búsqueda. Se recomienda que desarrolle un programa que permita crear un árbol binario, recorrerlo en diferente orden, y haber búsqueda de un elemento dentro del árbol. También puede usar otra estructura de datos.
- Publicar en su blog y responder esta entrada, indicando su nombre y la url de su tarea en el blog de su grupo.
Para esta tarea se ha desarrollado un árbol de búsqueda binario, el cual es un tipo de datos abstracto ideado para almacenamiento de elementos ordenados y su posterior búsqueda.
Esta implementación contiene los metódos de lookup, insert, printAsc y printDesc para poder saber si un valor se encuentra dentro del árbol, insertar otros, imprimir directamente a terminal tanto de menor a mayor como de mayor a menor.
WARNING: Este programa fue compilado directamente mediante el compilador de java, por lo tanto, para poder usarlo en alguna IDE como NetBeans podría ser necesario agregar algunos detalles como un package o algo similar.
public class TrinaryBee{
public static void main(String[] args){
TrinaryBee arbol = new TrinaryBee();
System.out.println(arbol.insert(5).getMessage());
System.out.println(arbol.insert(2).getMessage());
System.out.println(arbol.insert(8).getMessage());
System.out.println(arbol.insert(7).getMessage());
System.out.println(arbol.insert(3).getMessage());
System.out.println(arbol.lookup(5).getMessage());
System.out.println(arbol.lookup(2).getMessage());
System.out.println(arbol.lookup(7).getMessage());
System.out.println(arbol.lookup(2).getMessage());
System.out.println(arbol.lookup(8).getMessage());
arbol.printAsc();
arbol.printDesc();
}
/**
*I accept nothing as a parameter because
*I don't know what kind of data I'm expected to receive
*/
public TrinaryBee(){
rootNode = null;
}
/**
*I can only insert integer values because I'm just an example
*please extend my functionality if it becomes necessary
*/
public ActionStatus insert(int aValue){
if(rootNode == null)
{
rootNode = new TrinaryBeeNode(aValue);
return new ActionStatus("Insertion -"+"Value "+rootNode.getValue()+" succesfully inserted",true);
}
else
{
TrinaryBeeNode node = rootNode;
while(node != null)
{
if (node.getValue() == aValue)
{
return new ActionStatus("Insertion -"+"Value "+ node.getValue() +" already in tree",false);
}
else if(node.getValue() > aValue)
{
//try to insert left
if(node.getLeftNode() == null)
{
node.setLeftNode( new TrinaryBeeNode(aValue) );
return new ActionStatus("Insertion -"+"Value " + node.getLeftNode().getValue() + " succesfully inserted",true);
}
else
{
node = node.getLeftNode();
}
}
else
{
//try to insert right
if(node.getRightNode() == null)
{
node.setRightNode( new TrinaryBeeNode(aValue) );
return new ActionStatus("Insertion -"+"Value "+node.getRightNode().getValue()+" succesfully inserted",true);
}
else
{
node = node.getRightNode();
}
}
}
}
return new ActionStatus("Insertion -"+"This should never happen", false);
}
public ActionStatus lookup(int value){
//Default will be in-order, because it's cooler
if(rootNode == null){
return new ActionStatus("Lookup -"+"Tree doesn't have a root!", false);
}
if (checkLeftNode(rootNode, value))
return new ActionStatus("Lookup -"+"Value "+value+" found", true);
else
return new ActionStatus("Lookup -"+"Value "+value+" not found", false);
}
public void printDesc(){
TrinaryBeeNode node = rootNode;
if(node.getRightNode() != null )
{
printDesc(node.getRightNode());
}
System.out.print(" " + node.getValue());
if(node.getLeftNode() != null)
{
printDesc(node.getLeftNode());
}
System.out.println("");
return;
}
private void printDesc(TrinaryBeeNode node){
if(node.getRightNode() != null)
{
printDesc(node.getRightNode());
}
System.out.print(" " + node.getValue());
if(node.getLeftNode() != null)
{
printDesc(node.getLeftNode());
}
return;
}
public void printAsc(){
TrinaryBeeNode node = rootNode;
if(node.getLeftNode() != null)
{
printAsc(node.getLeftNode());
}
System.out.print(" " + node.getValue());
if(node.getRightNode() != null )
{
printAsc(node.getRightNode());
}
System.out.println("");
return;
}
private void printAsc(TrinaryBeeNode node){
if(node.getLeftNode() != null)
{
printAsc(node.getLeftNode());
}
System.out.print(" " + node.getValue());
if(node.getRightNode() != null)
{
printAsc(node.getRightNode());
}
return;
}
private boolean checkLeftNode(TrinaryBeeNode node, int value){
boolean st = false;
if(node.getLeftNode() != null)
{
st = checkLeftNode(node.getLeftNode(), value);
}
if(node.getValue() == value)
{
return true;
}
if(node.getRightNode() != null && !st)
{
st = checkLeftNode(node.getRightNode(), value);
}
return st;
}
private void setRoot(TrinaryBeeNode node){
rootNode = node;
}
private TrinaryBeeNode rootNode;
private class ActionStatus{
public ActionStatus(String aMessage, boolean success, int aValue){
message = aMessage;
status = success;
value = aValue;
}
public ActionStatus(String aMessage, boolean success){
message = aMessage;
status = success;
value = 0;
}
public String getMessage(){
return message;
}
public boolean isSuccess(){
return status;
}
public int getValue(){
return value;
}
private String message;
private boolean status;
private int value;
}
private class TrinaryBeeNode{
public TrinaryBeeNode(int aValue){
this.value = aValue;
leftNode = null;
rightNode = null;
}
public int getValue(){
return value;
}
public void setValue(int aValue){
value = aValue;
}
public void setLeftNode(TrinaryBeeNode aNode){
leftNode = aNode;
}
public void setRightNode(TrinaryBeeNode aNode){
rightNode = aNode;
}
public TrinaryBeeNode getLeftNode(){
return leftNode;
}
public TrinaryBeeNode getRightNode(){
return rightNode;
}
public void unsetLeftNode(){
leftNode = null;
}
public void unsetRightNode(){
rightNode = null;
}
private int value;
private TrinaryBeeNode leftNode;
private TrinaryBeeNode rightNode;
}
}
