Mi sembra che il traversal pre-ordine e DFS siano gli stessi di entrambi i casi attraversiamo da root fino al ramo sinistro e torniamo a root e quindi al ramo destro in modo ricorsivo. Qualcuno potrebbe correggermi se ho torto?
Grazie in anticipo!
L'attraversamento preordinato è uguale alla prima ricerca di profondità?
7
3 risposte
5
l'attraversamento pre-ordine è un attraversamento, visita ogni nodo in un albero binario
Depth First Search è una ricerca, gira attorno a un grafico arbitrario cercando un determinato nodo (che funziona meglio in un grafo non ciclico (a.k.a. tree) è irrilevante)
solo questa è una differenza abbastanza grande da chiamarli nomi di differenze
0
Per attraversare un albero binario in Preorder, le seguenti operazioni vengono eseguite
- Visita la root
- Attraversa la sottostruttura di sinistra
- Attraversa la sottostruttura di destra
Questo è nell'immagine qui sotto l'attraversamento di preordine sarebbe, 1,2,3,6,4,5,7,8,9,10,11,12
Nella stessa immagine 1,2,3,4,5,6,7,8,9,10,11,12 sarebbe per DFS
Fonte DFS: link
Origine preordine: Wiki
risposta data
05.02.2014 - 09:16
fonte
0
Sì, ma dovrebbe essere il contrario: DFS è simile a PreOrder. Il termine PreOrder è più rilevante per gli alberi binari e i parser. È usato per confrontarsi con altri ordini di attraversamento di un albero binario: InOrder, PostOrder e PreOrder. L'ordinamento topologico è simile al traversamento degli ordini (spingere il nodo in pila dopo aver visitato tutti i nodi adiacenti).
risposta data
22.07.2015 - 20:59
fonte
Leggi altre domande sui tag algorithms trees graph-traversal binary-tree