Pages: [1] 2   Go Down
Print
Author Topic: Alberi e metodi  (Read 6746 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« on: 25-04-2009, 11:30:21 »

Ragazzi non ho ben capito l'uso dei metodi degli alberi per ricercare , inserire e cancellare , qualcuno mi potrebbe fare un esempio? Oppure mi puo fare sapere come ha creato i metodi di inserimento , ricerca e cancella?

E per caso dobbiamo implementare anche le funzioni e i metodi delle liste e dei nodi?

e poi non ho capito una cosa.. key è l'indice o il valore a numero intero contenuto nel nodo?
« Last Edit: 25-04-2009, 14:38:03 by Alex_47 » Logged
rox
Forumista
***
Offline Offline

Posts: 633


« Reply #1 on: 27-04-2009, 16:52:16 »

Ragazzi non ho ben capito l'uso dei metodi degli alberi per ricercare , inserire e cancellare , qualcuno mi potrebbe fare un esempio? Oppure mi puo fare sapere come ha creato i metodi di inserimento , ricerca e cancella?

E per caso dobbiamo implementare anche le funzioni e i metodi delle liste e dei nodi?

e poi non ho capito una cosa.. key è l'indice o il valore a numero intero contenuto nel nodo?
Logged

Una macchina è in grado di lavorare come cinquanta uomini comuni, ma nessuna macchina può svolgere il lavoro di un uomo straordinario.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #2 on: 27-04-2009, 17:14:43 »

Ragazzi ho studiato alberi e nodi da un libro che avevo alle superiori ed ho capito un pò di cose , entro domani posterò le classi albero e nodi con il programma che fa inserimento,controllo e cancella!
Logged
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #3 on: 27-04-2009, 18:09:36 »

Questa è la mia implementazione... Gestrisco solo la visita e l'inserimento.
L'inserimento è fatto sia in maniera ricorsiva che no... Spero vi aiuti
Code:
public class Test {
public static void main(String[] arg) {
BT prova = new BT();
prova.insertRic(2);
prova.insertRic(10);
prova.insertRic(53);
prova.insertRic(4);
prova.preOrd();
}
}

class BTNode {
private int key;
private BTNode left;
private BTNode right;

public BTNode(int _key) {
this(_key, null, null);
}
public BTNode(int _key, BTNode _left, BTNode _right) {
key = _key;
left = _left;
right = _right;
}

public int getKey() { return key; }
public BTNode getLeft() { return left; }
public BTNode getRight() { return right; }

public void setKey(int _key) {
key = _key;
}
public void setLeft(BTNode _left) {
left = _left;
}
public void setRight(BTNode _right) {
right = _right;
}

public int visita() {
return getKey();
}
}

class BT {
private BTNode root;

public BT() {
root = null;
}

public boolean isEmpty() {
return (root == null);
}
public void insertRic(int _key) {
insertRic(_key, root, null);
}
private void insertRic(int _key, BTNode aux, BTNode prev) {

if (aux == null) {
if (prev == null) root = new BTNode(_key);
else if (_key < prev.getKey()) prev.setLeft(new BTNode(_key));
else prev.setRight(new BTNode(_key));
return;
}
if (aux.getKey() == _key) return;
if (_key < aux.getKey()) insertRic(_key, aux.getLeft(), aux);
else insertRic(_key, aux.getRight(), aux);

}

public void insert(int _key) {
if (isEmpty()) {
root = new BTNode(_key);
return;
}
BTNode aux = root;
BTNode prev = null;

while(!(aux == null)) {
if (_key == aux.getKey()) return;
else if (_key < aux.getKey()) {
prev = aux;
aux = aux.getLeft();
}
else {
prev = aux;
aux = aux.getRight();
}
}
if (_key < prev.getKey())
prev.setLeft(new BTNode(_key));
else prev.setRight(new BTNode(_key));
}


public void preOrd() {
preOrd(root);
}
private void preOrd(BTNode p) {
if (p==null) {
return;
}
System.out.println(p.visita());
preOrd(p.getLeft());
preOrd(p.getRight());
}

}
Logged

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #4 on: 01-05-2009, 10:36:09 »

Io metto la mia soluzione....

Questo programma gestisce inserimento,ricerca , inorder,postorder e preorder(sia ricorsivi ke interativi)

Code:
import java.io.*;
import java.lang.*;


class alberix
{
public static void main(String [] args) throws IOException
{
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader tastiera = new BufferedReader(in);

boolean esci=false;
Albero A =new Albero();
do
    {
    int x;
    int y;
    String nome;
   
   
    System.out.println("\nQUESTO E' UN PROGRAMMA SU CUI SI POSSONO EFFETTUARE DIVERSE OPERAZIONI SU UN ALBERO");
    System.out.println("+------------------------------+");
    System.out.println("|1-Inserimento                 |");
    System.out.println("|2-Ricerca                     |");
    System.out.println("|3-Inorder                     |");
    System.out.println("|4-Preorder                    |");
    System.out.println("|5-PostOrder                   |");
    System.out.println("|6-IterPreorder                |");
    System.out.println("|7-IterInorder                 |");
    System.out.println("|8-IterPostOrder               |");
    System.out.println("|9-///////////////////////     |");
    System.out.println("|10-Esci                       |");
    System.out.println("|11-////////////////////       |");
    System.out.println("+------------------------------+");
   
    System.out.println("Scegli quale operazione eseguire:");
    x= Integer.parseInt(tastiera.readLine());
   
    switch(x)
    {
    case 1:
         System.out.println("Scegli quale valore inserire:");
         y= Integer.parseInt(tastiera.readLine());
         
         try
         {
          A.inserisci(y);
         }
         catch(IOException e)
         {
          System.out.println( "Errore" );
         }
         
    break;
         
   
   
    case 2:
         System.out.println("Scegli quale valore ricercare nell'albero:");
         y= Integer.parseInt(tastiera.readLine());
         
         try
         {
          System.out.println(A.ricerca(y));
         }
         catch(ObjectNotFoundException e)
         {
          System.out.println( "Errore" );
         }
   
    break;
   
   
    case 3: 
          A.Inorder();   
    break;
   
   
    case 4:
          A.preorder(); 
    break;
   
    case 5:
          A.postorder();     
    break;
   
    case 6:
         
         try
         {
          A.IterPreorder();
         }
         catch( Overflow e ) { System.out.println( "Unexpected overflow" ); }
         catch( Underflow e ) { System.out.println( "Unexpected underflow" ); }
   
           
    break;
   
    case 7:
         try
         {
          A.IterInorder();
         }
         catch( Overflow e ) { System.out.println( "Unexpected overflow" ); }
         catch( Underflow e ) { System.out.println( "Unexpected underflow" ); }
         
    break;
   
    case 8:
         try
         {
          A.IterPostorder();
         }
         catch( Overflow e ) { System.out.println( "Unexpected overflow" ); }
         catch( Underflow e ) { System.out.println( "Unexpected underflow" ); }
           
    break;
   
    case 9: 
         
    break;
   
    case 10:
        esci = true;
    break;
   
   }


    }
    while(!esci);
    }






}



class Albero
{

// metodi per
// attraversamento (preorder, inorder, postorder),
// ricerca, inserimento, cancellazione

protected Nodo root;

public Albero()
{
root = null;
}


public boolean inserisci (int val) throws IOException // INSERIMENTO DI UN NODO
{
if(root==null)
{
root = new Nodo(val);
}
else
{
Nodo p= root , prev =null;

while(p!=null)
{
if(val==p.key) return false;

prev = p;

if(val < p.key) p = p.left;
else
{
p = p.right;
}

}

if(val <prev.key)
{
prev.left = new Nodo(val);
}
else
{
prev.right = new Nodo(val);
}


}
return true;
}


public Nodo ricerca(int val) throws ObjectNotFoundException
{
Nodo p = root;
while(p != null)
{
if(val == p.key) return p;
else
{
if (val < p.key) p = p.left;
else
    {
    p = p.right;
    }
}
}
return null;
}




public void Inorder() // INORDER
{
Inorder(root);
}

public void Inorder(Nodo n)
{
if(n != null)
{
Inorder(n.left);
System.out.println(n.visit());
Inorder(n.right);
}
}

public void preorder() // PREORDER
{
preorder(root);
}

public void preorder(Nodo n)
{
if(n != null)
{
System.out.println(n.visit());
preorder(n.left);
preorder(n.right);
}
}

public void postorder() // POSTORDER
{
postorder(root);
}

public void postorder(Nodo n)
{
if(n != null)
{
postorder(n.left);
postorder(n.right);
System.out.println(n.visit());
}
}


public void IterPreorder() throws Overflow,Underflow //Implementazione iterativa per preorder
{
Nodo p = root;
Pila aiuto = new Pila();

if(p!= null)
{
aiuto.push(p);

while(!aiuto.isEmpty())
{
p = (Nodo) aiuto.pop();
System.out.println(p.visit());

if (p.right != null) aiuto.push(p.right);
if (p.left != null) aiuto.push(p.left);
}
}

}


public void IterInorder() throws Overflow,Underflow //INORDER per iterazione
{
Nodo p = root;
Pila aiuto = new Pila();

while(p != null)
{
while(p != null) //chiamate ricorsive al sottoalbero sinistro
{
aiuto.push(p);
p = p.left;
}

do
{
p = (Nodo) aiuto.pop();
System.out.println(p.visit());
p = p.right;
}
while(!aiuto.isEmpty()); //chiamate ricorsive al sottoalbero destro
}
}


public void IterPostorder() throws Overflow,Underflow
{
Nodo p = root , q = root;
Pila aiuto = new Pila();

while(p != null)
{
for(;p.left != null;p = p.left) aiuto.push(p);


while (p != null && (p.right == null || p.right == q))
{
System.out.println(p.visit());
q = p;
if (aiuto.isEmpty()) return;

p = (Nodo) aiuto.pop();
}

aiuto.push(p);
p = p.right;
}
}

}

class Nodo
{
protected int key;
protected Nodo left,right;



public Nodo()
{
left = right = null;
}

public Nodo(int val)
{
this(val,null,null);
}

public Nodo(int val, Nodo lt, Nodo rt)
{
key = val;
left = lt;
right = rt;
}

public int visit()
{
return key;
}

public int visit(Nodo n)
{
return n.key;
}

}










class Underflow extends Exception{}
class Overflow extends Exception{}
class ObjectNotFoundException extends Exception{}

class Pila< E >
{
private E[] elem;

    private int top;
    private final int MAX;
    private static final int MAXDEFAULT = 10;


       
    public Pila( )
    {
        this( MAXDEFAULT );
    }

       
    public Pila( int max )
    {
    MAX = max;
   
    elem = (E[]) new Object[MAX];
   
        top = 0;
    }
   
    public boolean isEmpty( )
    {
    return top == 0;
    }

    public boolean isFull( )
    {
        return top == MAX;
    }

       
    public void clear( )
    {
        top = 0;
    }

       
    public int getSize( )
    {
        return top;
    }

       
    public E topElem( )
    {
    if( isEmpty( ) ) return null;
    return elem[ top ];
    }
     
     
    public E pop( ) throws Underflow
    {
    if( isEmpty( ) ) throw new Underflow( );
    return elem[ --top ];
    }
     

       
    public void push( E x ) throws Overflow
    {
    if( isFull( ) ) throw new Overflow( );
    elem[ top++ ] = x;
    }
     
     
     
    public void printStack( )
    {
    if( this.isEmpty( ) ) System.out.print( "Empty Stack" );
    else
    {
    for(int i=0; i<top; i++) System.out.print( elem[i] + " " );
    }
    }
     
     
}


che ve ne pare?
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #5 on: 02-05-2009, 14:41:22 »

Code:
public int visit(Nodo n)
{
return n.key;
}

che senso ha???
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
poty
Matricola
*
Offline Offline

Posts: 95


« Reply #6 on: 02-05-2009, 17:20:58 »

effettivamente ritornare un nodo che gli passiamo noi boh
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #7 on: 03-05-2009, 08:57:01 »

ma non ha senso visto che quel metodo è nella classe nodo e perciò deve già essere richiamato da un oggetto nodo  [Emoticon] Asd [Emoticon] Asd
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #8 on: 03-05-2009, 13:53:52 »

un piccolo errore di svista, grazie per avermelo fatto notare.
 era per fare una prova su un altro metodo
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #9 on: 03-05-2009, 14:04:43 »

 ok
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #10 on: 06-05-2009, 11:23:28 »

Ecco la mia implementazione dell'albero binario di ricerca, con le classi IntBSTNode, IntBST, che gestisce inserimento e visite
Code:

public class IntBSTNode
{
protected int key;
//protected boolean eliminato;  // attributo che mi specifica se il nodo è stato eliminato
protected IntBSTNode right,left;
public IntBSTNode(int _key)
{
this(_key,null,null);
//eliminato=false;

}
public IntBSTNode(int _key,IntBSTNode _right,IntBSTNode _left)
{
key=_key;
right=_right;
left=_left;
//eliminato=false;
}
public IntBSTNode()
{
right=left=null;
//eliminato=false;
}
public void visit()
{
System.out.print(key+" ");

}
}
Code:
public class IntBST
{
protected IntBSTNode root; // radice dell'albero


public IntBST()
{
root=null;
// TODO Auto-generated constructor stub
}
public boolean isEmpty(){
return root==null;
}
//Visita di un albero LRV
public void postorder()
{
postorder(root);
}
protected void postorder(IntBSTNode p)
{
if(p!=null)
{
postorder(p.left);
postorder(p.right);
p.visit();
}
}
//Visita di un albero LVR
public void inorder()
{
inorder(root);
}
public void preorder()
{
preorder(root);
}
protected void inorder(IntBSTNode p)
{
if(p!=null)
{
inorder(p.left);
p.visit();
inorder(p.right);
}
}
//Visita di un albero VLR
protected void preorder(IntBSTNode p)
{
if(p!=null)
{
p.visit();
preorder(p.left);
preorder(p.right);
}
}
public boolean insert(int x){
if(isEmpty())
root=new IntBSTNode(x);
else{
IntBSTNode p = root, prev=null;
while(p!=null){
if(x==p.key)
return false;//valore già presente
prev=p;
if(x<p.key)
p=p.left;
else
p=p.right;
}
if(x>prev.key)
prev.right= new IntBSTNode(x);
else
prev.left= new IntBSTNode (x);
}
return true;
}
Code:
//Classe di test

public class Test {


public static void main(String[] args)
{
IntBST Albero=new IntBST();
Albero.insert(15);
Albero.insert(4);
Albero.insert(7);
Albero.insert(20);
Albero.insert(16);
Albero.insert(25);
Albero.insert(5);
                System.out.println("Visita preorder");
Albero.preorder();
                System.out.println("Visita inorder");
Albero.inorder();
                System.out.println("Visita postorder");
                Albero.postorder();
}
}
Spero sia utile.Ciao
Logged
MiKKu
Apprendista Forumista
**
Offline Offline

Posts: 152



WWW
« Reply #11 on: 08-05-2009, 20:39:06 »

Qualcuno ha implementato la cancellazione??
Logged

Soltanto l'ardente pazienza porterà al raggiungimento di una splendida felicità. - www.ilmercatinoitaliano.it
Aigor
Forumista Esperto
****
Offline Offline

Gender: Male
Posts: 1.184


"Il destino non è una catena, ma un volo."[A.B.]


« Reply #12 on: 08-05-2009, 21:56:24 »

Ora pretendi troppo  cry
Logged

"Era d'altronde uno di quegli uomini che amano assistere alla propria vita, ritenendo impropria qualsiasi ambizione a viverla.
Si sarà notato che essi osservano il loro destino nel modo in cui, i più, sono soliti osservare una giornata di pioggia." - Seta,Baricco
rox
Forumista
***
Offline Offline

Posts: 633


« Reply #13 on: 09-05-2009, 07:09:04 »

io l'ho implementata ma non ho applicato la fusionemi manca ancora un pezzo di codice magati appena finisco lo posto qui.
Logged

Una macchina è in grado di lavorare come cinquanta uomini comuni, ma nessuna macchina può svolgere il lavoro di un uomo straordinario.
MiKKu
Apprendista Forumista
**
Offline Offline

Posts: 152



WWW
« Reply #14 on: 09-05-2009, 12:13:39 »

ti ringrazio  pray pray
Logged

Soltanto l'ardente pazienza porterà al raggiungimento di una splendida felicità. - www.ilmercatinoitaliano.it
Pages: [1] 2   Go Up
Print
Jump to: