[Java] Modifica albero binario

[andra_zx]

Buonasera a tutti, dovrei scrivere un algoritmo in java che: dato un albero binario proprio e la sua sequenza con la visita in-order, venga modificato in modo tale da avere una sequenza con la visita in-order: uguale alla precedente, ma shiftata di uno a sinistra. L'albero l' ho implementato con una lista concatenata, c' ho fatto il suo bell' iteratore, ma non riesco ad avere lo spunto per sceivere questo algoritmo, sapreste dari un' idea ?

Grazie a tutti..

[hamming_burst]

Adoro questo genere di problemi

Solo una cosa prima che non mi è chiaro. Cosa intendi di shiftato a sinistra? Che elemento deve essere spostato? fammi un esempio esplicito.

[andra_zx]

Un esempio: se la sequenza dopo la visita in-Order è ABCDE, si dovrà shiftare ottenendo: BCDEA.
Comunque ho avuto un' idea: potrei applicare la visita in order, poi la stringa ottenuta la modifica appositamente in modo da renderla "shiftata". Poi salvo i vari valori in un array. ED infine scrivo il nuovo metodo per la modifica dell' albero semplicemente ricopiando quello per la visita in order, ma invece dei comandi per leggere il contenuto del nodo, scrivo di copiarci dentro il nuovo valore salvato nell' array.

Tu cosa ne dici ?

P.S. inoltre vorrei scrivere personalmente l' algoritmo di visita in.order in maniera iterativa, per non essere la banale ricorsione, ma vedo che è piuttosto impossibile..XD è proprio così impossibile o sono io incapace ?

P.P.S. Un altra domanda visto che ci sei.. ho provato a scrivere l' algoritmo di visita in manierea ricorsiva, ma ho un problema con la concatenazione delle stringhe: non si concatenano. Il codice che ho scritto è:

private void visitInorder(BTNode n, String s) {

        if (n.left == null && n.right == null) 
            s = s + n.key;
        
        else {
            if (n.left != null) 
               visitInorder(n.left, ss);
            
            else 
               s = s + n.key;
           
	         if (n.right != null) 
                   visitInorder(n.right, s);
         
	    }
    }

[apatriarca]

Io l'avrei implementato nel seguente modo. Dovrebbe funzionare anche se è da tanto che non programmo in Java e quindi potrebbero esserci degli errori.

private void visitInorder(BTNode n, String s) {

    if (s == null) { // verifica che la stringa non sia nulla
        s = "";
    }

    if (n.left != null) {
        visitInorder(n.left, s); // visita albero sinistro
    }

    s += n.key; // aggiungo valore del nodo

    if (n.right != null) {
        visitInorder(n.right, s); // visita albero destro
    }
}

Ti consiglio di scrivere il codice in modo più ordinato. E' più facile riuscire a seguire bene il flusso delle istruzioni.

Per scrivere questa funzione in modo iterativo è necessario tenere traccia di tutti i nodi visitati. E' possibile ma non credo ci sarebbero grossi vantaggi rispetto alla versione ricorsiva: il codice sarebbe più complicato e le performance sarebbero probabilmente molto simili.

P.S. La trasformazione da ABCDE a BCDEA è una rotazione e non uno shift...

[andra_zx]

ah capisco.. il problema è che proprio non mi si concatenano i valori di nodi.. In internet ho trovato un metodo praticamente identico, ma che invece delle stringhe utilizza uno StringBuffer, e concatena le varie parti con il metodo append(). Ed effettivamente questo funziona.

Più che altro è sorto un nuovo problema: non ricordo come convertire in valori Int, cioè che è scritto in una stringa, qualora sia presente un numero.
Ho provato a scrivere:

Object [] nodeValue = new Object [n];
		for(int i = 0; i < n; i++){
			Object obj = s.charAt(i);
			if(obj instanceof Integer)
				nodeValue [i] = obj;
			}

cioè prendo un carattere della stringa s, e con il comando instanceof verifico che sia un integer, in caso affermativo si salva nell' array il valore scritto in s.
Il problema è che quel controllo fallisce sempre. Come mai ?

[apatriarca]

La funzione Integer.parseInt() dovrebbe convertire da String a int.

[andra_zx]

"apatriarca":La funzione Integer.parseInt() dovrebbe convertire da String a int.

ah giusto, grazie mille!! avevo proprio dimenticato questo metodo..

[andra_zx]

Scusate per il doppio posto, ma mi sembrava corretto conitnuare la discussione in questo topic. Nella realizzazionedi questo programma, mi sono imbattuto in nuovo problema: per concludere il programma dovrei inserire i dati nelle nuove posizioni dell' albero, per farlo ho salvato i valori in array e poi, applicando una nuova visita in oder, li dovrei copiare nei nodi corretti.

Ho scritto:

public void newInorderVisit(Object[] obj){
	int i = 0;                      //indice per scorrere l' array
	if (root != null)
	shiftTree(root, obj, i);	
}
	
private void shiftTree(BTNode n, Object [] value, int i) {
	
	if(n.left != null){
	shiftTree(n.left, value, i);
	}
	
	n.key = value[i];    // qui al posto della visita, copio il valore della cella dell' array nel nodo
	i++;                      //ed aggiorno l' indice 
		
	if(n.right != null){
	shiftTree(n.right, value, i);
			
	}
}

In via teorica non ci sono problemi, ma nella realtà non funziona per nulla, credo ci sia un problema con l' aggiornamento dell' indice, perchè inizialmente ho la sequenza 7965123, poi dovre avere 9651237, invece ho 9969696.

Qual è la causa di questo problema ??
e comunque qualcuno potrebbe farmi chiarezza sul come mai la visita ricorsiva non mi resistuisce nulla se concateno stringhe ? ed invece usando un elemento stringbuffer la cosa funziona ?

Grazue a tutti..