Utilità di attraversamento pre e post ordine di alberi binari

Question

Utilità di attraversamento pre e post ordine di alberi binari

#1 da (12 voti)
#2 da (11 voti)
#3 da (5 voti)

13

Questo può essere molto ingenuo, ma mi stavo chiedendo, il contesto degli alberi binari (semplice, ordinato ed equilibrato), di tutti i tipi di attraversamento:

depth-first pre-order
depth-first in-order
depth-first post-order
breadth-first

qual è l'utilità effettiva di quelli pre e post-ordine? Voglio dire, c'è qualche tipo e / o configurazione di un albero binario in cui l'attraversamento pre e / o post-ordine darebbe un (qualche) vantaggio (s) rispetto agli altri due?

AFAICS, ci sono alcuni tipi e configurazioni di alberi binari per i quali in-order e breadth-first potrebbero dare un certo vantaggio:

per un albero binario bilanciato ogni attraversamento in profondità utilizzerà meno spazio di memoria rispetto a larghezza prima (ad esempio per un albero binario bilanciato di 6 o 7 nodi, l'altezza è 2 quindi qualsiasi attraversamento in profondità sarà è necessario memorizzare un massimo di 2 nodi in un dato momento, mentre l'ultimo livello ha 3 o 4 nodi in modo che l'attraversamento dell'ampiezza iniziale debba memorizzare fino a 3 o 4 nodi ad un certo punto). In questo caso, l'attraversamento in ordine utilizza la minor quantità di memoria e visita i nodi nel loro ordine naturale.
per un albero binario non bilanciato, se è vicino allo scenario di inserimento nel caso peggiore, percorrendolo in ampiezza si utilizza meno memoria rispetto a qualsiasi traversamento in profondità. Quindi in questo caso l'ampiezza offre un vantaggio. Traversal in-order ha ancora il vantaggio di visitare i valori nel loro ordine naturale.

Tuttavia non riesco a pensare a una situazione in cui il pre e il post-attraversamento darebbero un vantaggio rispetto agli altri due.

graph-traversal binary-tree

posta Shivan Dragon 11.02.2013 - 14:49

fonte

3 risposte

Leggi altre domande sui tag graph-traversal binary-tree

Inizi a migrare il tuo progetto Swing su JavaFX [chiuso] Quali funzionalità funzionali meritano una piccola confusione OOP per i benefici che apportano?

score 12 · Answer 1

Devi fare varie cose con gli alberi, come tradurre tra la struttura dei dati e alcune rappresentazioni seriali, come su un file o in una lingua.

Quindi, ad esempio, supponiamo di avere un albero di analisi come questo:

    *
   / \
  +   \
 / \   \
A   B   C

Potresti serializzarlo come * + A B C camminandolo nell'ordine prefisso o come A B + C * camminandolo nell'ordine postfix. Se lavori con processori del linguaggio, queste cose devono essere seconde.

score 11 · Answer 2

L' articolo di Wikipedia ha una descrizione sintetica di quando vorresti usare i diversi tipi di profondità- prima ricerca:

Attraversamento del preordine mentre la duplicazione di nodi e valori può creare un duplicato completo di un albero binario. Può anche essere usato per fare un'espressione prefisso (notazione polacca) da alberi di espressione: attraversare l'albero delle espressioni in modo preordinato.
Il traversal in-order è molto comunemente usato sugli alberi di ricerca binari perché restituisce i valori dal set sottostante in ordine, in base al comparatore che imposta l'albero di ricerca binario (da cui il nome).
L'attraversamento degli ordini durante l'eliminazione o la liberazione di nodi e valori può eliminare o liberare un intero albero binario. Può anche generare una rappresentazione postfissa di un albero binario.

Si riduce alle esigenze logistiche di un algoritmo. Ad esempio, se non utilizzi l'attraversamento post-ordine durante l'eliminazione, perdi i riferimenti necessari per eliminare gli alberi figlio.

score 5 · Answer 3

Il punto di avere diversi algoritmi per gestire gli alberi binari non è fare cose con gli alberi. A questo livello astratto, un ordine è in gran parte buono come tutti gli altri, dal momento che ottieni solo simboli astratti fuori dalla procedura.

Ma gli alberi sono generalmente usati per rappresentare cose interessanti, e questo può fare una grande differenza nel risultato. Ad esempio, se i nodi rappresentano gli stati di ricerca in una ricerca completa attraverso un dominio grande (forse anche un dominio infinito), la prima discendente e l'elaborazione prima non determinano solo in quale ordine vengono trovati i risultati, può anche determinare se non troverai mai nessuna soluzione . Il punto è più facile da vedere con domini infiniti: se si scende incautamente, si potrebbe trascurare una soluzione che si trova piuttosto in alto nell'albero, semplicemente perché si è svolta una svolta sbagliata. Ma in pratica, dal momento che anche la memoria e i dischi sono finiti, questo si applica anche ai domini che sono semplicemente molto grandi piuttosto che veramente infiniti.