Stack Overflow en español Asked by user199438 on February 15, 2021
Hola amigos que tal? lo que pasa es que yo trato de imprimir las ramas del siguiente arbol
A
/ |
E L T
/ | |
B F H W
/ /
M N Y Z
y las ramas las deberia imprimir así:
1. A, E, B
2. A, E, F, M
3. A, E, F, N
4. A, E, H
5. A, L
6. A, T, W, Y
7. A, T, W, Z
pero a mi me salen cosas muy locas y ya no se que hacer
ademas de que después tengo que hacer un recorrido por niveles donde debería de quedarme así:
A, E, L, T, B, F, H, W, M, N, Y, Z
pero yo solo consigo sacarlos asi :
A,E,L,T,B,F,H,M,N,W,Y,Z
A continuación adjunto mi codigo para ver si alguien me puede ayudar. Cuando imprimo las ramas me salen así:
A
E
B
------------------
A
E
B
F
M
------------------
A
E
B
F
M
N
------------------
A
E
B
F
M
N
------------------
A
E
B
F
M
N
H
------------------
A
E
B
F
M
N
H
------------------
A
E
B
F
M
N
H
L
------------------
A
E
B
F
M
N
H
L
T
W
Y
------------------
A
E
B
F
M
N
H
L
T
W
Y
Z
------------------
A
E
B
F
M
N
H
L
T
W
Y
Z
------------------
A
E
B
F
M
N
H
L
T
W
Y
Z
------------------
A
E
B
F
M
N
H
L
T
W
Y
Z
------------------
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
public class Test {
public static <T> void main(String[] args) {
ArrayList<ArrayList<Nodo<T>>> ContenedorAux = new ArrayList<ArrayList<Nodo<T>>>();
Archivo objArchivo = new Archivo();
ArrayList<String[]> lineas;
ArbolNArio<T> miArbol = new ArbolNArio<T>();
lineas = objArchivo.leerArchivo();
String raiz;
// 1. Decido si es un arbol de caracteres o de numeros
String decicion = lineas.get(0)[0];// ? que se debe hacer?
// 2. la segunda línea será la raíz
raiz = lineas.get(1)[0];
miArbol.insertarRaiz(raiz);
// 3. insertar el segundo elemento
// el primer elemento será el padre donde insertaré al hijo
for (int i = 2; i < lineas.size(); i++) {
String[] linea = lineas.get(i);
// línea en 0 es el padre, linea en 1 el elemento a insertar en el arbol
miArbol.instertar(linea[0], linea[1]);
}
ContenedorAux = miArbol.RamasArbol();
for (int i = 0; i < ContenedorAux.size(); i++) {
for (int j = 0; j < ContenedorAux.get(i).size(); j++) {
System.out.println(ContenedorAux.get(i).get(j).getElemento());
}
System.out.println("------------------");
}
//miArbol.recorrer();
//miArbol.RetornarNodosNivel(2);
//miArbol.PodarArbol(1);
miArbol.recorreranchura();
//System.out.println(miArbol.altura());
}
}
class Nodo<T> {
private T elemento;
private ArrayList<Nodo<T>> hijos;
public Nodo(T elemento) {
this.elemento = elemento;
this.hijos = new ArrayList<Nodo<T>>();
}
public Nodo(Nodo<T> nodo) {
this.elemento = nodo.getElemento();
this.hijos = new ArrayList<Nodo<T>>();
}
public T getElemento() {
return elemento;
}
public void setElemento(T elemento) {
this.elemento = elemento;
}
public ArrayList<Nodo<T>> getHijos() {
return hijos;
}
public void setHijos(ArrayList<Nodo<T>> hijos) {
this.hijos = hijos;
}
public void agregarHijo(Nodo<T> hijo) {
hijos.add(hijo);
}
}
class ArbolNArio<T> {
private Nodo<T> raiz;
public ArbolNArio() {
this.raiz = null;
}
public Nodo<T> getRaiz() {
return raiz;
}
public void setRaiz(Nodo<T> raiz) {
this.raiz = raiz;
}
public void insertarRaiz(Comparable elemento) {
insertar(raiz, null, elemento);
}
public void instertar(Comparable posicion, Comparable elemento) {
insertar(raiz, posicion, elemento);
}
private void insertar(Nodo<T> arbol, Comparable posicion, Comparable elemento) {
Nodo<T> nuevoNodo = new Nodo(elemento);
if (raiz == null) {
raiz = nuevoNodo;//VERIFICA SI EL ARBOL ESTÁ VACIO, SI LO ESTÁ SE CREA UN ARBOL CON RAIZ ELEMENTO
} else {
if (posicion.equals(arbol.getElemento())) {
arbol.agregarHijo(nuevoNodo);//VERIFICA SI LA POSICION INGRESADA ES IGUAL AL NODO ACTUAL
} else {
//SI NO ES ASI, ENTRARÁ A CADA UNO DE LOS HIJOS DEL NODO ACTUAL A COMPARAR
for (int i = 0; i < arbol.getHijos().size(); i++) {
if (posicion.equals(arbol.getHijos().get(i).getElemento())) {
arbol.getHijos().get(i).agregarHijo(nuevoNodo);//AQUI PREGUNTO SI LA POSICION ES IGUAL A UNO DE LOS HIJOS DE LA RAIZ Y SI ES ASI INGRESE UN NUEVO HIJO A ESE HIJO
} else {
insertar(arbol.getHijos().get(i), posicion, elemento);//SINO ES ASI VOLVERA A INGRESAR EN CADA UNO DE LOS NODOS HIJOS DE ESE NODO
}
}
}
}
}
public void recorrer() {
recorrer(raiz);
}
public void recorrer(Nodo<T> NODO) {
System.out.println(NODO.getElemento());
for (int i = 0; i < NODO.getHijos().size(); i++) {
recorrer(NODO.getHijos().get(i));
}
}
private void RetornarNodosNivel(Nodo<T> arbol, int nivel, int nivelopcional) {
//segunda version con mejoras
ArrayList<Nodo<T>> Nodos = new ArrayList<Nodo<T>>();
if (arbol != null) {
if (nivel == nivelopcional) {
Nodos.add(arbol);
}
for (int i = 0; i < arbol.getHijos().size(); i++) {
RetornarNodosNivel(arbol.getHijos().get(i), nivel + 1, nivelopcional);
}
for (int i = 0; i < Nodos.size(); i++) {
System.out.print(Nodos.get(i).getElemento() + " ");
}
//primera version
/*if(nivel==nivelopcional)
{
if(nivel==0)
{
System.out.println("es el nivel de la raiz y la raiz es: "+arbol.getElemento());
}
else
{
System.out.print(arbol.getElemento()+",");
}
}
for (int i = 0; i < arbol.getHijos().size(); i++)
{
RetornarNodosNivel( arbol.getHijos().get(i), nivel+1, nivelopcional);
} */
}
}
public void RetornarNodosNivel(int nivelopcional) {
int aux = 0;
aux = altura() - 1;
if (nivelopcional <= aux) {
System.out.println("los nodos son en el nivel: " + nivelopcional + " son:");
RetornarNodosNivel(raiz, 0, nivelopcional);
} else {
System.out.println("ese nivel no existe en el arbol");
}
}
private int altura(Nodo<T> arbol) {
int mayor = 0, aux = 0;
if (arbol == null) {
return 0;
} else {
for (int i = 0; i < arbol.getHijos().size(); i++) {
aux = altura(arbol.getHijos().get(i));
if (aux > mayor) {
mayor = aux;
}
}
return mayor + 1;
}
}
private int altura() {
return altura(raiz);
}
public void recorreranchura(Nodo<T> arbol, int nivel) {
if (nivel == 0) {
System.out.println(nivel + "" + arbol.getElemento());
for (int i = 0; i < arbol.getHijos().size(); i++) {
System.out.println(nivel + 1 + "" + arbol.getHijos().get(i).getElemento());
}
} else {
if (nivel == altura() - 2)
for (int i = 0; i < arbol.getHijos().size(); i++) {
System.out.println(nivel + 1 + "" + arbol.getHijos().get(i).getElemento());
}
else
for (int i = 0; i < arbol.getHijos().size(); i++) {
System.out.println(nivel + 1 + "" + arbol.getHijos().get(i).getElemento());
}
}
for (int i = 0; i < arbol.getHijos().size(); i++) {
recorreranchura(arbol.getHijos().get(i), nivel + 1);
}
}
public void recorreranchura() {
recorreranchura(raiz, 0);
}
private void PodarArbol(Nodo<T> arbol, int nivel, int nivelopcional) {
if (arbol != null) {
if (nivel == nivelopcional) {
arbol.getHijos().clear();
}
for (int i = 0; i < arbol.getHijos().size(); i++) {
PodarArbol(arbol.getHijos().get(i), nivel + 1, nivelopcional);
}
}
}
public void PodarArbol(int nivelopcional) {
int aux = 0;
aux = altura() - 1;
if (nivelopcional <= aux) {
if (nivelopcional == 0) {
System.out.println("No se puede realizar esta acción ya que se eliminará el arbol");
} else {
PodarArbol(raiz, 0, nivelopcional - 1);
}
} else {
System.out.println("ese nivel no existe en el arbol");
}
}
private ArrayList<Nodo<T>> copiar(ArrayList<Nodo<T>> NodosCopia) {
ArrayList<Nodo<T>> lista = new ArrayList<Nodo<T>>();
for (Nodo<T> nodo : NodosCopia)
lista.add(new Nodo<T>(nodo));
return lista;
}
/*private void Camino(Nodo<T> arbol, ArrayList<Nodo<T>> camino,ArrayList<ArrayList<Nodo<T>>> rutas)
{
if (camino == null)
{
return;
}
camino.add(arbol);
if (arbol.getHijos().size() == 0)
{
rutas.add(copiar(camino));
}
for (Nodo<T> hijo : arbol.getHijos())
Camino(hijo, camino, rutas);
}
public ArrayList<ArrayList<Nodo<T>>> RamasArbol()
{
ArrayList<ArrayList<Nodo<T>>> rutas = new ArrayList<ArrayList<Nodo<T>>>();
ArrayList<Nodo<T>> camino = new ArrayList<Nodo<T>>();
Camino(raiz, camino, rutas);
return rutas;
}*/
public void camino(Nodo<T> arbol, ArrayList<Nodo<T>> camino, ArrayList<ArrayList<Nodo<T>>> rutas) {
if (arbol != null) {
/*if(arbol.getHijos().size()<=0)
{
camino.add(arbol);
}
else
{
rutas.add(copiar(camino));
}*/
camino.add(arbol);
for (int i = 0; i < arbol.getHijos().size(); i++) {
camino(arbol.getHijos().get(i), camino, rutas);
}
rutas.add(copiar(camino));
}
}
public ArrayList<ArrayList<Nodo<T>>> RamasArbol() {
ArrayList<ArrayList<Nodo<T>>> rutas = new ArrayList<ArrayList<Nodo<T>>>();
ArrayList<Nodo<T>> camino = new ArrayList<Nodo<T>>();
camino(raiz, camino, rutas);
return rutas;
}
}
class Archivo {
private File archivo;
private BufferedReader archivoEntrada;
public Archivo() {
archivo = new File("src\\DocumentoPrueba.txt");
if (archivo.exists() == false) {
try {
archivo.createNewFile();
} catch (IOException e) {
e.printStackTrace();
}
}
}
public void Archivo2() {
try {
archivoEntrada = new BufferedReader(new FileReader("src\DocumentoPrueba.txt"));
} catch (IOException e) {
e.printStackTrace();
}
}
public ArrayList<String[]> leerArchivo() {
String lineaArchivo = "";
String[] lineaPartida = null;
ArrayList<String[]> lineas = new ArrayList<String[]>();
try {
archivoEntrada = new BufferedReader(new FileReader(archivo));
while (lineaArchivo != null) {
lineaArchivo = archivoEntrada.readLine();
if (lineaArchivo != null) {
lineaPartida = lineaArchivo.split("-");
lineas.add(lineaPartida);
}
}
archivoEntrada.close();
} catch (Exception e) {
System.out.println("¡Ha ocurrido un error!");
e.getMessage();
}
return lineas;
}
}
Código para mostrar las ramas:
public void mostrarRamas() {
// lista para guardar los valores de los de la rama
List<T> rama = new ArrayList<>();
// agregar el valor de la raiz
rama.add(raiz.getElemento());
mostrarRamas(raiz, rama);
}
private void mostrarRamas(Nodo<T> nodo, List<T> rama) {
// si el nodo no tiene hijos imprimir la colección de valores
if (nodo.getHijos().isEmpty()) {
System.out.println(rama);
}
// recorrer los hijos del nodo
for (Nodo<T> n : nodo.getHijos()) {
// agregar el valor del nodo a la lista
rama.add(n.getElemento());
// llamada recursiva
mostrarRamas(n, rama);
// retirar el ultimo valor insertado
rama.remove(rama.size() - 1);
}
}
Código para mostrar los niveles:
public void recorrerNiveles() {
// lista para guardar los valores de los nodos
List<T> valores = new ArrayList<>();
// agregar el valor de la raíz
valores.add(raiz.getElemento());
// iterar desde 1 hasta altura - 1
// altura - 1 porque si el arbol tiene altura 4 solo se
// necesitan 3 niveles porque la raiz ya está incluida
for (int i = 1; i < altura(); i++) {
// llamda recursiva para bajar un nivel
recorrerNiveles(raiz, i - 1, valores);
}
System.out.println(valores);
}
private void recorrerNiveles(Nodo<T> nodo, int nivel, List<T> valores) {
// iterar los hijos del nodo
for (Nodo<T> n : nodo.getHijos()) {
// si ya se llegó al nivel 0 agregar los valores a la lista
if (nivel == 0)
valores.add(n.getElemento());
else // seguir bajando de nivel hasta llegar al nivel cero
recorrerNiveles(n, nivel - 1, valores);
}
}
Esos métodos son de la clase ArbolNArio
.
Correct answer by Lobos on February 15, 2021
Si te fijas tu problema es que se imprimen antes los nodos de niveles inferiores que los del mismo nivel. Quizá un método auxiliar que te seleccionase los nodos por niveles te resultaría de ayuda:
public void getNodesForLevel(int level, int desiredLevel, Nodo<T> arbol, List<Nodo<T>> listaDeNodos){
if(level < desiredLevel){
for (int i = 0; i < arbol.getHijos().size(); i++) {
getNodesForLevel(level + 1, desiredLevel, arbol.getHijos().get(i));
}
}
else{
listaDeNodos.add(arbol.getRaiz());
}
}
}
Answered by Alvaro Maleno Alferez on February 15, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP