/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package proyectoarbolesl;
import java.util.Scanner;
/**
*
* @author ElmerG
*/
public class ProyectoArboles {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int op, x = 0;
int n;
Scanner entrada = new Scanner(System.in);
ArbolBB abb = new ArbolBB();
do {
System.out.println("Menu Arboles");
System.out.println("[1] Insertar Arbol");
System.out.println("[2] Pre Orden");
System.out.println("[3] En Orden");
System.out.println("[4] Post Orden");
System.out.println("[5] Eliminar");
System.out.println("[6] Numero de nodos");
System.out.println("[7] altura del Arbol");
System.out.println("[8] Maximo del arbol");
System.out.println("[9] Minimo del arbol");
System.out.println("[10] Contar por la derecha:");
System.out.println("[11] Mayor elemento por dos metodos:");
System.out.println("[12] Camino para llegar a un nodo determinado:");
System.out.println("[13] Busqueda del valor y decir cuantos elementos se recorrio:");
System.out.println("[14] Cuál es la diferencia entre el mayor y menor elemento de un árbol:");
System.out.println("[15] Cuál es el segundo elemento menor de un árbol tipo ABB:");
System.out.println("[16] Muestre todas las hojas terminales:");
System.out.println("[17] Dado un ABB, cree una copia de él:");
System.out.println("[18] Lea 2 árboles ¿Que elementos del primer árbol no se encuentran en el segundo árbol:");
System.out.println("[19] En un arbolBB elimine el menor elemento iterativamente:");
System.out.println("[20] En un árbol binario Cuantos nodos tienen un solo hijo:");
System.out.println("[21] Lista enlazada para contruir un arbol:");
System.out.println("[22] Orden de un arbolBB ascendentemente:");
System.out.println("[23] Salir");
System.out.print("Ingrese opcion : ");
op = entrada.nextInt();
switch (op) {
case 1:
System.out.println("cuantos elementos desea ingresar:");
n = entrada.nextInt();
for (int i = 0; i < n; i++) {
System.out.print(" Ingrese numero " + i + " : =");
x = entrada.nextInt();
abb.inserta(x);
}
break;
case 2:
System.out.println(" Pre Orden");
abb.preOrden();
break;
case 3:
System.out.println(" En Orden");
abb.enOrden();
break;
case 4:
System.out.println(" Post Orden");
abb.postOrden();
break;
case 5:
System.out.print(" Ingrese numero a eliminar: ");
x = entrada.nextInt();
abb.elimina(x);
break;
case 6:
System.out.println(" El numero de nodos del arbol" + abb.contar());
break;
case 7:
System.out.println(" La altura del arbol es : " + abb.alturaArbol());
break;
case 8:
System.out.println(" Maximo elemento" + abb.buscarMax());
break;
case 9:
System.out.println(" Minimo elemento" + abb.buscarMin());
break;
case 10:
System.out.println("Total elementos a la derecha es: " + abb.totalElmentosDe());
break;
case 11:
System.out.println("El mayor de los nodos es " + abb.buscarMayorInteractivamente());
break;
case 12:
System.out.println("ingrese numero: ");
int p = entrada.nextInt();
if(abb.buscarNumero(x)){
System.out.println("El camino es");
abb.caminoSeguir(p);
}
else
{
System.out.println("El numero no existe");
}
break;
case 13:
System.out.println("Ingrese un numero ");
int numero = entrada.nextInt();
if (abb.buscarNumero(numero)) {
System.out.println("Total de elemtos para llegar al valor es " + abb.totalElementos(numero));
} else {
System.out.println("El numero no existe");
}
break;
case 14:
System.out.println("la diferencia entre mayor y menor es:" + abb.diferenciaMayorMenor());
break;
case 15:
if (abb.esVacio()) {
System.out.println("No existe numeros que mostrar:");
} else {
System.out.println(" segundo elemto menor es: " + abb.segundoElementoMenor());
}
break;
case 16:
System.out.println("Monstrando hojas termianles:");
abb.NodoHojasTerminales();
break;
case 17:
System.out.println("la copia es:");
abb.copiarArbol();
break;
case 18:
break;
case 19:
System.out.println("Borrado el menor");
abb.borarMenor();
break;
case 20:
System.out.println("Nodos con un solo hijo son:");
System.out.println("total de nodos con un solo hijo:" + abb.NodoConSoloHijo());
break;
case 21:
break;
case 22:
System.out.println(" orden descendentemente es:");
abb.ordenDescendente();
break;
default:
System.out.println("opccion incorrecta:");
break;
}
} while (op != 23);
}
}
NODO
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package proyectoarbolesl;
/**
*
* @author ElmerG
*/
class NodoArbol {
int info;
NodoArbol hi;
NodoArbol hd;
public NodoArbol() {
}
public NodoArbol(int x) {
info = x;
hi = null;
hd = null;
}
public NodoArbol(int info, NodoArbol hi, NodoArbol hd) {
this.info = info;
this.hi = hi;
this.hd = hd;
}
public int getInfo() {
return info;
}
public void setInfo(int info) {
this.info = info;
}
public NodoArbol getHi() {
return hi;
}
public void setHi(NodoArbol hi) {
this.hi = hi;
}
public NodoArbol getHd() {
return hd;
}
public void setHd(NodoArbol hd) {
this.hd = hd;
}
}
CLASE ARBOLAA
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package proyectoarbolesl;
/**
*
* @author ElmerG
*/
class ArbolBB {
private NodoArbol raiz;
int cont;
public ArbolBB() {
raiz = null;
}
public boolean esVacio() {
return raiz == null;
}
//INSERTAR ARBOL
public void inserta(int x) {
raiz = inserta(x, raiz);
}
private NodoArbol inserta(int x, NodoArbol r) {
if (r == null) {
r = new NodoArbol(x);
} else if (x < r.getInfo()) {
r.setHi(inserta(x, r.getHi()));
} else if (x > r.getInfo()) {
r.setHd(inserta(x, r.getHd()));
}
return r;
}
//EN ORDEN
public void enOrden() {
enOrden(raiz);
System.out.println();
}
private void enOrden(NodoArbol r) {
if (r != null) {
enOrden(r.getHi());
System.out.print(r.getInfo() + " ");
enOrden(r.getHd());
}
}
//EN POSTORDEN
public void postOrden() {
postOrden(raiz);
System.out.println();
}
private void postOrden(NodoArbol r) {
if (r != null) {
postOrden(r.getHi());
postOrden(r.getHd());
System.out.print(r.getInfo() + " ");
}
}
//EN PREORDEN
public void preOrden() {
preOrden(raiz);
System.out.println();
}
private void preOrden(NodoArbol r) {
if (r != null) {
System.out.print(r.getInfo() + " ");
preOrden(r.getHi());
preOrden(r.getHd());
}
}
//BUSCAR MAXIMO
public int buscarMax() {
return buscarMax(raiz);
}
private int buscarMax(NodoArbol r) {
int x;
if (r.getHd() == null) {
x = r.getInfo();
} else {
x = buscarMax(r.getHd());
}
return x;
}
//BUSCAR MINIMO
public int buscarMin() {
return buscarMin(raiz);
}
private int buscarMin(NodoArbol r) {
int x;
if (r.getHi() == null) {
x = r.getInfo();
} else {
x = buscarMin(r.getHi());
}
return x;
}
//CONTAR
public int contar() {
return contar(raiz);
}
private int contar(NodoArbol r) {
if (r == null) {
return 0;
} else {
return 1 + contar(r.getHi()) + contar(r.getHd());
}
}
//VEIFICAR UN NUMERO
public boolean buscarNumero(int x) {
if (buscarNumero(x, raiz)) {
return true;
} else {
return false;
}
}
private boolean buscarNumero(int x, NodoArbol r) {
boolean verifica = false;
NodoArbol nuevo = new NodoArbol(x);
if (r != null) {
if (nuevo.getInfo() == r.getInfo()) {
verifica = true;
} else {
if (nuevo.getInfo() > r.getInfo()) {
verifica = buscarNumero(x, r.getHd());
} else {
verifica = buscarNumero(x, r.getHi());
}
}
}
return verifica;
}
// 1. En un ABB ¿Cuantos elementos hay en la derecha de un nodo determinado?
public int totalElmentosDe() {
return cuantosElementos(raiz);
}
private int cuantosElementos(NodoArbol r) {
if (r == null) {
return 0;
} else {
return 1 + contar(r.getHd());
}
}
// ejercicio 2 Buscando el mayor iterativamente solamente por el lado correcto
public int buscarMayorInteractivamente() {
return buscarMayorInterractivamente(raiz);
}
private int buscarMayorInterractivamente(NodoArbol r) {
int mayor = 0;
if (r != null) {
if (r.getHd() == null) {
mayor = r.getInfo();
} else {
mayor = buscarMayorInterractivamente(r.getHd());
}
}
return mayor;
}
// 3.En un ABB muestre el camino que se debe seguir para llegar a un nodo determinado.
public void caminoSeguir(int x) {
caminoSeguir(x, raiz);
System.out.println();
}
private void caminoSeguir(int x, NodoArbol r) {
if (x != r.getInfo()) {
System.out.println(r.getInfo());
if (x < r.getInfo()) {
caminoSeguir(x, r.getHi());
} else {
caminoSeguir(x, r.getHd());
}
}
}
// 4. En un ABB, busque un valor y diga cuantos elementos se recorrieron
//para llegar a dicho valor. Este valor es conocido como longitud del camino
public int totalElementos(int x) {
return totalElementos(x, raiz);
}
private int totalElementos(int x, NodoArbol r) {
int contador = 0;
if (x != r.getInfo()) {
contador = 1;
if (x < r.getInfo()) {
contador = 1 + totalElementos(x, r.getHi());
} else {
contador = 1 + totalElementos(x, r.getHd());
}
}
return contador;
}
//5. ¿Cuál es la diferencia entre el mayor y menor elemento de un árbol?
public int diferenciaMayorMenor() {
return diferenciaMayorMenor(raiz);
}
private int diferenciaMayorMenor(NodoArbol r) {
int maximo;
int minimo;
maximo = buscarMax();
minimo = buscarMin();
return maximo - minimo;
}
//6. ¿Cuál es el segundo elemento menor de un árbol tipo ABB?
public int segundoElementoMenor() {
return segundoElementoMenor(raiz);
}
private int segundoElementoMenor(NodoArbol r) {
int x = 0, y = 0;
NodoArbol aux = r.getHi();
if (r != null) {
if (aux.getHi() == null) {
x = aux.getHd().getInfo();
} else if (aux.getHd() == null) {
x = aux.getInfo();
} else {
x = segundoElementoMenor(r.getHi());
}
}
return x;
}
/*
public int segundoElementoMeno() {
return segundoElementoMeno(raiz);
}
private int segundoElementoMeno(NodoArbol r) {
int x = 0, y = 0;
NodoArbol aux = r.getHi();
if (r != null) {
if (aux.getHi().getInfo() <r.getInfo()) {
x = aux.getInfo();
} else if (aux.getHd().getInfo()>r.getInfo()) {
x = aux.getInfo();
} else {
x = segundoElementoMenor(r.getHi());
}
}
return x;
}*/
/*7. Muestre todas las hojas terminales (también llamados elementos de la frontera
del árbol en un ABB, Sugerencia: recorra el árbol y cuando no tenga
a donde ir (izquierda y derecha apuntan a NULL) imprima su valor.*/
public void NodoHojasTerminales() {
cont = 0;
NodoHojasTerminales(raiz);
System.out.println();
}
private void NodoHojasTerminales(NodoArbol recorrido) {
if (recorrido != null) {
if (recorrido.getHi() == null && recorrido.getHd() == null) {
System.out.println(recorrido.getInfo());
}
NodoHojasTerminales(recorrido.getHi());
NodoHojasTerminales(recorrido.getHd());
}
}
//8. Dado un ABB, cree una copia de él.
public ArbolBB copiarArbol() {
ArbolBB copia = null;
if (esVacio()) {
System.out.print("El arbol esta vacio:");
} else {
copia = this.copiarArbol(raiz);
}
return copia;
}
private ArbolBB copiarArbol(NodoArbol temp) {
NodoArbol tempCopia;
if (temp == null) {
tempCopia = null;
} else {
ArbolBB hiCopia, hdCopia;
hiCopia = copiarArbol(temp.hi);
hdCopia = copiarArbol(temp.hd);
tempCopia = new NodoArbol(temp.info);
tempCopia.hi = hiCopia.raiz;
tempCopia.hd = hdCopia.raiz;
System.out.print(tempCopia.getInfo());
}
ArbolBB copia = new ArbolBB();
copia.raiz = tempCopia;
return copia;
}
//9. Lea 2 árboles ¿Que elementos del primer árbol no se encuentran en el segundo árbol?
//10. En un arbolBB elimine el menor elemento iterativamente.
public void borarMenor() {
if (raiz != null) {
if (raiz.hi == null) {
raiz = raiz.hd;
} else {
NodoArbol atras = raiz;
NodoArbol reco = raiz.hi;
while (reco.hi != null) {
atras = reco;
reco = reco.hi;
}
System.out.println("El numero borrado es:" + reco.info);
atras.hi = reco.hd;
}
}
}
//11. ¿En un árbol binario Cuantos nodos tienen un solo hijo?
private void NodoConSoloHijo(NodoArbol reco) {
if (reco != null) {
if (reco.getHd() == null && reco.getHi() != null) {
System.out.println(reco.getInfo());
cont++;
} else if (reco.getHi() == null && reco.getHd() != null) {
System.out.println(reco.getInfo());
cont++;
}
NodoConSoloHijo(reco.getHi());
NodoConSoloHijo(reco.getHd());
}
}
public int NodoConSoloHijo() {
cont = 0;
NodoConSoloHijo(raiz);
return cont;
}
//12. Se tiene una lista enlazada se pide construir un árbol a partir de esta
//lista luego recorra el árbol y reporte cuantas veces se repite cada elemento.
//13. Muestre los elementos de un árbol binario de búsqueda ordenados descendentemente.
public void ordenDescendente() {
if (esVacio()) {
System.out.println("El arbo esta vacio");
} else {
ordenDescendente(raiz);
}
}
private void ordenDescendente(NodoArbol r) {
if (r != null) {
ordenDescendente(r.getHd());
System.out.println(r.getInfo());
ordenDescendente(r.getHi());
}
}
public void eliminaMin() {
raiz = eliminaMin(raiz);
}
private NodoArbol eliminaMin(NodoArbol r) {
if (r.getHi() == null) {
r = r.getHd();
} else {
r.setHi(eliminaMin(r.getHi()));
}
return r;
}
public void elimina(int x) {
raiz = elimina(x, raiz);
}
private NodoArbol elimina(int x, NodoArbol r) {
if (r != null) {
if (x < r.getInfo()) {
r.setHi(elimina(x, r.getHi()));
} else if (x > r.getInfo()) {
r.setHd(elimina(x, r.getHd()));
} else if (r.getHi() == null) {
r = r.getHd();
} else if (r.getHd() == null) {
r = r.getHi();
} else {
r.setInfo(buscarMin(r.getHd()));
r.setHd(eliminaMin(r.getHd()));
}
}
return r;
}
public int alturaArbol() {
return alturaArbol(raiz);
}
private int alturaArbol(NodoArbol r) {
int ahi, ahd;
if (r == null) {
return -1;
} else {
ahi = 1 + alturaArbol(r.getHi());
ahd = 1 + alturaArbol(r.getHd());
if (ahi > ahd) {
return ahi;
} else {
return ahd;
}
}
}
}
No hay comentarios.:
Publicar un comentario