Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: Vivynz on 20-05-2009, 09:48:29



Title: BT con chiavi ripetute..
Post by: Vivynz on 20-05-2009, 09:48:29
abbiamo visto il codice per inserimento, ricerca ecc ecc per gli alberi binari di ricerca...ma se invece la struttura dovesse essere un albero binario con chiavi ripetute???come fare??quali metodi modificare e come?chiedo perchè ci sono esercizi che richiedono questo tipo di struttura..


Title: Re:BT con chiavi ripetute..
Post by: Bart46 on 20-05-2009, 10:01:16
non vorrei sbagliare... ma credo che basti eliminare nell'insierimento la condizione
"if(val==p.visit())"

dove val è il valore che passiamo e che bisognerebbe inserire...


ripeto spero di non sbagliare  :-ciao


Title: Re:BT con chiavi ripetute..
Post by: k1r4 on 20-05-2009, 10:06:43
si dovrebbe modificare il metodo di inserimento:

Code:
    private BTNode insert(int val, BTNode p) {
        if (p == null) {
            p = new BTNode(val);
        } else {
            if (val < p.key) {
                p.left = insert(val, p.left);
            } else {
                if (val > p.key) {
                    p.right = insert(val, p.right);
                } else {
                    // E' un duplicato
                }
            }
        }
        return p;
    }

modificando queste condizioni:

if (val < p.key)                -->      if(val<=p.key)

if(val > p.key)                 -->      if(val>=p.key)

almeno credo .smile