Home | Edit | Attach | Site Map | Help

Search Search All Webs Search Prog groupSearch Programmazione1 Search Topics name Go To topic Create topic Advanced search... Topics Home Recent Changes Topics Index Email Notify Statistics Web Preferences Iscrizione Cambia Password Reset Password Parents DomandeHomework8aa0203

Homework 8 - alberi binari Vedi anche: DomandeHomework8aa0203, SoluzioneHomework8aa0203, RisultatiHomework8aa0203. Homework 8 - alberi binari Obiettivi Alberi binari Esempi Ordinamenti Preordine Inordine Postordine Svolgimento Formato del grafo Preordine Inordine Postordine Esempio di formato usato per input e/o output Opzionale Obiettivi lettura in preordine di un albero binario stampa in postordine di un albero binario Alberi binari Un albero binario è composto da nodi formati da 3 campi: valore che contiene il valore (intero) associato al nodo sinistro che contiene un puntatore al nodo radice del sottoalbero sinistro (oppure NULL) destro che contiene un puntatore al nodo radice del sottoalbero destro (oppure NULL) Parlando di alberi di usano i seguenti termini: radice è il nodo più in alto (in informatica gli alberi sono disegnati a testa in giù ) figli sono i (due) nodi che un nodo ha subito sotto foglia è un nodo che non ha figli Esempi Negli esempi: la radice è il nodo che contiene il valore 1 le foglie dell'esempio a sinistra sono i nodi 6, 7, 5, 3 le foglie dell'esempio a destra sono i nodi 5, 6, 7 i figli del nodo 2 dell'esempio di sinistra sono i nodi 4, 5 Ordinamenti Preordine La lettura (o scrittura) in preordine viene eseguita ricorsivamente seguendo il seguente schema: prima si legge (o stampa) il valore del nodo radice poi si legge (o stampa) il sottoalbero sinistro poi si legge (o stampa) il sottoalbero destro Inordine La lettura (o scrittura) in inordine viene eseguita ricorsivamente seguendo il seguente schema: prima si legge (o stampa) il sottoalbero sinistro poi si legge (o stampa) il valore del nodo radice poi si legge (o stampa) il sottoalbero destro Postordine La lettura (o scrittura) in postordine viene eseguita ricorsivamente seguendo il seguente schema: prima si legge (o stampa) il sottoalbero sinistro poi si legge (o stampa) il sottoalbero destro poi si legge (o stampa) il valore del nodo radice Svolgimento Si scriva un programma C che legge da stdin un albero binario in preordine e lo stampa su stdout in postordine seguendo il formato specificato qua sotto sia per l'input che per l'output . Formato del grafo Nel seguito <esiste sottoalbero ...> può valere: 0 = non esiste 1 = esiste Nel seguito <sottoalbero XXX (se esiste)> indica che: se l'indicatore <esiste sottoalbero XXX> valeva 1 a partire da quella riga bisogna leggere (o scrivere) un albero quell'albero è il sottoalbero figlio XXX (sinistro o destro) del nodo corrente altrimenti il sottoalbero XXX non c'e' e non appare nell'input (o output) Preordine Il grafo (in preordine) viene specificato da una successione di righe che seguono il formato seguente: <valore della radice> <esiste sottoalbero sinistro> <esiste sottoalbero destro> <sottoalbero sinistro (se esiste)> <sottoalbero destro (se esiste)> Inordine Il grafo (in inordine) viene specificato da una successione di righe che seguono il formato seguente: <esiste sottoalbero sinistro> <esiste sottoalbero destro> <sottoalbero sinistro (se esiste)> <valore della radice> <sottoalbero destro (se esiste)> Postordine Il grafo (in postordine) viene specificato da una successione di righe che seguono il formato seguente: <esiste sottoalbero sinistro> <esiste sottoalbero destro> <sottoalbero sinistro (se esiste)> <sottoalbero destro (se esiste)> <valore della radice> Esempio di formato usato per input e/o output Ecco le diverse rappresentazioni di un grafo: Grafo Preordine Inordine Postordine 1 1 1 2 1 1 4 1 1 6 0 0 7 0 0 5 0 0 3 0 0 1 1 1 1 1 1 0 0 6 4 0 0 7 2 0 0 5 1 0 0 3 1 1 1 1 1 1 0 0 6 0 0 7 4 0 0 5 2 0 0 3 1 Grafo Preordine Inordine Postordine 1 1 1 2 1 0 5 0 0 3 0 1 4 1 1 6 0 0 7 0 0 1 1 1 0 0 0 5 2 1 0 1 3 1 1 0 0 6 4 0 0 7 1 1 1 0 0 0 5 2 0 1 1 1 0 0 6 0 0 7 4 3 1 Opzionale Si faccia in modo che il programma possa accettare sulla riga di comando un parametro che può valere: pre l'albero letto viene stampato in preordine in l'albero letto viene stampato in inordine post l'albero letto viene stampato in postordine Se il parametro non è presente l'albero letto viene stampato in postordine -- AndreaSterbini - 17 Dec 2002 Set ALLOWTOPICCHANGE = DocentiProg1Group

Actions: Edit | Attach | Ref-By | Printable view | Raw view | See diffs | Help | More...

Programmazione1.HomeWork8aa0203 r1.9 - 30 Sep 2003 - 13:15 GMT - AndreaSterbini Programmazione1.HomeWork8aa0203 moved from Programmazione1.HomeWork8 on 30 Sep 2003 - 13:09 by AndreaSterbini - put it back

Copyright © 2000 by the contributing authors. All material on this collaboration tool is the property of the contributing authors. Ideas, requests, problems regarding TWiki? Send feedback.