[JAVA] Ricerca tra i nodi di un albero binario

[x3d0]

Premetto che non posso utilizzare Java Collection o altri framework

Questa è la classe che definisce il nodo

Codice PHP:

public class NodoBin {
    String info;
    NodoBin sin;
    NodoBin des;

    public NodoBin(String i, NodoBin s, NodoBin d) {
        this.info = i;
        this.sin = s;
        this.des = d;
    }
} 


Questo è il codice della creazione di una lista di nodi dell'albero

Codice PHP:

String s1 = "Giovanni";
        String s2 = "Maria";
        String s3 = "Marco";
        String s4 = "Sergio";
        String s5 = "Giulia";
        String s6 = "Marta";

        // Creazione nodi
        NodoBin n1 = new NodoBin(s1, null, null);
        NodoBin n2 = new NodoBin(s2, null, null);
        NodoBin n3 = new NodoBin(s3, null, null);
        NodoBin n4 = new NodoBin(s4, null, null);
        NodoBin n5 = new NodoBin(s5, null, null);
        NodoBin n6 = new NodoBin(s6, null, null);

        // Creazione albero
        n1.sin = n2;
        n1.des = n3;
        n2.sin = n4;
        n2.des = n5;
        n3.des = n6; 


Devo scrivere un metodo "cerca", che esegue la ricerca di un elemento in un albero binario di oggetti della classe NodoBin.
In particolare, il metodo "cerca" riceve in ingresso il riferimento alla radice dell'albero e una stringa
x. Qualora il campo info di un nodo dell'albero abbia valore uguale a quello della stringa x, il metodo restituisce il riferimento a tale nodo, altrimenti esso restituisce null (per semplicità tutti i nodi dell'albero abbiano valori di versi del campo info).


Ho iniziato a scrivere il metodo "cerca", ma non riesco a capire come renderlo ricorsivo per tutti i nodi

Codice PHP:

public static NodoBin cerca(NodoBin r, String s)
    {
        if(r == null)
        {
            return null;
        }
        
        if(r.info.equals(s))
        {
            return r;
        }else{
            return null;
        }
        
    } 


Il problema è che in questo modo non esamino nè r.sin, nè r.des, e di conseguenza tutti i nodi figli!

[Mixmar]

Nel secondo "else", puoi ispezionare sia il ramo sinistro, che quello destro, semplicemente invocando di nuovo la funzione su "r.sin" e "r.des". Poi ritorni null se entrambi i risultati sono null, altrimenti ritorna quello che non è null.

[x3d0]

Originariamente inviato da Mixmar

Nel secondo "else", puoi ispezionare sia il ramo sinistro, che quello destro, semplicemente invocando di nuovo la funzione su "r.sin" e "r.des". Poi ritorni null se entrambi i risultati sono null, altrimenti ritorna quello che non è null.

Ok, e se volessi ripeterlo ricorsivamente su tutti i sotto-nodi della radice "r".
Potresti scrivermi concretamente il pezzo di codice?

[clockover]

Procedi in questo modo
1) se il nodo parametro == null ritorni null
2) chiave == stringa ritorni il nodo parametro
3) se la chiamata ricorsiva al nodo sinistro ha come risultato != null ritorni il risultato
4) se la chiamata ricorsiva precedente ha avuto risultato null effettui la chiamata ricorsiva al nodo destro. Se la chiamata ha come risultato un valore != null ritorni il risultato altrimenti ritorni null

Dove nodo parametro è nella tua funzione postata prima NodoBin r