TransWikia.com

Imprimir cada una de las ramas y hacer un recorrido por niveles de un arbol n-ario

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;
    }


}

2 Answers

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP