alberi binari (BTS) sono strutture dati utilizzate dai programmatori di computer il cui software deve rappresentare medie e grandi serie di dati in una maniera strutturata organizzata. Un BT costituito da un nodo padre con un massimo di due nodi secondari opzionali: un figlio sinistro e un figlio destro . Strutture di dati per applicazioni specifiche , quali alberi di ricerca , i cumuli e gli alberi di espressione sono semplicemente raccolte di singoli BT collegati tra loro a formare un set di dati collettiva . Ci sono tre metodi distinti per attraversare BTS: preordine , ordine simmetrico e postordine . Preorder Traversal
Preorder traversal visita nodi dell'albero in questa sequenza : genitore , figlio sinistro , figlio destro . Alcune applicazioni di preordine sono la valutazione di espressioni in notazione prefisso e il trattamento di alberi di sintassi astratta di compilatori . Il seguente pseudocodice dimostra la procedura esatta per un preordine :
---------------------- PROCEDURA preorder ( Binary_Tree_Node T ) BEGINProcessNode ( T ) Se ( figlio sinistro di T è NOT NULL ) BEGINPreOrder ( figlio sinistro di T ) endif ( figlio destro di T è NOT NULL ) BEGINPreOrder ( figlio destro di T) ENDEND
ordine simmetrico
< p > ordine simmetrico visita nodi dell'albero in questa sequenza : figlio sinistro , genitore , figlio destro . Alberi binari di ricerca ( un particolare tipo di BT ) utilizzano ordine simmetrico di stampare tutti i dati in ordine alfanumerico . Il seguente pseudocodice dimostra la procedura esatta per un ordine simmetrico :
---------------------- PROCEDURA ordine simmetrico ( Binary_Tree_Node T ) BEGINIf (T di sinistra bambino non è NULL ) BEGINInOrder ( figlio sinistro di T) ENDProcessNode ( T ) Se ( figlio destro di T è NOT NULL ) BEGINInOrder ( figlio destro di T) ENDEND ------------------- -
postordine
postordine visita nodi dell'albero in questa sequenza : figlio sinistro , figlio destro , genitore . Un'applicazione popolare per l'uso di postordine è la valutazione di espressioni in notazione postfissa . Il seguente pseudocodice dimostra la procedura esatta per un postordine :
---------------------- PROCEDURA postorder ( Binary_Tree_Node T ) BEGINIf (T di sinistra bambino non è NULL ) BEGINPostOrder ( figlio sinistro di T ) endif ( figlio destro di T è NOT NULL ) BEGINPostOrder ( figlio destro di T) ENDProcessNode ( T ) END ------------------- -
