Questo pseudocodice di Wikipedia per l'attraversamento generico di alberi in ordine è corretto?

Naviga le tue risposte
4

Wikipedia afferma che il seguente algoritmo funziona per qualsiasi albero ( non necessariamente alberi binari)

  1. Perform pre-order operation
  2. For each i (with i = 1 to n) do:
    1. Visit i-th, if present
    2. Perform in-order operation
  3. Perform post-order operation

where n is the number of child nodes.

Le parti di preordine e post-ordine hanno senso. L'in-order non ha senso per me comunque. Eseguendo questo algoritmo eseguirò l'operazione in-order sullo stesso nodo più volte. Fondamentalmente, se ho un nodo con 5 nodi figlio, eseguirò l'operazione in ordine sul nodo 5 volte, una volta dopo aver visitato ciascun nodo figlio. Questo non ha senso per me. Un attraversamento di alberi non dovrebbe attraversare ogni nodo una volta?

In realtà, una traversata ordinata ha senso anche per alberi generici? Non si applica solo agli alberi binari o agli alberi in cui l'ordine non è ambiguo?

    
posta 9a3eedi 19.03.2015 - 08:44
fonte

1 risposta

1

Nell'algoritmo che hai fornito, anche se è vero che la stessa operazione in-order viene eseguita nello stesso nodo più volte, viene comunque eseguita una volta per ogni nodo e ogni nodo viene visitato una sola volta.

Si noti che questo non è un attraversamento dell'albero "in ordine", non è possibile effettuare un attraversamento di questo tipo su un albero, ma non ha senso. Questo è semplicemente un deep-traversal e l'operazione in-order è qualcosa che viene eseguita dopo che il nodo è stato visitato. Non ha nulla a che fare con le "funzioni in-order" menzionate altrove nella pagina.

Forse dovrei aggiungere, visita è la chiamata ricorsiva in questo caso, non l'operazione in-order.

    
risposta data 24.03.2015 - 22:33
fonte

Leggi altre domande sui tag

È una buona idea avere una riga di database che rappresenta un valore sconosciuto all'interno di un sistema [chiuso] Progetto di casa e progetto di lavoro che condivide la libreria comune in fase di sviluppo