Estructura de Datos
Enviado por Dietzzel • 20 de Enero de 2021 • Apuntes • 8.225 Palabras (33 Páginas) • 79 Visitas
public class ABB {
NodoABB root;
/***************************************************************************/
/******************************* INSERTAR **********************************/
public void insertar(int key) {
root = insertarR(key, root);
}
private NodoABB insertarR(int key, NodoABB nodo) {
if (nodo == null) {
return new NodoABB(key);
}
//Navega por el arbol dependiendo del valor de key
if (key < nodo.key) {
nodo.leftChild = insertarR(key, nodo.leftChild);
} else if(key > nodo.key){
nodo.rightChild = insertarR(key, nodo.rightChild);
}
return nodo;
}
/***************************************************************************/
/******************************* ELIMINAR **********************************/
public void eliminar(int key) {
root = borrar(root, key);
}
private NodoABB borrar(NodoABB nodo, int key) {
if (nodo == null){
System.out.println("Llave no encontrada");
return nodo;
}
if (key < nodo.key){
nodo.leftChild = borrar(nodo.leftChild, key);
}else if (key > nodo.key){
nodo.rightChild = borrar(nodo.rightChild, key);
}else {
if (nodo.leftChild == null && nodo.rightChild == null) {
nodo = null;
} else if (nodo.rightChild == null) {
NodoABB aux = nodo.leftChild;
while (aux.leftChild != null) {
aux = aux.leftChild;
}
int valor = aux.key;
borrar(root, valor);
nodo.key = valor;
} else {
NodoABB aux = nodo.rightChild;
while (aux.leftChild != null) {
aux = aux.leftChild;
}
int valor = aux.key;
borrar(root, valor);
nodo.key = valor;
}
}
return nodo;
}
/***************************************************************************/
/*************************** MENOR A MAYOR *********************************/
public void mostrarMenorAMayor() {
menorAMayor(root);
}
private void menorAMayor(NodoABB focusNode) {
if (focusNode != null) {
menorAMayor(focusNode.leftChild);
System.out.print(focusNode);
menorAMayor(focusNode.rightChild);
}
}
/***************************************************************************/
/*************************** MAYOR A MENOR *********************************/
public void mostrarMayorAMenor() {
mayorAMenor(root);
}
private void mayorAMenor(NodoABB focusNode) {
if (focusNode != null) {
mayorAMenor(focusNode.rightChild);
System.out.print(focusNode);
mayorAMenor(focusNode.leftChild);
}
}
/***************************************************************************/
/******************************* POST ORDER ********************************/
public void mostrarPostOrder() {
postOrder(root);
}
public void postOrder(NodoABB focusNode) {
if (focusNode != null) {
postOrder(focusNode.leftChild);
postOrder(focusNode.rightChild);
System.out.print(focusNode);
}
}
/***************************************************************************/
/******************************* BUSCAR ************************************/
public NodoABB buscarElemento(int key) {
NodoABB nodoActual = root;
while (nodoActual.key != key) {
if (key < nodoActual.key) {
nodoActual = nodoActual.leftChild;
} else {
nodoActual = nodoActual.rightChild;
}
if (nodoActual == null) {
return null;
}
}
return nodoActual;
}
/***************************************************************************/
/******************************* BUSCAR MIN ********************************/
//Busca el valor minimo dado un nodo
public int buscarMin(NodoABB nodoActual) {
int min = 0;
if (nodoActual.leftChild != null) {
min = buscarMin(nodoActual.leftChild);
return min;
} else {
min = nodoActual.key;
return min;
}
}
//Busca el valor minimo del arbol
public int buscarMin() {
return buscarMin(this.root);
}
/***************************************************************************/
/************************** MOSTRAR ARBOL **********************************/
public void mostrarArbol() {
showTree(root, 0);
}
private void showTree(NodoABB nodo, int depth) {
if (nodo.rightChild != null) {
showTree(nodo.rightChild, depth+1);
}
for (int i = 0; i < depth; i++) {
System.out.print(" ");
}
System.out.println("("+nodo.key+")");
if (nodo.leftChild != null) {
showTree(nodo.leftChild, depth+1);
}
}
}
public class ABB {
NodoABB root;
/***************************************************************************/
/******************************* INSERTAR **********************************/
public void insertar(int key) {
root = insertarR(key,
...