Arquivo Discussoes de Programacao e Tecnologia 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.
Rapaiz, se você nunca se deparou com uma situação dessas e ainda quer trabalhar com desenvolvimento, corra para fazer a sua faculdade… 
Uma dica: pesquise sobre árvores binárias e seus algoritmos de caminho entre os nós…
[]'s.
: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.
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();
}
}
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.