Impesud Technology: programming, design and computer

Algoritmi in Java: Alberi - Parte 1

05-Jun-08

E finalmente dopo aver spiegato le definizioni e codici delle pile e code, siamo arrivato al tema degli alberi. Prima di iniziare vi darò alcune definizioni principali e le spiegherò nel modo più semplice possibile:

Albero: Struttura formata da un primo elemento detto radice a cui sono collegati uno o più sottoalberi.
SottoAlbero: Struttura formata da un primo elemento detto radice a cui sono collegati uno o più sottoalberi.
Nodi: Sono gli elementi fondamentali di un albero. Si dividono in nodi interni e foglie.
Nodi Interni: Sono i nodi che sono collegati a uno o più discendenti (figli).
Foglie: Sono i nodi che non sono collegati a nessun discendente.
Ramo: E' il legame che lega un nodo con un suo discendente.
Padre: E' il nodo interno a cui è collegato almeno un altro elemento detto discendente o figlio.
Figlio: Sono i nodi che non si possono raggiungere attraverso i collegamenti a partire da un nodo interno. Ogni nodo interno ha almeno un figlio. Il numero massimo di Figlio dipende dalla tipologia dell'Albero.
Path (Percorso): Sono i rami che bisogna percorrere per raggiungere un elemento partendo dalla radice.
Livello: E' il numero di rami che bisgona percorrere per raggiungere un elemento partendo dalla radice. E' la lunghezza del percorso.
Altezza (Profondità): E' il massimo numero di rami che bisogna percorrere per una foglia. E' il percorso più lungo.

Esistono diverse tipologie di alberi (albero binario, albero ternario, albero quadernario...albero n-ario) ma quello che ci interessa in particolare sono gli alberi binari. Dentro a questa tipologia si trovano gli alberi binari di ricerca.

Alberi Binari di Ricerca:

E' un albero binario con una particolarità: Per tutti i nodi i valori contenuti nel sottoalbero sinistro sono minori dei valori contenuti nel sottoalbero destro.

Albero Binario di Ricerca

Visita di un Albero:

E' l'accesso alle informazioni passando per ogni nodo una sola volta. Si utilizza un procedimento di tipo ricorsivo.

Visita Anticipata o Pre-Ordine: Stampa la radice, dopodichè effettua una visita anticipata nel sottoalbero sinistro e poi nel sottoalbero destro. Facendo questo tipo di visita nell'albero precedente abbiamo: 8-4-2-6-12-10-13
Visita Simmetrica o In-Ordine: Effettua una visita simmetrica nel sottoalbero sinistro, dopodichè stampa la radice e poi effettua una visita simmetrica nel sottoalbero destro. Facendo questo tipo di visita nell'albero precedente abbiamo: 2-4-6-8-10-12-13
Visita Posticipata o Post-Ordine: Effettua una visita posticipata nel sottoalbero sinistro, dopodichè effettua una visita posticipata nel sottoalbero destro e poi stampa la radice. Facendo questo tipo di visita nell'albero precedente abbiamo: 2-6-4-10-13-12-8

In seguito pubblico un esempio che abbiamo elaborato con Carlos Alva:

PLAIN TEXT

JAVA:

public class Tree {
Tree left,right,root;
int val;
Tree(int v,Tree a,Tree b){
val=v;
left=a;
right=b;
}
Tree(int n){
this.val=n;
this.left=null;
this.right=null;
}
int getval(){
return this.val;
}
Tree getleft(){
return this.left;
}
Tree getright(){
return this.right;
}
public void Add(Tree T, int n){
if(n<T.val){
if(T.left==null){
Tree t=new Tree(n);
T.left=t;
T.left.root=T;
}else{
Add(T.left,n);
}
}else {
if(T.right==null){
Tree t=new Tree(n);
T.right=t;
T.right.root=T;
}else{
Add(T.right,n);
}
}
}
}

PLAIN TEXT

JAVA:

import java.util.*;
public class Stampa {
public static void Preordine(Tree t){
if(t!=null){
System.out.print(t.val+" ");
Preordine(t.left);
Preordine(t.right);
}
}
public static void Inordine(Tree t){
if(t!=null){
Inordine(t.left);
System.out.print(t.val+" ");
Inordine(t.right);
}
}
public static void Postordine(Tree t){
if(t!=null){
Postordine(t.left);
Postordine(t.right);
System.out.print(t.val+" ");
}
}
public static void main(String[] args) {
Tree t=new Tree(72);
int x[]={51,30,19,3,27,45,69,74,99,80};
for(int i=0;i<=x.length-1;i++){
t.Add(t,x[i]);
}
Stampa.Preordine(t);
Stampa.Inordine(t);
Stampa.Postordine(t);
}
}

Per oggi penso che sia sufficiente come prima parte, nella seconda spiegherò altri metodi che potranno essere aggiunti all'albero di ricerca. Se avete dubbi, domande potete contattarmi quando volete , sia lasciando un commento o andando all'area Contact-me

If you liked this post, buy me a beer - Si te ha gustado este artículo,cómprame una cervezita - Se ti è piaciuto questo articolo, comprami una birra

Popularity: 23% [?]

Algoritmi in Java: Implementazione dinamica di una Coda usando un Array

27-May-08

Continuo ancora a pubblicare gli algoritmi in Java, giacchè spero di "affrontarli" il meglio possibile nel prossimo esame. Facendo questo "sforzo sopraumano" spero di poter anche aiutarvi a capirli . Con questo articolo chiudo il tema dell'implementazioni di pile e code.

PLAIN TEXT

JAVA:

/* AUTORE: Erick Jara */
public class UsaCodaconArray
{
public static void main(String[] args){
CodaconArray c = new CodaconArray(5);
CodaconArray c1 = new CodaconArray(5);
System.out.println("La coda e' vuota? " + c.codavuota());
System.out.println("La coda e' piena? " + c.codapiena());
c.enqueue(4); // Inserisco 4 nella coda dell'oggetto c
c.enqueue(6); // Inserisco 6 nella coda dell'oggetto c
c.enqueue(7); // Inserisco 7 nella coda dell'oggetto cc
c1.enqueue(8); // Inserisco 8 nella coda dell'oggetto c1
c1.enqueue(10); // Inserisco 10 nella coda dell'oggetto c1
System.out.println("Coda 1: "+c.toString()); // Stampo i valori presenti nell'oggetto c: 4 - 6 - 7 - 0 - 0
System.out.println("Coda 2: "+c1.toString()); // Stampo i valori presenti nell'oggetto c1: 8 - 10 - 0 - 0 - 0
System.out.println(c.top()); // Visualizzo primo elemento in testa dell'oggetto c
c.dequeue(); //Tolgo l'elemento in testa -> Nuova struttura dell'oggetto c: 6 - 7
System.out.println(c.top()); // Visualizzo primo elemento in testa dell'oggetto c
c.dequeue(); //Tolgo l'elemento in testa -> Nuova struttura dell'oggetto c: 7
System.out.println(c.top()); // Visualizzo primo elemento in testa dell'oggetto c
System.out.println(c1.top()); // Visualizzo primo elemento in testa dell'oggetto c1
}
}

PLAIN TEXT

JAVA:

public class CodaconArray
{
private int[] elementi;
private int numElementi;
private int head; // testa
private int tail; // coda
public CodaconArray(int capacita)
{
numElementi = capacita;
elementi = new int[capacita];
head = 0;
tail = 0;
}
public void enqueue(int n){
if (codapiena()) System.out.println("Coda piena, non e' possibile inserire un elemento");
else {elementi[tail] = n; // inserisce n in coda
tail = (tail+1)%numElementi; // punta al prox elem libero
}
return;
/* Algoritmo Accoda(Q,x)
Q[Tail[Q]]=x
IF Tail[Q]=Length[Q]
THEN Tail[Q]=1
ELSE Tail[Q]=Tail[Q]+1 */
}
public void dequeue(){
if (!codavuota()) head = (head+1)%numElementi;
else {System.out.println("Coda vuota, non e' possibile cancellare nulla");
}
return;
/* Algoritmo Estrai-da-Coda(Q)
x=Q[Head[Q]]
IF Head[Q]=Length[Q]
THEN Head[Q]=1
ELSE Head[Q]=Head[Q]+1
return x */
}
public int top(){
if (!codavuota()) return(elementi[head]);
else { System.out.println("Coda vuota, non e' possibile trovare il primo elemento");
return(-1);
}
}
public boolean codavuota(){
return(head==tail);
}
public boolean codapiena(){
return((tail+1)%numElementi==head); // lascia sempre una posizione vuota nel vettore
}
public String toString() {
String temp="(CODA)[INIZIO]-";
for ( int i = 0; i <numElementi; i++ )
temp+=elementi[i] + "-";
return temp+"[FINE]";
}
}

If you liked this post, buy me a beer - Si te ha gustado este artículo,cómprame una cervezita - Se ti è piaciuto questo articolo, comprami una birra

Popularity: 24% [?]

Algoritmi in Java: Implementazione dinamica di una Coda usando una Lista

27-May-08

Una coda è una struttura dati che utilizza la disciplina FIFO ( First In First Out ). Anche le code possono essere implementate, come le pile, o in modo illimitato, con delle liste concatenate, o in modo limitato, con un array o vettore. In questo caso vedremo solo l’utilizzo di una coda illimitata.
Le operazioni che si possono eseguire su una coda sono quindi le seguenti:

enqueue (x) : inserisce l’elemento x in fondo alla coda;
dequeue ( ) : elimina l’elemento in testa alla coda senza ritornarlo;
front ( ) : restituisce l’elemento in testa alla coda senza rimuoverlo;
isEmpty ( ) : indica se la coda è vuota;

Per il momento pubblico il codice della implementazione dinamica di una coda usando una lista, il prossimo articolo corrisponderà a quello con l'implementazione usando un array.

PLAIN TEXT

JAVA:

class Nodo{
private int dato;
private Nodo next;
public void enqueue(int n)
{
next = new Nodo(n);
}
public Nodo dequeue(Nodo primo)
{
primo = primo.next;
return primo;
}
public int front()
{
return dato;
}
public Nodo(int n)
{
dato = n;
next = null;
}
}

PLAIN TEXT

JAVA:

/*
Queue (Coda)
1) Una Coda è un insieme dinamico in cui l’elemento rimosso dall’operazione di cancellazione è predeterminato.
2) In una Coda questo elemento è l’elemento che per più tempo è rimasto nell’insieme.
3) Una Coda implementa una lista di tipo “first in,first out” (FIFO)
4) Possiede una testa (Head) ed una coda (Tail).
5) Quando si aggiunge un elemento, viene inserito in coda al posto referenziato da Tail.
6) Quando si estrae un elemento, viene estratto dalla testa.
*/
class Coda
{
private Nodo head;
private Nodo tail;
public Coda()
{
head = null;
tail = null;
}
public void enqueue(int n){ // Inserimento: enqueue (x)
if (vuota()) { // inserisce l’elemento x in fondo alla coda
head = new Nodo(n);
tail = head;
}
else {
tail.enqueue(n);
}
}
public void dequeue(){ // Cancellazione: dequeue ( )
if (!vuota()) { // cancella l’elemento in testa alla coda senza ritornarlo
head = head.dequeue(head);
if (head==null)
tail = null;
}
else System.out.println("Coda vuota, non e' possibile cancellare nulla");
}
public int front(){ // Visualizzazione primo elemento: front ( )
if (!vuota()) { // restituisce l’elemento in testa alla coda senza rimuoverlo
return(head.front());
}
else {
System.out.println("Coda vuota, non e' possibile trovare il primo elemento");
return(-1);
}
}
public boolean vuota(){ // Altre operazioni: Coda-Vuota()
return(tail==null); // verifica se la Coda è vuota (ritorna True se la Coda è vuota)
}
public static void main(String[] args){
Coda c = new Coda();
Coda c1 = new Coda();
c.enqueue(5);
c.enqueue(3);
System.out.println(c.front());
c1.enqueue(9);
c1.enqueue(6);
c.dequeue();
System.out.

Impesud Technology

About Me

Recent Comments

Categories

Archives

Network Blogs

Recent Posts

Advertisers

Algoritmi in Java: Alberi - Parte 1

05-Jun-08

Algoritmi in Java: Implementazione dinamica di una Coda usando un Array

27-May-08

Algoritmi in Java: Implementazione dinamica di una Coda usando una Lista

27-May-08