Generic Tree, how to do?

Question

Generic Tree, how to do?

Navigation

#1 by (12 votes)

9

I'm trying to mount a Generic Tree in java to mount a Boolean expression inside a genetic expression algorithm, this tree would store several types of variables, I'm not sure which is the most optimized way to do this, I was thinking of saving logical operators as && , || in strings and also the mathematical operators + , - , / , * . Operators would be stored in the root / branch nodes and operands that could be functions or variables would be stored in terminal nodes (sheets), does anyone have any ideas? I spent the day in this problem and I'm a bit frustrated.

public class ArvoreJava {    
   public static No raiz; // o único campo de dado em Arvore    


   public ArvoreJava() { // construtor    
     raiz = null;  //nenhum nó na arvore    
   }   
public static No insere(String palavra, No no) {  //metodo insere  

        if(no == null){  
            no = new No(palavra);  //se nao existir nó cria um novo  
        }  

        else if((compare(palavra, no.palavra)) < 0){ // faz comparação, se palavra  
            no.filhoEsquerda = ArvoreJava.insere( palavra , no.filhoEsquerda);// menor que nó, insere na esquerda  
        }  
        else if((compare(palavra, no.palavra)) > 0){//se palavra maior que nó, insere na direita  
           no.filhoDireita = ArvoreJava.insere(no.palavra, no.filhoDireita);  
        }  
        else{// senão, palavra já contem  
            System.out.println("ERRO: valor já existe na árvore.");  
            return null;  
        }  

        return no;  

}  
public static void caminhando(ArvoreJava arv){//caminha na arvore   
                System.out.println("Pré-ordem: ");  
        arv.preordem(arv.raiz);  

}  
public static int compare(String palavra, String no){ // compara strings e retorna um inteiro  
     return palavra.toString().compareTo(no.toString());//-1 menor, 1 maior, 0 iguais  
}  


        public  void preordem(No no)    {//caminha em preordem  
            if (no == null){  
        return;  
        }  
    System.out.println(no.palavra);  
    preordem(no.filhoEsquerda);  
    preordem(no.filhoDireita);  
    }  


}

And the node class.

package arvore;  

public class No {  

     String palavra;    //dado  
     No filhoEsquerda; //cria filho  a esquerda  
     No filhoDireita;  // cria filho a direita  

    public No(String palavra){  
        this.palavra = palavra;  
    }  

     public void mostraNo(){     
       {     

             System.out.print(palavra);     
             System.out.print(", ");     

        }     
     }     
   }

That is, what I would know to implement is very simple, but in personal design I need to implement a structure with these characteristics or close to them to get close to some satisfactory result. Anyone who has the patience to try to help, I thank you right away.

java

asked by anonymous 03.07.2014 / 23:13

1 answer

Customize comparison between javascript objects Increasing and decreasing ordering in ClientDataSet

score 12 · Accepted Answer

First, if you need to save different types in a data structure, you must define a supertype for all of them. For example, instead of your node being a class, make it a generic interface:

interface No<T> {
    T avaliar();
}

Then you can define your nodes so that they implement this interface, but each one giving a slightly different implementation:

class FolhaNumerica implements No<Double> {
    double valor;
    Double avaliar() { return valor; }
}

class FolhaBooleana implements No<Boolean> {
    boolean valor;
    Boolean avaliar() { return valor; }
}

For operators, my suggestion is to use classes or enumerations to represent them (classes if you predict they will / can change a lot, enumerations if they are more or less fixed). That way you not only represent them, but you can also do something useful with them:

interface Operador<E,S> {
    S aplicar(E[] operandos);
    Class<E> obterClasseOperandos(); // Workaround para uma limitação nos tipos genéricos
}

class Soma implements Operador<Double,Double> {
    String toString() { return "+"; }
    Double aplicar(Double[] operandos) {
        double ret = 0;
        for ( Double d : operandos )
            ret += d;
        return ret;
    }
    Class<Double> obterClasseOperandos() { return Double.class; }
}

class Conjuncao implements Operador<Boolean,Boolean> {
    String toString() { return "&&"; }
    Boolean aplicar(Boolean[] operandos) {
        for ( Boolean b : operandos )
            if ( !b )
                return false;
        return true;
    }
    Class<Boolean> obterClasseOperandos() { return Boolean.class; }
}

class Igualdade implements Operador<Double,Boolean> {
    String toString() { return "=="; }
    Boolean aplicar(Double[] operandos) {
        double primeiro = operandos[0];
        for ( Double d : operandos )
            if ( d != primeiro )
                return false;
        return true;
    }
    Class<Double> obterClasseOperandos() { return Double.class; }
}

(Note: instead of having unary and binary operators, I made all operators accept a variable number of arguments, for simplicity)

Finally, you can create a class also generic to represent the branches / root:

class Galho<E,S> implements No<S> {
    Operador<E,S> op;
    No<E>[] operandos;

    S avaliar() {
        @SuppressWarnings("unchecked")
        E[] array = (E[])Array.newInstance(op.obterClasseOperandos(), operandos.length);
        for ( int i = 0 ; i < array.length ; i++ )
            array[i] = operandos[i].avaliar(); // Avalia cada sub-nó recursivamente

        return op.aplicar(array); // Passa os resultados para o operador
    }
}

In this way, you can mount the tree you want:

// (4 == 2 + 2) && true
No<Double> mais = new Galho<Double,Double>(new Soma(), new FolhaNumerica(2), new FolhaNumerica(2))
No<Boolean> igual = new Galho<Double,Boolean>(new Igualdade(), new FolhaNumerica(4), mais);
No<Boolean> raiz = new Galho<Boolean,Boolean>(new Conjuncao(), igual, new FolhaBooleana(true));

boolean resultado = raiz.avaliar(); // true

Example in ideone . Source code for creating a generic array: this answer in SOen .

This is just an example. If you find it necessary, you can create more types of sheets (even a generic type Folha<T> with T valor ), more types of operators (I think it does not even make sense to subtract with more than 2 operands), more types of branches, etc.

Note: In my answer, I omitted the constructors, modifiers, and some generic types so the code does not get too long. The example in ideone fills in the gaps.