Newsgroup: it.comp.lang.c
Titolo: strutture dati ad albero

Salve il mio problema è semplice a dirsi ma, a quanto pare meno a farsi:
dovrei stampare un albero con una procedura iterativa, assolutamente senza
fare uso di ricorsione,
sapreste darmi qualche suggerimento??
La struttura dati dell albero è questa:
Struct nodi{
int info;
struct nodi *sx;
struct nodi *dx:
};
typedef struct nodi * albero;
Grazie mille

 Grazie mille
Potresti usare uno stack... Avevo letto qualcosa di simile su "Algoritmi
in C", ma non ho piů quel libro. Comunque perchč senza ricorsione?

:

Ipotiziamo una visita in ordine.
Se la radine e' nulla hai finito.
Se no inizi (non e' ottimizzata, ma ti spiega l'algoritmo):
WHILE lo stack non e' vuoto:
    1) POP()
    2) IF c'e' un figlio sinistro
        a) PUSH (nodo corrente)
        b) PUSH (figlio sinistro)
        c) continua
    3) visita (nodo corrente)
    4) IF c'e' un figlio destro
        a) PUSH (figlio destro)
Nota che se c'e' un sottoalbero sinistro (quindi anche un solo nodo)
devi visitarlo tutto prima del nodo corrente (che hai gia' poppato per
capire chi era e quindi devi rimettercelo dentro).
Una prima ottimizzazione e' non poppare subito il nodo, ma solo se non
ci sono figli sinistri, controllando se ci sono figli sinistri con un
operazione di lettura del TOP dello stack ed fare la pop solo prima
della visita.
Ovviamente cambia l'ordine delle operazioni a seconda del tipo di
visita che devi fare (pre, post o inorder e da sinistra a destra o da
destra a sinistra).
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 wrote in message
n138eusc2ddvtb6ui...@4ax.com...


 ha scritto nel messaggio
news:lXTE8.64014$zW3.9...@news1.tin.it...


Secondo te (Andrea) vale la pena di comprare il libro da te citato??
Scusate se ho invertito l'ordine della domanda con la risposta, ma e'
stato piu' forte di me correggere :P
"Algoritmi in C" vale la pena, soprattutto se non ti interessano tutti
gli aspetti matematici e i teoremi che ci stanno dietro, ma vuoi solo
la parte pratica (in C) e tratta aspetti che gli altri non fanno (come
il considerare gli overflow nella concezione degli algoritmi).
Altri 2 ottimi libri sono il Knuth ("The Art of Computer Programming"
e il titolo dice tutto) e il Rivest ("Introduzione agli algoritmi",
BTW l'autore e' la R di RSA, proprio il primo che capita non e').
Pero' trattano di Algoritmi, non di implementazione in un dato
linguaggio.


>         a) PUSH (figlio destro)
Ecco il codice in forma C-like. Noterai che dice le stesse cose, solo
che e' meno comprensibile perche' piu' sporco di parentesi, operatori,
punteggiatora... non e' un caso se quando ti spiegano gli algoritmi
usano pseudocodice o un implementazione minimale e grezza, spezzando
il piu' possibile in funzioni.
<CODE>
stack S;
btree root;
btree tmp;
push(S, root);
while (!isempty(S)) {
    tmp = pop(S);
    if (tmp == NULL)
	continue;
    if (tmp->left != NULL) {
        push(S, tmp);
        push(S, tmp->left);
        continue;
    }
    visit(tmp) /* per es. la stampa dei dati contenuti */
    if (tmp->right != NULL)
        push(S, tmp->right);
}
</CODE>
Per come implementare lo stack RTK&R (si intuisce abbastanza questa
sigla :P).


 >Scusami  potresti postarmi qualcosa che sia piů vicino al c.


come è implementata la pop a cui ti riferisci?
Di push ne faccio molte, nel ciclo while ce n'e' una per ogni figlio
sinistro E per ogni padre del figlio sinistro.
Metti la root nella pila, poi nel ciclo inizi a estrarre finche' ci
sono nodi nella pila. Se alla prima estrazione tiri fuori solo la root
E ha valore NULL allora avevi un albero vuoto, riinizi il ciclo, lo
stack e' vuoto quindi termini.
A ogni passo leggi la cima dello stack (POP), e poi controlli se ha
figli sinistri. Se li ha il figlio dev'essere visitato prima del
padre, ma non subito, perche' se avesse a sua volta dei figli pure
loro andrebbero visitati ... percio' riimpila il nodo corrente, poi
riimpila left e ricomincia il ciclo. Al passo dopo estrarra' il
vecchio left e continuera' a visitarlo ricorsivamente fino alle
foglie.
Quando arriva a una foglia non e' piu' vera la condizione "if
(tmp->left != NULL)" percio' non impila nulla ma analizza il nodo
corrente.
Visitato quello passa a destra e ripete lo stesso discorso di prima
(anche a destra possono esserci figli sinistri da visitare prima).
E' esattamente lo stesso meccanismo della ricorsione, solo che attivo
io a mano i "record di attivazione" delle varie chiamate anziche'
farlo fare al compilatore.
Uso tmp per non usare la root, perche' root potrebbe essere
modificabile e perderei la testa dell'albero E comunque non e'
didattico assegnare a root sempre valori diversi: root e' la testa e
basta, variabili nominate tmp, aux, ptr servono per scorrere (usare
nomi almeno vagamente significativi per lo scopo delle variabili).
Immagina uno stack molto grezzo fatto cosi':
typedef struct stack {
    btree base[10];
    int top;
} stack;
La POP sara' una cosa del tipo (implementabile anche come una macro se
preferisci).
btree pop(stack S) {
    return (top == -1) ? (NULL) : ((S.base)[top--]);
}
Ovviamente il valore di ritorno dipende da cosa deve contenere lo
stack (io preferisco i void *, ma non penso sia il thread giusto per
portarti questo esempio).
La isempty() controlla semplicemente che top sia -1 (in caso lo stack
e' vuoto) o un valore compreso tra 0 e MAX (in tal caso non e' vuoto).
La push funziona al contrario: prima incrementa il puntatore allo
stack e poi inserisce li (controllando di non fare overflow).
E' descritta pari pari sul K&R.


 wrote in message
455feukhq6fhdaere...@4ax.com...


 >come č implementata la pop a cui ti riferisci?


come pensi si possa risolvere?
Se vuoi implementare lo stack con una lista allora ti serve una
struttura in piu': uno stack_node. Per la lista bastava un puntatore
in testa, per lo stack servono almeno 2 puntatori.
<CODE>
/* per comodita', ti bastarebbero i 2 puntatori */
typedef struct stack {
    stack_node * base;
    stack_node * top;
} stack;
typedef struct stack_node {
    btree * data;
    btree * next;
} stack_node;
stack S;
</CODE>
Supponi lo stack inizializzato correttamente e una funzione che alloca
correttamente il nodo chiamata new_node (e' facile da scrivere, e non
e' quello il problema).
<CODE>
int push(stack S, btree t)
{
    stack_node * tmp;
    tmp = new_stacknode();
    tmp->data = t;
    tmp->next = S.top;
    if (S.top == NULL)
        S.base = tmp;
    S.top = tmp;
    return 1;
}
</CODE>
<CODE>
btree * pop (stack S)
{
    btree tmp;
    if (S.top == NULL)
	return NULL;
    tmp = S.top;
    if (S.top == S.base)
        S.top = S.base = NULL
    else
        S.top = S.top->next;
    return tmp;
}
</CODE>
L'albero non lo devi mai toccare ne ricreare: ci copi solo un
riferimento nello stack per i cicli successivi. Lo stack in questo
caso ti fa' da promemoria per sapere cosa fare al ciclo dopo.


</CODE>


 wrote in message
e1ufeush74ihnvu3o...@4ax.com...


typedef struct nodi *PILA;
Presupporrebbe che tu distrugga il nodo ogni volta. Il mio medoto
invece prende l'indirizzo di un nodo dell'albero e te lo ritorna nella
funzione principale, cosi':
- non devi riscriverti la funzione principale
- hai un costo bassissimo	
Lo stack sara' graficamente una cosa cosi':
+--+                        Non sai a priori dove puntano left e right
|  | -->  NODO_3            dei vari nodi, ma tanto non ti serve
+--+                        saperlo finche' non devi decidere se
|  | -->  NODO_2            impilare un figlio, cosi' come non ti
+--+                        serve il campo data se non quando devi
|  | -->  NODO_1            visitarlo.
+--+


 in testa, per lo stack servono almeno 2 puntatori.
scusa, ma perche`? Per uno stack basta questo:
struct node {
        int info;
        struct node* next;
};
typedef struct node* Stack;
Poi fai inserimenti e cancellazioni in testa alla lista.
ciao Anto
-- 
Antonio Cuni, 20 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

Poi fai inserimenti e cancellazioni in testa alla lista.
Vero, stavo pensando a un'altro aspetto del problema e mi e' sfuggita
la soluzione ovvia.
