Se abbiamo un albero a 4 vie come quello mostrato qui sotto, e facciamo un traversale ordinato, quale sarebbe l'uscita della traversata in ordine per un albero M-way?
In quale ordine verranno visitati i nodi? Quando verrebbe elaborato il valore nel nodo (alla prima visita o alla seconda visita)?
(Come esempio concreto, quale sarebbe la procedura passo passo per l'attraversamento in ordine per l'albero di esempio mostrato sotto?)
Credo che l'attraversamento in ordine degli alberi m-way possa essere generalizzato. Prendiamo l'esempio dell'albero che hai fornito. Di seguito sono riportati i passaggi per questo:
Vai prima sul nodo più a sinistra e stampa il suo primo elemento. Quindi controlla se c'è un sottoalbero tra questo elemento e l'elemento successivo in quel nodo. Se esiste, applica lo stesso approccio su quel sottoalbero, altrimenti usa l'elemento di stampa. Allo stesso modo, spostati attraverso tutti gli elementi in quel nodo. Dal momento che nel tuo albero non ci sono sottoalberi nel nodo più a sinistra, quindi stampa tutti gli elementi. Quindi l'output del primo passo sarà: 2, 5, 6.
Quindi applicate lo stesso algo nel nodo genitore e spostatevi verso il nodo radice in modo ricorsivo.
Quindi l'output della traversata in ordine del tuo albero dovrebbe essere:
2,5,6, 7, 9,12,17, 20, 26,31,39, 45, 46,53,71
Puoi fare riferimento a questo ppt per maggiori informazioni: In ordine Traversal of M-Way Trees
Non esiste una traversata ordinata in ordine per gli alberi di rose (m-way trees), a differenza degli attraversamenti pre- o post-ordine, perché mentre è evidente che è necessario elaborare prima la sottostruttura più a sinistra e la sottostruttura più a destra, non è chiaro quando dovresti elaborare il nodo corrente.
Ho finito col dire "processare la sottostruttura più a sinistra, quindi il nodo corrente, quindi i restanti sottoalberi in ordine". Quando i nodi dell'albero di rose hanno tutti due o meno sottoalberi, questo finisce con la stessa traversata di un traversamento in ordine di un albero binario.
Supponendo che ogni nodo nel diagramma abbia un valore di matrice (non trovo il diagramma molto chiaro), l'attraversamento che descrivo darebbe [[2,5,6],[7,20,45],[9,12,17],[26,31,39],[46,53,71]] .
Leggi altre domande sui tag data-structures algorithms trees