Hola a todos, hoy os dejo una serie de ejercicios de Java para practicar todo aquello que hemos explicado en anteriores posts.
Todos los ejercicios que proponemos están resueltos en este mismo post, intenta hacerlo por ti mismo y si te quedas atascado puedes mirar la solución. Recuerda, que no tiene por que estar igual tu solución con la del post, el objetivo es que aprendas no que me copies la solución.
Te recomiendo que uses mensajes de trazas, donde te sean necesarios. Si tienes problemas también puedes usar el depurador.
Aquí tienes todos los posts relacionados con Java:
Si tienes alguna duda, recuerda que puedes consultarnos escribiendo un comentario en este post o enviándonos un e-mail a administrador@discoduroderoer.es
1. Sumar los números números naturales hasta N (se lo damos nosotros) de forma recursiva.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_DDR_1;
/**
*
* @author Disco Duro de Roer
*/
public class Ejercicio_recursividad_DDR_1 {
public static void main(String[] args) {
int n=10;
//guardamos el resultado en una variable
int resultado=sumaRecursiva(n);
//Mostramos el resultado
System.out.println(resultado);
}
public static int sumaRecursiva(int numero){
int res;
if(numero==1){
//Se termina la recursion
return 1;
}else{
//Se llama a si misma la función con el parametro numero menos 1
res = numero+sumaRecursiva(numero-1);
}
//Devuelve el resultado
return res;
}
}
| |
2. Factorial de un número.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_2;
/**
* @author Disco Duro de Roer
*/
public class ejercicio_recursividad_DDR_2 {
public static void main(String[] args) {
int n=5;
//Guarda el resultado en una variable
int resultado=factorialRecursivo(n);
//Muestra el resultado
System.out.println(resultado);
}
public static int factorialRecursivo(int numero){
int res;
if(numero==1){
//Se termina la recursión
return 1;
}else{
//Se llama asi misma la funcion, con el valor del numero menos 1
res = numero * factorialRecursivo(numero-1);
}
//Devolvemos el valor
return res;
}
}
| |
3. Recorrer un array de forma recursiva.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_3;
/**
* @author Disco Duro de Roer
*/
public class Ejercicio_recursividad_DDR_3 {
public static void main(String[] args) {
int[] array={1,2,3,4,5}; //Creamos un array
mostrarArrayRecursivo(array, 0); //Pasamos el array y la posicion donde empieza
}
public static void mostrarArrayRecursivo(int[] array, int indice){
/*1º forma*/
/*
if (indice == (array.length-1)){
System.out.println(array[indice]);
}else{
System.out.println(array[indice]);
mostrarArrayRecursivo(array, indice+1);
}
*/
/*2º forma*/
if (indice != array.length){
//Mostramos el valor en ese indice
System.out.println(array[indice]);
//Llamamos recursivamente a la función
mostrarArrayRecursivo(array, indice+1);
}
}
}
| |
4. Buscar un elemento de un array de forma recursiva.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_4;
public class Ejercicio_recursividad_DDR_4 {
public static void main(String[] args) {
int[] array={1,2,3,4,5};
int elementoBuscar=3;
int posElementoEncontrado=posicionElementoRecursivo(array, elementoBuscar,0);
System.out.println(posElementoEncontrado);
}
public static int posicionElementoRecursivo(int[] array, int elementoBuscar ,int indice){
if(indice==array.length || array[indice]==elementoBuscar){
if(indice==array.length){
return -1;
}else{
return indice;
}
}else{
return posicionElementoRecursivo(array, elementoBuscar, indice+1);
}
}
}
| |
5. Recorrer una matriz de forma recursiva.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_5;
/**
* @author DiscoDurodeRoer
*/
public class Ejercicio_recursividad_DDR_5 {
public static void main(String[] args) {
int[][] m = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
//llamada inicial
recorrerMatrizRecursivo(m, 0, 0);
}
public static void recorrerMatrizRecursivo(int[][] m, int i, int j) {
//Muestro el numero (sin salto de linea)
System.out.print(m[i][j] + " ");
//
if (i != m.length - 1 || j != m[i].length - 1) {
//Indico si llego al final de la fila
if (j == m[i].length - 1) {
//Paso a la siguiente fila
i++;
//Reinicio la j
j = 0;
//Salto de linea (solo formato)
System.out.println("");
} else {
//Paso a la siguiente columna
j++;
}
//Volvemos a llamar la función recursivamente
recorrerMatrizRecursivo(m, i, j);
}
}
}
| |
6. Calcular el valor de la posición fibonacci usando recursividad.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_6;
/**
* @author DiscoDurodeRoer
*/
public class Ejercicio_recursividad_DDR_6 {
public static void main(String[] args) {
//Serie fibonacci
// 1 1 2 3 5 8 13 21 34 55
//llamada inicial
int posicion = 5;
int resultado = fibonacciRecursivo(posicion);
System.out.println(resultado);
}
public static int fibonacciRecursivo(int n) {
//CASO BASE, si es cero devuelve un cero
//Puedes poner n<=0 tamvien para incluir negativos
if (n == 0) {
return 0;
//CASO BASE, si es 1 devuelve un 1
} else if (n == 1) {
return 1;
} else {
//Hago la suma
return fibonacciRecursivo(n - 1) + fibonacciRecursivo(n - 2);
}
}
}
| |
7. Invertir un numero de forma recursiva (no usar String)
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_7;
public class ejercicio_recursividad_ddr_7 {
public static void main(String[] args) {
int a = 254; //400 + 50 + 2
System.out.println(invertirNum(a, 2));
}
public static int invertirNum(int num, int pos){
//Si es menor que 10 devuelvo el numero (el ultimo numero)
if(num < 10){
return num;
}else{
//Cojo el modulo del numero y lo multiplico por la potencia (4 * 100) por ejemplo
return (num % 10) * (int) Math.pow(10, pos) + (invertirNum(num/10, pos-1));
}
}
}
| |
8. Invertir una palabra de forma recursiva
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_8;
public class Ejercicio_recursividad_DDR_8 {
public static void main(String[] args) {
String palabra = "Hola";
System.out.println(invertirPalabra(palabra, palabra.length()-1));
}
public static String invertirPalabra(String palabra, int longitud){
if(longitud==0){
return palabra.charAt(longitud)+"";
}else{
return palabra.charAt(longitud) + (invertirPalabra(palabra, longitud-1));
}
}
}
| |
9. Calcula la potencia de un numero de forma recursiva, tanto para exponentes
negativos como positivos.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_9;
public class Ejercicio_recursividad_DDR_9 {
public static void main(String[] args) {
int base = 10;
int exponente = -2;
System.out.println(potencia(base, exponente));
}
public static double potencia(int base, int exponente) {
if (exponente == 0) { //caso base
return 1; //10^0 = 1
} else if (exponente == 1) { //caso base
return base; //10^1 = 10
} else if (exponente < 0) { //Exponente negativo
return potencia(base, exponente + 1) / base;
} else { //Exponente positivo
return base * potencia(base, exponente - 1);
}
}
}
| |
10. Suma los digitos de un numero de forma recursiva.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_10;
public class Ejercicio_recursividad_DDR_10 {
public static void main(String[] args) {
int numero = 123;
System.out.println(sumaDigitos(numero));
}
public static int sumaDigitos(int numero){
if(numero < 10){ //caso base
return numero; //devuelvo el numero
}else{
return (numero % 10) + sumaDigitos(numero/10); //Cojo el digito y llamo a la funcion
}
}
}
| |
11. Haz una función que obtenga el maximo numero de un array, pasandole el array, el indice y el numero maximo actual.
Otra función sin que sea necesario el tercer parámetro.
Haz lo mismo con el mínimo.
| Spoiler Inside | SelectShow> |
|---|---|
package ejercicio_recursividad_ddr_11;
public class Ejercicio_recursividad_DDR_11 {
public static void main(String[] args) {
int[] numeros = {6, 5, -9999, 10, 2, -10, 6};
System.out.println("Maximo v1: " + maximoRec(numeros, 0, numeros[0]));
System.out.println("Maximo v2: " + maximoRecV2(numeros, 0));
System.out.println("Minimo v1: " + minimoRec(numeros, 0, numeros[0]));
System.out.println("Minimo v2: " + minimoRecV2(numeros, 0));
}
public static int maximoRec(int[] numeros, int indice, int max) {
//Cuando el indice sea igual a la longitud del array, terminaremos la recursividad
if (indice != numeros.length) {
//Si el valor actual es mayor que el actual, lo llamaremos de forma distinta
if (numeros[indice] > max) {
max = maximoRec(numeros, indice + 1, numeros[indice]);
} else {
max = maximoRec(numeros, indice + 1, max);
}
}
return max;
}
public static int maximoRecV2(int[] numeros, int indice) {
int maximo = Integer.MIN_VALUE;
//Cuando el indice sea igual a la longitud del array, terminaremos la recursividad
if (indice != numeros.length) {
//Comparamos el 1º con el 2º, el 2º con el 3º, etc.
maximo = Math.max(numeros[indice], maximoRecV2(numeros, indice + 1));
}
return maximo;
}
public static int minimoRec(int[] numeros, int indice, int min) {
//Cuando el indice sea igual a la longitud del array, terminaremos la recursividad
if (indice != numeros.length) {
//Si el valor actual es menor que el actual, lo llamaremos de forma distinta
if (numeros[indice] < min) {
min = minimoRec(numeros, indice + 1, numeros[indice]);
} else {
min = minimoRec(numeros, indice + 1, min);
}
}
return min;
}
public static int minimoRecV2(int[] numeros, int indice) {
int minimo = Integer.MAX_VALUE;
//Cuando el indice sea igual a la longitud del array, terminaremos la recursividad
if (indice != numeros.length) {
//Comparamos el 1º con el 2º, el 2º con el 3º, etc.
minimo = Math.min(numeros[indice], minimoRecV2(numeros, indice + 1));
}
return minimo;
}
}
| |
12. Usando el arbol de nuestro canal, cuenta recursivamente, cuantos nodos hay.
| Spoiler Inside | SelectShow> |
|---|---|
— Main package ejercicio_recursividad_ddr_12;
import arbol.BinarySearchTree;
import arbol.NodoArbolBinario;
public class Ejercicio_recursividad_DDR_12 {
public static void main(String[] args) {
BinarySearchTree<Integer> arbol = new BinarySearchTree();
arbol.add(8);
arbol.add(4);
arbol.add(10);
arbol.add(12);
arbol.add(1);
arbol.add(0);
arbol.add(2);
arbol.add(9);
arbol.add(20);
arbol.add(30);
arbol.add(14);
arbol.add(16);
arbol.add(15);
arbol.add(13);
System.out.println(cuentaNodos(arbol.getRoot()));
}
public static int cuentaNodos(NodoArbolBinario nodo){
int contador=1;
if(nodo.getLeft()!=null){
contador += cuentaNodos(nodo.getLeft());
}
if(nodo.getRight()!=null){
contador += cuentaNodos(nodo.getRight());
}
return contador;
}
}
–NodoArbolBinario package arbol;
public class NodoArbolBinario<T extends Comparable<T>> {
private T element;
private NodoArbolBinario<T> parent;
private NodoArbolBinario<T> left;
private NodoArbolBinario<T> right;
public NodoArbolBinario(T element) {
this.element = element;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.parent = parent;
this.left = left;
this.right = right;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
this.element = element;
this.parent = parent;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public NodoArbolBinario<T> getParent() {
return parent;
}
public void setParent(NodoArbolBinario<T> parent) {
this.parent = parent;
}
public NodoArbolBinario<T> getLeft() {
return left;
}
public void setLeft(NodoArbolBinario<T> left) {
this.left = left;
}
public NodoArbolBinario<T> getRight() {
return right;
}
public void setRight(NodoArbolBinario<T> right) {
this.right = right;
}
}
— NodoArbolBinario package arbol;
public class NodoArbolBinario<T extends Comparable<T>> {
private T element;
private NodoArbolBinario<T> parent;
private NodoArbolBinario<T> left;
private NodoArbolBinario<T> right;
public NodoArbolBinario(T element) {
this.element = element;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.parent = parent;
this.left = left;
this.right = right;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
this.element = element;
this.parent = parent;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public NodoArbolBinario<T> getParent() {
return parent;
}
public void setParent(NodoArbolBinario<T> parent) {
this.parent = parent;
}
public NodoArbolBinario<T> getLeft() {
return left;
}
public void setLeft(NodoArbolBinario<T> left) {
this.left = left;
}
public NodoArbolBinario<T> getRight() {
return right;
}
public void setRight(NodoArbolBinario<T> right) {
this.right = right;
}
}
— Nodo package lista_dinamica;
/**
* Clase Nodo
*
* @author DiscoDurodeRoer
* @param <T>
*/
public class Nodo<T> {
//Atributos
private T elemento;
private Nodo<T> siguiente; //Apunta al siguiente nodo
//Contructor
public Nodo(T elemento, Nodo<T> siguiente) {
this.elemento = elemento;
this.siguiente = siguiente;
}
//Metodos
public T getElemento() {
return elemento;
}
public void setElemento(T elemento) {
this.elemento = elemento;
}
public Nodo<T> getSiguiente() {
return siguiente;
}
public void setSiguiente(Nodo<T> siguiente) {
this.siguiente = siguiente;
}
@Override
public String toString() {
return elemento + "\n";
}
}
— ListaDinamica package lista_dinamica;
import java.util.Iterator;
/**
* Lista Dinamica Version 2.0
*
* @author DiscoDurodeRoer
* @param <T>
*/
public class ListaDinamica<T> implements Iterable<T>{
//Atributos
private Nodo<T> primero;
private Nodo<T> ultimo;
private int tamanio;
public ListaDinamica() {
primero = null;
ultimo = null;
tamanio = 0;
}
/**
* Indica si esta la lista vacia o no
*
* @return
*/
public boolean isEmpty() {
return tamanio == 0;
}
/**
* Devuelve el tamaño de la lista
*
* @return
*/
public int size() {
return tamanio;
}
/**
* Devuelve el elemento en la posicion indicada
*
* @param index
* @return
*/
public T get(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return getFirst(); //Cojo el primero
} else if (index == size() - 1) {
return getLast(); //Cojo el ultimo
} else {
//Uso la funcion getNode para coger el nodo deseado
Nodo<T> buscado = getNode(index);
return buscado.getElemento();
}
}
/**
* Devuelve el primer elemento, null si esta vacia la lista
*
* @return
*/
public T getFirst() {
//Si esta vacia, no hay primero que coger
if (isEmpty()) {
return null;
} else {
return primero.getElemento();
}
}
/**
* Devuelve el ultimo elemento, null si esta vacia la lista
*
* @return
*/
public T getLast() {
//Si esta vacia, no hay ultimo que coger
if (isEmpty()) {
return null;
} else {
return ultimo.getElemento();
}
}
/**
* Devuelve el nodo completo de una posicion concreta
*
* @param index
* @return
*/
private Nodo<T> getNode(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return primero; //devuelvo el primero
} else if (index == size() - 1) {
return ultimo; //devuelvo el ultimo
} else {
Nodo<T> buscado = primero;
//Busco el nodo deseado con un recorrido
int contador = 0;
while (contador < index) {
contador++;
buscado = buscado.getSiguiente();
}
//Me devuelve el buscado
return buscado;
}
}
/**
* Añade un elemento al final de la lista
*
* @param elemento
* @return elemento añadido
*/
public T addLast(T elemento) {
Nodo<T> aux;
//Si esta vacia, hago lo mismo que si fuera añadir el primero
if (isEmpty()) {
return addFirst(elemento);
} else {
//Hago el intercambio
aux = new Nodo<>(elemento, null);
ultimo.setSiguiente(aux);
ultimo = aux;
}
//Aumento el tamanño
tamanio++;
return ultimo.getElemento();
}
/**
* Añade el elemento al principio de la lista
*
* @param elemento
* @return elemento añadido
*/
public T addFirst(T elemento) {
Nodo<T> aux;
//si esta vacia, el nodo será el primero y ultimo
if (isEmpty()) {
aux = new Nodo<>(elemento, null);
primero = aux;
ultimo = aux;
} else {
//Hago el intercambio
Nodo<T> primeroActual = primero;
aux = new Nodo<>(elemento, primeroActual);
primero = aux;
}
//Aumento el tamanño
tamanio++;
return primero.getElemento();
}
/**
* Añade un elemento en una posicion indicada
*
* @param elemento
* @param index debe ser un indice valido
* @return elemento añadido
*/
public T add(T elemento, int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (index == 0) {
return addFirst(elemento); //Añade en la primera posicion
} else if (index == size()) {
return addLast(elemento); //añade en la ultima posicion
} else if ((index < 0 || index >= size())) {
return null;
} else {
//Cojo el anterior nodo al que estoy buscando
Nodo<T> buscado_anterior = getNode(index - 1);
//Cojo el nodo de la posicion indicada
Nodo<T> buscado_actual = getNode(index);
//Creo el nuevo novo, este apuntara al de la posicion actual
Nodo<T> aux = new Nodo<>(elemento, buscado_actual);
//el nodo anterior apunta a nuestro nuevo nodo
buscado_anterior.setSiguiente(aux);
//Aumento el tamaño
tamanio++;
return getNode(index).getElemento();
}
}
/**
* Devuelve el estado de la lista
*
* @return
*/
public String toString() {
String contenido = "";
//Si esta vacia, lo indica
if (isEmpty()) {
contenido = "Lista vacia";
} else {
Nodo<T> aux = primero;
//Recorre la lista, mostrando el contenido
while (aux != null) {
contenido += aux.toString();
aux = aux.getSiguiente();
}
}
return contenido;
}
/**
* Indica si existe el elemento indicado
*
* @param elemento
* @return
*/
public boolean exists(T elemento) {
//Si esta vacio, devuelve el false
if (isEmpty()) {
return false;
} else {
Nodo<T> aux = primero;
//Recorremos la lista
while (aux != null) {
if (elemento.equals(aux.getElemento())) { //Mejor .equals que ==
return true; //Existe
}
aux = aux.getSiguiente();
}
//Si no lo encuentra devuelve false
return false;
}
}
/**
* Indica la posición del elemento
*
* @param elemento
* @return
*/
public int indexOf(T elemento) {
//Si esta vacio, devuelvemos -1
if (isEmpty()) {
return -1;
} else {
Nodo<T> aux = primero;
int posicion = 0;
while (aux != null) {
if (elemento.equals(aux.getElemento())) { //Mejor .equals que ==
return posicion; //Existe
}
posicion++;
aux = aux.getSiguiente();
}
//Si no lo encuentra devuelve -1
return -1;
}
}
/**
* Elimina el primer elemento de la lista
*
* @return
*/
public T removeFirst() {
//Si la lista esta vacia, devolvemos null
if (isEmpty()) {
return null;
} else {
//Guardo el elemento antes
T elemento = primero.getElemento();
//Cojo el segundo
Nodo<T> aux = primero.getSiguiente();
primero = null; //Lo marco como null para el recolector
primero = aux; //Este es mi nuevo primero
//En caso de que borremos el ultimo elemento,el ultimo también
if (size() == 1) {
ultimo = null;
}
tamanio--;
return elemento;
}
}
/**
* Borra el ultimo elemento de la lista
*
* @return
*/
public T removeLast() {
if (isEmpty()) {
return null;
} else {
//Coge el elemento antes de borrar
T elemento = ultimo.getElemento();
//Cojo el penultimo
Nodo<T> aux = getNode(size() - 2);
//En caso de que sea null
//Hay 1 o dos elementos
if (aux == null) {
//marco el ultimo como nulo
ultimo = null;
//Si hay dos, el primero y el ultimo seran el mismo
//Si hay 1 elemento, significa que borramos la lista
if (size() == 2) {
ultimo = primero;
} else {
primero = null;
}
} else {
//el penultimo es el nuevo ultimo
//y le ponemos como siguiente nulo
ultimo = null;
ultimo = aux;
ultimo.setSiguiente(null);
}
tamanio--;
return elemento;
}
}
/**
* Elimina el nodo de la lista en una posicion concreta
*
* @param index
* @return
*/
public T remove(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return removeFirst();
} else if (index == size() - 1) {
return removeLast();
} else {
//Cojo el nodo anterior al que quiero borrar
Nodo<T> nodo_anterior = getNode(index - 1);
//Cojo el nodo que quiero borrar
Nodo<T> nodo_actual = getNode(index);
//Cojo el elemento antes de borrar
T elemento = nodo_actual.getElemento();
//Cojo el nodo siguiente al que quiero borrar
Nodo<T> nodo_siguiente = nodo_actual.getSiguiente();
//Lo marco para borrar para el recolector
nodo_actual = null;
//El nodo anterior apunta al nodo siguiente
nodo_anterior.setSiguiente(nodo_siguiente);
tamanio--;
return elemento;
}
}
/**
* Modifico el elemento de una posicion No afecta a la estructura de la
* lista
*
* @param elemento
* @param index
* @return
*/
public T modify(T elemento, int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else {
//Nodo actual
Nodo<T> aux = getNode(index);
//modifico
aux.setElemento(elemento);
return aux.getElemento();
}
}
@Override
public Iterator<T> iterator() {
return new MyIterator();
}
//Creo la clase interna MyIterator, que implementa la interfaz Iterator
private class MyIterator<ListaDinamica> implements Iterator<T>{
//Indica el siguiente elemento que se va a devolver
private int siguiente;
//Indica si hay un elemento
@Override
public boolean hasNext() {
return getNode(siguiente)!=null;
}
//Devuelve el elemento actual e incrementa al siguiente
@Override
public T next() {
T elemento = getNode(siguiente).getElemento();
siguiente++;
return elemento;
}
}
}
| |
13. Usando el arbol de nuestro canal, cuenta recursivamente, cuantas hojas hay (external).
| Spoiler Inside | SelectShow> |
|---|---|
— Main package ejercicio_recursividad_ddr_13;
import arbol.BinarySearchTree;
import arbol.NodoArbolBinario;
public class Ejercicio_recursividad_DDR_13 {
public static void main(String[] args) {
BinarySearchTree<Integer> arbol = new BinarySearchTree();
arbol.add(8);
arbol.add(4);
arbol.add(10);
arbol.add(12);
arbol.add(1);
arbol.add(0);
arbol.add(2);
arbol.add(9);
arbol.add(20);
arbol.add(30);
arbol.add(14);
arbol.add(16);
arbol.add(15);
arbol.add(13);
System.out.println(cuentaNodos(arbol, arbol.getRoot()));
}
public static int cuentaNodos(BinarySearchTree arbol, NodoArbolBinario nodo){
int contador=0;
if(arbol.isLeaf(nodo)){
contador++;
}
if(nodo.getLeft()!=null){
contador += cuentaNodos(arbol, nodo.getLeft());
}
if(nodo.getRight()!=null){
contador += cuentaNodos(arbol, nodo.getRight());
}
return contador;
}
}
–NodoArbolBinario package arbol;
public class NodoArbolBinario<T extends Comparable<T>> {
private T element;
private NodoArbolBinario<T> parent;
private NodoArbolBinario<T> left;
private NodoArbolBinario<T> right;
public NodoArbolBinario(T element) {
this.element = element;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.parent = parent;
this.left = left;
this.right = right;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
this.element = element;
this.parent = parent;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public NodoArbolBinario<T> getParent() {
return parent;
}
public void setParent(NodoArbolBinario<T> parent) {
this.parent = parent;
}
public NodoArbolBinario<T> getLeft() {
return left;
}
public void setLeft(NodoArbolBinario<T> left) {
this.left = left;
}
public NodoArbolBinario<T> getRight() {
return right;
}
public void setRight(NodoArbolBinario<T> right) {
this.right = right;
}
}
— NodoArbolBinario package arbol;
public class NodoArbolBinario<T extends Comparable<T>> {
private T element;
private NodoArbolBinario<T> parent;
private NodoArbolBinario<T> left;
private NodoArbolBinario<T> right;
public NodoArbolBinario(T element) {
this.element = element;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.parent = parent;
this.left = left;
this.right = right;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
this.element = element;
this.parent = parent;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public NodoArbolBinario<T> getParent() {
return parent;
}
public void setParent(NodoArbolBinario<T> parent) {
this.parent = parent;
}
public NodoArbolBinario<T> getLeft() {
return left;
}
public void setLeft(NodoArbolBinario<T> left) {
this.left = left;
}
public NodoArbolBinario<T> getRight() {
return right;
}
public void setRight(NodoArbolBinario<T> right) {
this.right = right;
}
}
— Nodo package lista_dinamica;
/**
* Clase Nodo
*
* @author DiscoDurodeRoer
* @param <T>
*/
public class Nodo<T> {
//Atributos
private T elemento;
private Nodo<T> siguiente; //Apunta al siguiente nodo
//Contructor
public Nodo(T elemento, Nodo<T> siguiente) {
this.elemento = elemento;
this.siguiente = siguiente;
}
//Metodos
public T getElemento() {
return elemento;
}
public void setElemento(T elemento) {
this.elemento = elemento;
}
public Nodo<T> getSiguiente() {
return siguiente;
}
public void setSiguiente(Nodo<T> siguiente) {
this.siguiente = siguiente;
}
@Override
public String toString() {
return elemento + "\n";
}
}
— ListaDinamica package lista_dinamica;
import java.util.Iterator;
/**
* Lista Dinamica Version 2.0
*
* @author DiscoDurodeRoer
* @param <T>
*/
public class ListaDinamica<T> implements Iterable<T>{
//Atributos
private Nodo<T> primero;
private Nodo<T> ultimo;
private int tamanio;
public ListaDinamica() {
primero = null;
ultimo = null;
tamanio = 0;
}
/**
* Indica si esta la lista vacia o no
*
* @return
*/
public boolean isEmpty() {
return tamanio == 0;
}
/**
* Devuelve el tamaño de la lista
*
* @return
*/
public int size() {
return tamanio;
}
/**
* Devuelve el elemento en la posicion indicada
*
* @param index
* @return
*/
public T get(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return getFirst(); //Cojo el primero
} else if (index == size() - 1) {
return getLast(); //Cojo el ultimo
} else {
//Uso la funcion getNode para coger el nodo deseado
Nodo<T> buscado = getNode(index);
return buscado.getElemento();
}
}
/**
* Devuelve el primer elemento, null si esta vacia la lista
*
* @return
*/
public T getFirst() {
//Si esta vacia, no hay primero que coger
if (isEmpty()) {
return null;
} else {
return primero.getElemento();
}
}
/**
* Devuelve el ultimo elemento, null si esta vacia la lista
*
* @return
*/
public T getLast() {
//Si esta vacia, no hay ultimo que coger
if (isEmpty()) {
return null;
} else {
return ultimo.getElemento();
}
}
/**
* Devuelve el nodo completo de una posicion concreta
*
* @param index
* @return
*/
private Nodo<T> getNode(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return primero; //devuelvo el primero
} else if (index == size() - 1) {
return ultimo; //devuelvo el ultimo
} else {
Nodo<T> buscado = primero;
//Busco el nodo deseado con un recorrido
int contador = 0;
while (contador < index) {
contador++;
buscado = buscado.getSiguiente();
}
//Me devuelve el buscado
return buscado;
}
}
/**
* Añade un elemento al final de la lista
*
* @param elemento
* @return elemento añadido
*/
public T addLast(T elemento) {
Nodo<T> aux;
//Si esta vacia, hago lo mismo que si fuera añadir el primero
if (isEmpty()) {
return addFirst(elemento);
} else {
//Hago el intercambio
aux = new Nodo<>(elemento, null);
ultimo.setSiguiente(aux);
ultimo = aux;
}
//Aumento el tamanño
tamanio++;
return ultimo.getElemento();
}
/**
* Añade el elemento al principio de la lista
*
* @param elemento
* @return elemento añadido
*/
public T addFirst(T elemento) {
Nodo<T> aux;
//si esta vacia, el nodo será el primero y ultimo
if (isEmpty()) {
aux = new Nodo<>(elemento, null);
primero = aux;
ultimo = aux;
} else {
//Hago el intercambio
Nodo<T> primeroActual = primero;
aux = new Nodo<>(elemento, primeroActual);
primero = aux;
}
//Aumento el tamanño
tamanio++;
return primero.getElemento();
}
/**
* Añade un elemento en una posicion indicada
*
* @param elemento
* @param index debe ser un indice valido
* @return elemento añadido
*/
public T add(T elemento, int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (index == 0) {
return addFirst(elemento); //Añade en la primera posicion
} else if (index == size()) {
return addLast(elemento); //añade en la ultima posicion
} else if ((index < 0 || index >= size())) {
return null;
} else {
//Cojo el anterior nodo al que estoy buscando
Nodo<T> buscado_anterior = getNode(index - 1);
//Cojo el nodo de la posicion indicada
Nodo<T> buscado_actual = getNode(index);
//Creo el nuevo novo, este apuntara al de la posicion actual
Nodo<T> aux = new Nodo<>(elemento, buscado_actual);
//el nodo anterior apunta a nuestro nuevo nodo
buscado_anterior.setSiguiente(aux);
//Aumento el tamaño
tamanio++;
return getNode(index).getElemento();
}
}
/**
* Devuelve el estado de la lista
*
* @return
*/
public String toString() {
String contenido = "";
//Si esta vacia, lo indica
if (isEmpty()) {
contenido = "Lista vacia";
} else {
Nodo<T> aux = primero;
//Recorre la lista, mostrando el contenido
while (aux != null) {
contenido += aux.toString();
aux = aux.getSiguiente();
}
}
return contenido;
}
/**
* Indica si existe el elemento indicado
*
* @param elemento
* @return
*/
public boolean exists(T elemento) {
//Si esta vacio, devuelve el false
if (isEmpty()) {
return false;
} else {
Nodo<T> aux = primero;
//Recorremos la lista
while (aux != null) {
if (elemento.equals(aux.getElemento())) { //Mejor .equals que ==
return true; //Existe
}
aux = aux.getSiguiente();
}
//Si no lo encuentra devuelve false
return false;
}
}
/**
* Indica la posición del elemento
*
* @param elemento
* @return
*/
public int indexOf(T elemento) {
//Si esta vacio, devuelvemos -1
if (isEmpty()) {
return -1;
} else {
Nodo<T> aux = primero;
int posicion = 0;
while (aux != null) {
if (elemento.equals(aux.getElemento())) { //Mejor .equals que ==
return posicion; //Existe
}
posicion++;
aux = aux.getSiguiente();
}
//Si no lo encuentra devuelve -1
return -1;
}
}
/**
* Elimina el primer elemento de la lista
*
* @return
*/
public T removeFirst() {
//Si la lista esta vacia, devolvemos null
if (isEmpty()) {
return null;
} else {
//Guardo el elemento antes
T elemento = primero.getElemento();
//Cojo el segundo
Nodo<T> aux = primero.getSiguiente();
primero = null; //Lo marco como null para el recolector
primero = aux; //Este es mi nuevo primero
//En caso de que borremos el ultimo elemento,el ultimo también
if (size() == 1) {
ultimo = null;
}
tamanio--;
return elemento;
}
}
/**
* Borra el ultimo elemento de la lista
*
* @return
*/
public T removeLast() {
if (isEmpty()) {
return null;
} else {
//Coge el elemento antes de borrar
T elemento = ultimo.getElemento();
//Cojo el penultimo
Nodo<T> aux = getNode(size() - 2);
//En caso de que sea null
//Hay 1 o dos elementos
if (aux == null) {
//marco el ultimo como nulo
ultimo = null;
//Si hay dos, el primero y el ultimo seran el mismo
//Si hay 1 elemento, significa que borramos la lista
if (size() == 2) {
ultimo = primero;
} else {
primero = null;
}
} else {
//el penultimo es el nuevo ultimo
//y le ponemos como siguiente nulo
ultimo = null;
ultimo = aux;
ultimo.setSiguiente(null);
}
tamanio--;
return elemento;
}
}
/**
* Elimina el nodo de la lista en una posicion concreta
*
* @param index
* @return
*/
public T remove(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return removeFirst();
} else if (index == size() - 1) {
return removeLast();
} else {
//Cojo el nodo anterior al que quiero borrar
Nodo<T> nodo_anterior = getNode(index - 1);
//Cojo el nodo que quiero borrar
Nodo<T> nodo_actual = getNode(index);
//Cojo el elemento antes de borrar
T elemento = nodo_actual.getElemento();
//Cojo el nodo siguiente al que quiero borrar
Nodo<T> nodo_siguiente = nodo_actual.getSiguiente();
//Lo marco para borrar para el recolector
nodo_actual = null;
//El nodo anterior apunta al nodo siguiente
nodo_anterior.setSiguiente(nodo_siguiente);
tamanio--;
return elemento;
}
}
/**
* Modifico el elemento de una posicion No afecta a la estructura de la
* lista
*
* @param elemento
* @param index
* @return
*/
public T modify(T elemento, int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else {
//Nodo actual
Nodo<T> aux = getNode(index);
//modifico
aux.setElemento(elemento);
return aux.getElemento();
}
}
@Override
public Iterator<T> iterator() {
return new MyIterator();
}
//Creo la clase interna MyIterator, que implementa la interfaz Iterator
private class MyIterator<ListaDinamica> implements Iterator<T>{
//Indica el siguiente elemento que se va a devolver
private int siguiente;
//Indica si hay un elemento
@Override
public boolean hasNext() {
return getNode(siguiente)!=null;
}
//Devuelve el elemento actual e incrementa al siguiente
@Override
public T next() {
T elemento = getNode(siguiente).getElemento();
siguiente++;
return elemento;
}
}
}
| |
14. Usando el arbol de nuestro canal, guardar en una lista dinámica todos los números entre 2 números pasados por parámetro.
| Spoiler Inside | SelectShow> |
|---|---|
— Main package ejercicio_recursividad_ddr_14;
import arbol.BinarySearchTree;
import arbol.NodoArbolBinario;
import lista_dinamica.ListaDinamica;
public class Ejercicio_recursividad_DDR_14 {
public static void main(String[] args) {
BinarySearchTree<Integer> arbol = new BinarySearchTree();
arbol.add(8);
arbol.add(4);
arbol.add(10);
arbol.add(12);
arbol.add(1);
arbol.add(0);
arbol.add(2);
arbol.add(9);
arbol.add(20);
arbol.add(30);
arbol.add(14);
arbol.add(16);
arbol.add(15);
arbol.add(13);
ListaDinamica<Integer> l = new ListaDinamica<>();
rellenaElementos(arbol.getRoot(), l, 5, 15);
for (Integer i:l) {
System.out.println(i);
}
}
public static void rellenaElementos(NodoArbolBinario<Integer> nodo,
ListaDinamica<Integer> lista,
int min, int max) {
if (nodo.getElement() >= min && nodo.getElement() <= max) {
lista.addFirst(nodo.getElement());
}
if (nodo.getLeft() != null) {
rellenaElementos(nodo.getLeft(), lista, min, max);
}
if (nodo.getRight() != null) {
rellenaElementos(nodo.getRight(), lista, min, max);
}
}
}
–NodoArbolBinario package arbol;
public class NodoArbolBinario<T extends Comparable<T>> {
private T element;
private NodoArbolBinario<T> parent;
private NodoArbolBinario<T> left;
private NodoArbolBinario<T> right;
public NodoArbolBinario(T element) {
this.element = element;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.parent = parent;
this.left = left;
this.right = right;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
this.element = element;
this.parent = parent;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public NodoArbolBinario<T> getParent() {
return parent;
}
public void setParent(NodoArbolBinario<T> parent) {
this.parent = parent;
}
public NodoArbolBinario<T> getLeft() {
return left;
}
public void setLeft(NodoArbolBinario<T> left) {
this.left = left;
}
public NodoArbolBinario<T> getRight() {
return right;
}
public void setRight(NodoArbolBinario<T> right) {
this.right = right;
}
}
— NodoArbolBinario package arbol;
public class NodoArbolBinario<T extends Comparable<T>> {
private T element;
private NodoArbolBinario<T> parent;
private NodoArbolBinario<T> left;
private NodoArbolBinario<T> right;
public NodoArbolBinario(T element) {
this.element = element;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.parent = parent;
this.left = left;
this.right = right;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
this.element = element;
this.parent = parent;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public NodoArbolBinario<T> getParent() {
return parent;
}
public void setParent(NodoArbolBinario<T> parent) {
this.parent = parent;
}
public NodoArbolBinario<T> getLeft() {
return left;
}
public void setLeft(NodoArbolBinario<T> left) {
this.left = left;
}
public NodoArbolBinario<T> getRight() {
return right;
}
public void setRight(NodoArbolBinario<T> right) {
this.right = right;
}
}
— Nodo package lista_dinamica;
/**
* Clase Nodo
*
* @author DiscoDurodeRoer
* @param <T>
*/
public class Nodo<T> {
//Atributos
private T elemento;
private Nodo<T> siguiente; //Apunta al siguiente nodo
//Contructor
public Nodo(T elemento, Nodo<T> siguiente) {
this.elemento = elemento;
this.siguiente = siguiente;
}
//Metodos
public T getElemento() {
return elemento;
}
public void setElemento(T elemento) {
this.elemento = elemento;
}
public Nodo<T> getSiguiente() {
return siguiente;
}
public void setSiguiente(Nodo<T> siguiente) {
this.siguiente = siguiente;
}
@Override
public String toString() {
return elemento + "\n";
}
}
— ListaDinamica package lista_dinamica;
import java.util.Iterator;
/**
* Lista Dinamica Version 2.0
*
* @author DiscoDurodeRoer
* @param <T>
*/
public class ListaDinamica<T> implements Iterable<T>{
//Atributos
private Nodo<T> primero;
private Nodo<T> ultimo;
private int tamanio;
public ListaDinamica() {
primero = null;
ultimo = null;
tamanio = 0;
}
/**
* Indica si esta la lista vacia o no
*
* @return
*/
public boolean isEmpty() {
return tamanio == 0;
}
/**
* Devuelve el tamaño de la lista
*
* @return
*/
public int size() {
return tamanio;
}
/**
* Devuelve el elemento en la posicion indicada
*
* @param index
* @return
*/
public T get(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return getFirst(); //Cojo el primero
} else if (index == size() - 1) {
return getLast(); //Cojo el ultimo
} else {
//Uso la funcion getNode para coger el nodo deseado
Nodo<T> buscado = getNode(index);
return buscado.getElemento();
}
}
/**
* Devuelve el primer elemento, null si esta vacia la lista
*
* @return
*/
public T getFirst() {
//Si esta vacia, no hay primero que coger
if (isEmpty()) {
return null;
} else {
return primero.getElemento();
}
}
/**
* Devuelve el ultimo elemento, null si esta vacia la lista
*
* @return
*/
public T getLast() {
//Si esta vacia, no hay ultimo que coger
if (isEmpty()) {
return null;
} else {
return ultimo.getElemento();
}
}
/**
* Devuelve el nodo completo de una posicion concreta
*
* @param index
* @return
*/
private Nodo<T> getNode(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return primero; //devuelvo el primero
} else if (index == size() - 1) {
return ultimo; //devuelvo el ultimo
} else {
Nodo<T> buscado = primero;
//Busco el nodo deseado con un recorrido
int contador = 0;
while (contador < index) {
contador++;
buscado = buscado.getSiguiente();
}
//Me devuelve el buscado
return buscado;
}
}
/**
* Añade un elemento al final de la lista
*
* @param elemento
* @return elemento añadido
*/
public T addLast(T elemento) {
Nodo<T> aux;
//Si esta vacia, hago lo mismo que si fuera añadir el primero
if (isEmpty()) {
return addFirst(elemento);
} else {
//Hago el intercambio
aux = new Nodo<>(elemento, null);
ultimo.setSiguiente(aux);
ultimo = aux;
}
//Aumento el tamanño
tamanio++;
return ultimo.getElemento();
}
/**
* Añade el elemento al principio de la lista
*
* @param elemento
* @return elemento añadido
*/
public T addFirst(T elemento) {
Nodo<T> aux;
//si esta vacia, el nodo será el primero y ultimo
if (isEmpty()) {
aux = new Nodo<>(elemento, null);
primero = aux;
ultimo = aux;
} else {
//Hago el intercambio
Nodo<T> primeroActual = primero;
aux = new Nodo<>(elemento, primeroActual);
primero = aux;
}
//Aumento el tamanño
tamanio++;
return primero.getElemento();
}
/**
* Añade un elemento en una posicion indicada
*
* @param elemento
* @param index debe ser un indice valido
* @return elemento añadido
*/
public T add(T elemento, int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (index == 0) {
return addFirst(elemento); //Añade en la primera posicion
} else if (index == size()) {
return addLast(elemento); //añade en la ultima posicion
} else if ((index < 0 || index >= size())) {
return null;
} else {
//Cojo el anterior nodo al que estoy buscando
Nodo<T> buscado_anterior = getNode(index - 1);
//Cojo el nodo de la posicion indicada
Nodo<T> buscado_actual = getNode(index);
//Creo el nuevo novo, este apuntara al de la posicion actual
Nodo<T> aux = new Nodo<>(elemento, buscado_actual);
//el nodo anterior apunta a nuestro nuevo nodo
buscado_anterior.setSiguiente(aux);
//Aumento el tamaño
tamanio++;
return getNode(index).getElemento();
}
}
/**
* Devuelve el estado de la lista
*
* @return
*/
public String toString() {
String contenido = "";
//Si esta vacia, lo indica
if (isEmpty()) {
contenido = "Lista vacia";
} else {
Nodo<T> aux = primero;
//Recorre la lista, mostrando el contenido
while (aux != null) {
contenido += aux.toString();
aux = aux.getSiguiente();
}
}
return contenido;
}
/**
* Indica si existe el elemento indicado
*
* @param elemento
* @return
*/
public boolean exists(T elemento) {
//Si esta vacio, devuelve el false
if (isEmpty()) {
return false;
} else {
Nodo<T> aux = primero;
//Recorremos la lista
while (aux != null) {
if (elemento.equals(aux.getElemento())) { //Mejor .equals que ==
return true; //Existe
}
aux = aux.getSiguiente();
}
//Si no lo encuentra devuelve false
return false;
}
}
/**
* Indica la posición del elemento
*
* @param elemento
* @return
*/
public int indexOf(T elemento) {
//Si esta vacio, devuelvemos -1
if (isEmpty()) {
return -1;
} else {
Nodo<T> aux = primero;
int posicion = 0;
while (aux != null) {
if (elemento.equals(aux.getElemento())) { //Mejor .equals que ==
return posicion; //Existe
}
posicion++;
aux = aux.getSiguiente();
}
//Si no lo encuentra devuelve -1
return -1;
}
}
/**
* Elimina el primer elemento de la lista
*
* @return
*/
public T removeFirst() {
//Si la lista esta vacia, devolvemos null
if (isEmpty()) {
return null;
} else {
//Guardo el elemento antes
T elemento = primero.getElemento();
//Cojo el segundo
Nodo<T> aux = primero.getSiguiente();
primero = null; //Lo marco como null para el recolector
primero = aux; //Este es mi nuevo primero
//En caso de que borremos el ultimo elemento,el ultimo también
if (size() == 1) {
ultimo = null;
}
tamanio--;
return elemento;
}
}
/**
* Borra el ultimo elemento de la lista
*
* @return
*/
public T removeLast() {
if (isEmpty()) {
return null;
} else {
//Coge el elemento antes de borrar
T elemento = ultimo.getElemento();
//Cojo el penultimo
Nodo<T> aux = getNode(size() - 2);
//En caso de que sea null
//Hay 1 o dos elementos
if (aux == null) {
//marco el ultimo como nulo
ultimo = null;
//Si hay dos, el primero y el ultimo seran el mismo
//Si hay 1 elemento, significa que borramos la lista
if (size() == 2) {
ultimo = primero;
} else {
primero = null;
}
} else {
//el penultimo es el nuevo ultimo
//y le ponemos como siguiente nulo
ultimo = null;
ultimo = aux;
ultimo.setSiguiente(null);
}
tamanio--;
return elemento;
}
}
/**
* Elimina el nodo de la lista en una posicion concreta
*
* @param index
* @return
*/
public T remove(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return removeFirst();
} else if (index == size() - 1) {
return removeLast();
} else {
//Cojo el nodo anterior al que quiero borrar
Nodo<T> nodo_anterior = getNode(index - 1);
//Cojo el nodo que quiero borrar
Nodo<T> nodo_actual = getNode(index);
//Cojo el elemento antes de borrar
T elemento = nodo_actual.getElemento();
//Cojo el nodo siguiente al que quiero borrar
Nodo<T> nodo_siguiente = nodo_actual.getSiguiente();
//Lo marco para borrar para el recolector
nodo_actual = null;
//El nodo anterior apunta al nodo siguiente
nodo_anterior.setSiguiente(nodo_siguiente);
tamanio--;
return elemento;
}
}
/**
* Modifico el elemento de una posicion No afecta a la estructura de la
* lista
*
* @param elemento
* @param index
* @return
*/
public T modify(T elemento, int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else {
//Nodo actual
Nodo<T> aux = getNode(index);
//modifico
aux.setElemento(elemento);
return aux.getElemento();
}
}
@Override
public Iterator<T> iterator() {
return new MyIterator();
}
//Creo la clase interna MyIterator, que implementa la interfaz Iterator
private class MyIterator<ListaDinamica> implements Iterator<T>{
//Indica el siguiente elemento que se va a devolver
private int siguiente;
//Indica si hay un elemento
@Override
public boolean hasNext() {
return getNode(siguiente)!=null;
}
//Devuelve el elemento actual e incrementa al siguiente
@Override
public T next() {
T elemento = getNode(siguiente).getElemento();
siguiente++;
return elemento;
}
}
}
| |
15. Contar el números de nodos con un elemento en concreto.
| Spoiler Inside | SelectShow> |
|---|---|
— Main package ejercicio_recursividad_ddr_15;
import arbol.BinarySearchTree;
import arbol.NodoArbolBinario;
public class Ejercicio_recursividad_DDR_15 {
public static void main(String[] args) {
BinarySearchTree<Integer> arbol = new BinarySearchTree();
arbol.add(8);
arbol.add(4);
arbol.add(10);
arbol.add(12);
arbol.add(1);
arbol.add(0);
arbol.add(2);
arbol.add(9);
arbol.add(20);
arbol.add(30);
arbol.add(14);
arbol.add(16);
arbol.add(15);
arbol.add(13);
System.out.println(cuentaNodos(arbol.getRoot(), 4));
}
public static int cuentaNodos(NodoArbolBinario<Integer> nodo, int elemento){
int contador=0;
if(nodo.getElement() == elemento){
contador++;
}
if(nodo.getLeft()!=null){
contador += cuentaNodos(nodo.getLeft(), elemento);
}
if(nodo.getRight()!=null){
contador += cuentaNodos(nodo.getRight(), elemento);
}
return contador;
}
}
–NodoArbolBinario package arbol;
public class NodoArbolBinario<T extends Comparable<T>> {
private T element;
private NodoArbolBinario<T> parent;
private NodoArbolBinario<T> left;
private NodoArbolBinario<T> right;
public NodoArbolBinario(T element) {
this.element = element;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.parent = parent;
this.left = left;
this.right = right;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
this.element = element;
this.parent = parent;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public NodoArbolBinario<T> getParent() {
return parent;
}
public void setParent(NodoArbolBinario<T> parent) {
this.parent = parent;
}
public NodoArbolBinario<T> getLeft() {
return left;
}
public void setLeft(NodoArbolBinario<T> left) {
this.left = left;
}
public NodoArbolBinario<T> getRight() {
return right;
}
public void setRight(NodoArbolBinario<T> right) {
this.right = right;
}
}
— NodoArbolBinario package arbol;
public class NodoArbolBinario<T extends Comparable<T>> {
private T element;
private NodoArbolBinario<T> parent;
private NodoArbolBinario<T> left;
private NodoArbolBinario<T> right;
public NodoArbolBinario(T element) {
this.element = element;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.parent = parent;
this.left = left;
this.right = right;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> parent) {
this.element = element;
this.parent = parent;
}
public NodoArbolBinario(T element, NodoArbolBinario<T> left, NodoArbolBinario<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public NodoArbolBinario<T> getParent() {
return parent;
}
public void setParent(NodoArbolBinario<T> parent) {
this.parent = parent;
}
public NodoArbolBinario<T> getLeft() {
return left;
}
public void setLeft(NodoArbolBinario<T> left) {
this.left = left;
}
public NodoArbolBinario<T> getRight() {
return right;
}
public void setRight(NodoArbolBinario<T> right) {
this.right = right;
}
}
— Nodo package lista_dinamica;
/**
* Clase Nodo
*
* @author DiscoDurodeRoer
* @param <T>
*/
public class Nodo<T> {
//Atributos
private T elemento;
private Nodo<T> siguiente; //Apunta al siguiente nodo
//Contructor
public Nodo(T elemento, Nodo<T> siguiente) {
this.elemento = elemento;
this.siguiente = siguiente;
}
//Metodos
public T getElemento() {
return elemento;
}
public void setElemento(T elemento) {
this.elemento = elemento;
}
public Nodo<T> getSiguiente() {
return siguiente;
}
public void setSiguiente(Nodo<T> siguiente) {
this.siguiente = siguiente;
}
@Override
public String toString() {
return elemento + "\n";
}
}
— ListaDinamica package lista_dinamica;
import java.util.Iterator;
/**
* Lista Dinamica Version 2.0
*
* @author DiscoDurodeRoer
* @param <T>
*/
public class ListaDinamica<T> implements Iterable<T>{
//Atributos
private Nodo<T> primero;
private Nodo<T> ultimo;
private int tamanio;
public ListaDinamica() {
primero = null;
ultimo = null;
tamanio = 0;
}
/**
* Indica si esta la lista vacia o no
*
* @return
*/
public boolean isEmpty() {
return tamanio == 0;
}
/**
* Devuelve el tamaño de la lista
*
* @return
*/
public int size() {
return tamanio;
}
/**
* Devuelve el elemento en la posicion indicada
*
* @param index
* @return
*/
public T get(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return getFirst(); //Cojo el primero
} else if (index == size() - 1) {
return getLast(); //Cojo el ultimo
} else {
//Uso la funcion getNode para coger el nodo deseado
Nodo<T> buscado = getNode(index);
return buscado.getElemento();
}
}
/**
* Devuelve el primer elemento, null si esta vacia la lista
*
* @return
*/
public T getFirst() {
//Si esta vacia, no hay primero que coger
if (isEmpty()) {
return null;
} else {
return primero.getElemento();
}
}
/**
* Devuelve el ultimo elemento, null si esta vacia la lista
*
* @return
*/
public T getLast() {
//Si esta vacia, no hay ultimo que coger
if (isEmpty()) {
return null;
} else {
return ultimo.getElemento();
}
}
/**
* Devuelve el nodo completo de una posicion concreta
*
* @param index
* @return
*/
private Nodo<T> getNode(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return primero; //devuelvo el primero
} else if (index == size() - 1) {
return ultimo; //devuelvo el ultimo
} else {
Nodo<T> buscado = primero;
//Busco el nodo deseado con un recorrido
int contador = 0;
while (contador < index) {
contador++;
buscado = buscado.getSiguiente();
}
//Me devuelve el buscado
return buscado;
}
}
/**
* Añade un elemento al final de la lista
*
* @param elemento
* @return elemento añadido
*/
public T addLast(T elemento) {
Nodo<T> aux;
//Si esta vacia, hago lo mismo que si fuera añadir el primero
if (isEmpty()) {
return addFirst(elemento);
} else {
//Hago el intercambio
aux = new Nodo<>(elemento, null);
ultimo.setSiguiente(aux);
ultimo = aux;
}
//Aumento el tamanño
tamanio++;
return ultimo.getElemento();
}
/**
* Añade el elemento al principio de la lista
*
* @param elemento
* @return elemento añadido
*/
public T addFirst(T elemento) {
Nodo<T> aux;
//si esta vacia, el nodo será el primero y ultimo
if (isEmpty()) {
aux = new Nodo<>(elemento, null);
primero = aux;
ultimo = aux;
} else {
//Hago el intercambio
Nodo<T> primeroActual = primero;
aux = new Nodo<>(elemento, primeroActual);
primero = aux;
}
//Aumento el tamanño
tamanio++;
return primero.getElemento();
}
/**
* Añade un elemento en una posicion indicada
*
* @param elemento
* @param index debe ser un indice valido
* @return elemento añadido
*/
public T add(T elemento, int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (index == 0) {
return addFirst(elemento); //Añade en la primera posicion
} else if (index == size()) {
return addLast(elemento); //añade en la ultima posicion
} else if ((index < 0 || index >= size())) {
return null;
} else {
//Cojo el anterior nodo al que estoy buscando
Nodo<T> buscado_anterior = getNode(index - 1);
//Cojo el nodo de la posicion indicada
Nodo<T> buscado_actual = getNode(index);
//Creo el nuevo novo, este apuntara al de la posicion actual
Nodo<T> aux = new Nodo<>(elemento, buscado_actual);
//el nodo anterior apunta a nuestro nuevo nodo
buscado_anterior.setSiguiente(aux);
//Aumento el tamaño
tamanio++;
return getNode(index).getElemento();
}
}
/**
* Devuelve el estado de la lista
*
* @return
*/
public String toString() {
String contenido = "";
//Si esta vacia, lo indica
if (isEmpty()) {
contenido = "Lista vacia";
} else {
Nodo<T> aux = primero;
//Recorre la lista, mostrando el contenido
while (aux != null) {
contenido += aux.toString();
aux = aux.getSiguiente();
}
}
return contenido;
}
/**
* Indica si existe el elemento indicado
*
* @param elemento
* @return
*/
public boolean exists(T elemento) {
//Si esta vacio, devuelve el false
if (isEmpty()) {
return false;
} else {
Nodo<T> aux = primero;
//Recorremos la lista
while (aux != null) {
if (elemento.equals(aux.getElemento())) { //Mejor .equals que ==
return true; //Existe
}
aux = aux.getSiguiente();
}
//Si no lo encuentra devuelve false
return false;
}
}
/**
* Indica la posición del elemento
*
* @param elemento
* @return
*/
public int indexOf(T elemento) {
//Si esta vacio, devuelvemos -1
if (isEmpty()) {
return -1;
} else {
Nodo<T> aux = primero;
int posicion = 0;
while (aux != null) {
if (elemento.equals(aux.getElemento())) { //Mejor .equals que ==
return posicion; //Existe
}
posicion++;
aux = aux.getSiguiente();
}
//Si no lo encuentra devuelve -1
return -1;
}
}
/**
* Elimina el primer elemento de la lista
*
* @return
*/
public T removeFirst() {
//Si la lista esta vacia, devolvemos null
if (isEmpty()) {
return null;
} else {
//Guardo el elemento antes
T elemento = primero.getElemento();
//Cojo el segundo
Nodo<T> aux = primero.getSiguiente();
primero = null; //Lo marco como null para el recolector
primero = aux; //Este es mi nuevo primero
//En caso de que borremos el ultimo elemento,el ultimo también
if (size() == 1) {
ultimo = null;
}
tamanio--;
return elemento;
}
}
/**
* Borra el ultimo elemento de la lista
*
* @return
*/
public T removeLast() {
if (isEmpty()) {
return null;
} else {
//Coge el elemento antes de borrar
T elemento = ultimo.getElemento();
//Cojo el penultimo
Nodo<T> aux = getNode(size() - 2);
//En caso de que sea null
//Hay 1 o dos elementos
if (aux == null) {
//marco el ultimo como nulo
ultimo = null;
//Si hay dos, el primero y el ultimo seran el mismo
//Si hay 1 elemento, significa que borramos la lista
if (size() == 2) {
ultimo = primero;
} else {
primero = null;
}
} else {
//el penultimo es el nuevo ultimo
//y le ponemos como siguiente nulo
ultimo = null;
ultimo = aux;
ultimo.setSiguiente(null);
}
tamanio--;
return elemento;
}
}
/**
* Elimina el nodo de la lista en una posicion concreta
*
* @param index
* @return
*/
public T remove(int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else if (index == 0) {
return removeFirst();
} else if (index == size() - 1) {
return removeLast();
} else {
//Cojo el nodo anterior al que quiero borrar
Nodo<T> nodo_anterior = getNode(index - 1);
//Cojo el nodo que quiero borrar
Nodo<T> nodo_actual = getNode(index);
//Cojo el elemento antes de borrar
T elemento = nodo_actual.getElemento();
//Cojo el nodo siguiente al que quiero borrar
Nodo<T> nodo_siguiente = nodo_actual.getSiguiente();
//Lo marco para borrar para el recolector
nodo_actual = null;
//El nodo anterior apunta al nodo siguiente
nodo_anterior.setSiguiente(nodo_siguiente);
tamanio--;
return elemento;
}
}
/**
* Modifico el elemento de una posicion No afecta a la estructura de la
* lista
*
* @param elemento
* @param index
* @return
*/
public T modify(T elemento, int index) {
//si esta vacio o el indice no es correcto, devuelve null
if (isEmpty() || (index < 0 || index >= size())) {
return null;
} else {
//Nodo actual
Nodo<T> aux = getNode(index);
//modifico
aux.setElemento(elemento);
return aux.getElemento();
}
}
@Override
public Iterator<T> iterator() {
return new MyIterator();
}
//Creo la clase interna MyIterator, que implementa la interfaz Iterator
private class MyIterator<ListaDinamica> implements Iterator<T>{
//Indica el siguiente elemento que se va a devolver
private int siguiente;
//Indica si hay un elemento
@Override
public boolean hasNext() {
return getNode(siguiente)!=null;
}
//Devuelve el elemento actual e incrementa al siguiente
@Override
public T next() {
T elemento = getNode(siguiente).getElemento();
siguiente++;
return elemento;
}
}
}
| |
Espero que os sea de ayuda. Si tenéis dudas, preguntad. Estamos para ayudarte.
Saludos, me gustaría sugerir una solución alternativa al problema 7, pues con la solución actual tienen que iniciar sabiendo la longitud inicial del número, con está se puede devolver el número invertido sin necesidad de saber su longitud. Saludos.
private static int invertirNum(int f, int r){
return (f < 10)? r * 10 + f : A(f/10, r*10 + f%10);
}
public static void main(String[] args) {
System.out.println(invertirNum(120003, 0));
}
El ejemplo 11 puede resumirse mas, hacerlo solo pasando el arreglo.
private static int getMax(int [] arr){
return (arr.length == 0)? Integer.MIN_VALUE :
Math.max(arr[0], getMax(Arrays.copyOfRange(arr, 1, arr.length)));
}
private static int getMin(int [] arr){
return (arr.length == 0)? Integer.MAX_VALUE :
Math.min(arr[0], getMin(Arrays.copyOfRange(arr, 1, arr.length)));
}
public static void main(String[] args) {
int []arr = new int[]{2,5,9,6,156, 3,4,7,8,1,12,68,4,3};
System.out.println(getMax(arr));
System.out.println(getMin(arr));
}
Como harían para escribir una función recursiva que reciba un número natural n e imprima los n primeros números naturales(comenzando en uno) encolumnados. Por ejemplo: para n=4 debería imprimir
1
2
3
4
Hola, vi que habia una alternativa para el ejercicio 7 para hacerlo sin la longitud del numero pero igualmente veo que hace uso de dos parámetros, acá dejo mi solución con uno solo:
public static void main(String[] args) {
int n=419;
int r=DarVuelta(n);
System.out.println(r);
}
public static int DarVuelta(int n){
int i=n,j;
if(n10){
n=n/10;
integrador++; //cuento la cantidad de ceros
}
n=i; //reestablezco el valor de N
j=(int)(Math.pow(10, integrador)); // calculo el multiplicador con 10 elevado a la cantidad de ceros
i=n%10; // extraigo el ultimo valor del actual n
i=i*j; // multiplico ese valor por la cantidad de ceros
return i+DarVuelta(n/10); // recursion
}
Solución al ejercicio 7 con solo un parametro
public static void invertirNumero(int numero){
if (numero/10 > 0){
System.out.print(numero%10);
invertirNumero(numero/10);
}else{
System.out.println(numero%10);
}
}
Buen día, disculpen me podrían ayudar con el siguiente ejercicio de Java:
Elabore un programa en Java que utilice un método recursivo para invertir una cadena de caracteres, así, por ejemplo: el usuario ingresa la palabra universidad y el método recursivo debe devolver dadisrevinu.
El método que construirá se llamará invertir, devolverá y recibirá como parámetro un String.
EL EJERCICIO 15 NO TIENE SENTIDO PUES EN UN BINARYSEARCHTREE LOS ELEMENTOS NO SE REPITEN