[RESOLVIDO] Imprimir árvore com recursão

Programação Java
#1

Olá galera, recentemente participei de uma seleção em uma empresa que possui como foco a evolução de sistemas legados.

Eles aplicaram o seguinte teste:

Observe a seguinte estrutura:-

  1
 / \

2 3
/ \
4 5 6

Elabore um algoritmo que armazene esta estrutura e através de um método recursivo imprima-a.

Não consegui resolver, pois nunca me deparei com um problema desses e, desde então venho pesquisando uma solução.

Agradeço a atenção!
Obrigado.

#2

Rapaiz, se você nunca se deparou com uma situação dessas e ainda quer trabalhar com desenvolvimento, corra para fazer a sua faculdade… :stuck_out_tongue:
Uma dica: pesquise sobre árvores binárias e seus algoritmos de caminho entre os nós…

[]'s.

#3

:oops: Então acho que devo desistir dessa idéia pois não tenho condições de fazer uma faculdade e o pouco que aprendi foi com o Google e em alguns livros que consegui.

#4

Depois de uma pesquisa no livro do deitel e algum tempo raciocinando acho que encontrei uma solução.

Segue:

AdvancedTree.java


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package com.wordpress.sivoleu;

import java.util.ArrayList;
import java.util.List;


/**
 *
 * @author Clovis Terruel
 */

public class AdvancedTree {

    private AdvancedTreeNode root;

    public AdvancedTree() {

        root = null;
        
    }

    public synchronized void insertNode( int node, int value ) {

        if ( root == null )
           root = new AdvancedTreeNode(  node );

        else
           root.insertValue( node, value );
    }

    public synchronized void printInPreorder() {

        printInPreorderHelper( root );

    }

    private void printInPreorderHelper(AdvancedTreeNode node) {

        if (node == null)
            return;

        System.out.println("\nPai: " + node.data);
        
        if (node.atreeNode.size() != 0) {
            for (int i = 0; i <= node.atreeNode.size() -1 ; i++) {
                System.out.println("Filho: " + node.atreeNode.get(i).data);
            }
        } else System.out.println("Filho: Não possui Filho(s)");
        

        for (int i = 0; i <= node.atreeNode.size() -1 ; i++) {
            printInPreorderHelper(node.atreeNode.get(i));
        }
    }
}
class AdvancedTreeNode {

    int data;
    List<AdvancedTreeNode> atreeNode;

    public AdvancedTreeNode (int nodeValue ) {

        data = nodeValue;
        atreeNode = new ArrayList<AdvancedTreeNode>();
    }

    public synchronized void insertValue( int node, int value ) {

        if (this.data == node) {
            AdvancedTreeNode aTreeNodeE = new AdvancedTreeNode(value);
            atreeNode.add(aTreeNodeE);
        }
        else {
            for (int i = 0; i <= atreeNode.size() - 1; i++) {
                    atreeNode.get(i).insertValue(node, value);
            }
        }

    }

}

Teste:

AdvancedTreeTest.java


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package com.wordpress.sivoleu;

import javax.swing.JOptionPane;

/**
 *
 * @author Clovis Terruel
 *
 * 
 *
 */
public class AdvancedTreeTest {

    public static void main( String args[] )
   {
      AdvancedTree tree = new AdvancedTree();

      System.out.println( "Inserting the following values: " );

      int array1[] = new int [8];
      int array2[] = new int [8];
      
      for ( int i = 0; i <= 7; i++ ) {
        
         String input1 = JOptionPane.showInputDialog("Digite 1 inteiro maior que zero");
         array1[i] = Integer.parseInt(input1);

         String input2 = JOptionPane.showInputDialog("Digite 1 inteiro maior que zero");
         array2[i] = Integer.parseInt(input2);
         
         System.out.println( input1 + " " + input2);

        tree.insertNode( array1[i], array2[i] );

      }

      System.out.println ( "\n\nImprimindo árvore em pré-ordem" );
      
      tree.printInPreorder();

   }

}
#5

Tá quase lá.
Antes de entender arvore binária tem que entender arvore (Tree)

Vc chegou no conceito. A arvore é um encadeamento de nós. Um nó tem um conjunto de nós. ( è aqui que está a recursividade edida no enunciado).
A sacada é que a arvore não existe e apenas nós existem. Portanto só precisa implementar um classe.
O resto é programação simples.

Experimente generalizar o seu tree. Permita que use qq Object no estilo de List ou Map.
Algo assim

public class TreeNode<T> {

      public void addNode(TreeNode<T> n)
      public void removeNode(TreeNode<T> n)
      public set(T obj)
      public T get()

}

Depois compare com javax.swing.tree.TreeNode

Para ver o que pode melhorar.
Depois vc pode pesquisar sobre arvore binária.

só um adendo : System.out.print dentro de tree é proibido. Faça a logica de print fora do treeNode.

#6