mondo reale pre/post-order esempi albero attraversamento

Question

capisco pre-ordine, in ordine, e post-order algoritmi di attraversamento di alberi che bene. (Reference). Comprendo alcuni usi: in ordine per attraversare alberi di ricerca binaria in ordine, pre-ordine per clonare un albero. Ma non posso per la vita di me venire fuori con un compito del mondo reale che avrei bisogno di attraversare dopo l'ordine per realizzare.

Potete farmi un esempio? E: puoi darmi migliori usi per attraversare il pre-ordine?

Edit: Qualcuno mi può dare un esempio diverso da alberi di espressione e RPN? È davvero tutto a posto per il post-ordine?

Answer 1

Topological sorting è un attraversamento post-ordine di alberi (o grafo aciclico diretto).

L'idea è che i nodi del grafo rappresentano compiti e un arco da A a B indica che A deve essere eseguita prima B. Un ordinamento topologico organizzerà queste attività in una sequenza in modo tale che tutte le dipendenze di un'attività compaiano prima del compito stesso. Qualsiasi sistema di build come UNIX make deve implementare questo algoritmo.

L'esempio che Dario menzionato - distruggendo tutti i nodi di un albero con gestione manuale della memoria - è un esempio di questo problema. Dopo tutto, il compito di distruggere un nodo dipende dalla distruzione dei suoi figli.

Answer 2

ordine Post è (può essere) utilizzata dai compilatori. Considerare un albero di espressioni per a + b + c, il linguaggio macchina richiederebbe una sequenza come a b + c +. Questo è anche chiamato Reverse polish Notation (RPN). Nella pagina di Wikipedia si legge: "RPN aka Postfix"

Il post-ordine è necessario anche per distruggere un albero, proprio come è necessario il pre-ordine per crearlo/clonarlo.

Answer 3

Come Henk Holterman ha sottolineato, distruggendo un albero con gestione manuale della memoria di solito è un attraversamento post-ordine.

Pseudocode:

destroy(node) { 
    if (node == null) return; 

    destroy(node.left) 
    destroy(node.right) 

    // Post-order freeing of current node 
    free(node) 
}