So che è possibile ricostruire un albero binario quando gli vengono impartiti gli inorder e gli attraversamenti preordinati come stringhe, ma è possibile trovare il postorder e/o gli attraversamenti preordinati solo quando dato l'inorder traversal?Trovare gli altri due attraversamenti di un albero binario quando viene dato solo un attraversamento
Trovare gli altri due attraversamenti di un albero binario quando viene dato solo un attraversamento
risposta
No, non è possibile recuperare il postorder/preorder dal solo attraversamento inorder. Se lo fosse, sarebbe possibile ricostruire un albero binario con solo l'inorder traversal, il che non è possibile perché un traversal inorder può darti diversi possibili alberi binari ricostruiti.
Come appare il tuo input e qual è lo scopo dell'albero?
Se si dispone di un'espressione in ordine completamente tra parentesi, si dispone di un albero uniqe e si ottiene pre e post ordine costruendo l'albero e quindi costruendo i termini pre- e post ordine dall'albero.
Se la tua espressione non è completamente tra parentesi, allora questa è un'indicazione che non c'è differenza tra i diversi alberi che corrispondono al tuo in-order. E.g Se si tratta di un albero che rappresenta espressioni aritmetiche, allora x+y+z
è lo stesso di (x+y)+z
e x+(y+z)
. Ciò significa, tuttavia, che non importa quale pre o postorder utilizzi, anche ++xyz
e +x+yz
sono gli stessi.
Ora, se questo non ha importanza, non è necessario preoccuparsi di diverse rappresentazioni del proprio ordine. Basta scegliere una delle rappresentazioni e quindi calcolare il pre e post ordine indotto da questo albero.
- 1. Costruire un albero con attraversamento di prenotazione dato
- 2. Attraversamento di un albero per trovare un nodo
- 3. trovare due elementi più distanti in un albero binario
- 4. Un albero binario contiene un altro albero?
- 5. Dato il vettore di un asse, come faccio a trovare i vettori di altri due assi?
- 6. Implementazione di un iteratore su un albero di ricerca binario
- 7. Trova un loop in un albero binario
- 8. In Albero binario, trovare quanti nonni hanno solo due o tre grandchildrens
- 9. eliminazione ricorsiva su un albero binario
- 10. Determinare se un albero binario è sottostruttura di un altro albero binario utilizzando le stringhe pre-ordine e in ordine
- 11. Mantenere un albero binario bilanciato quando gli elementi vengono inseriti nell'ordine
- 12. Albero di ricerca binario su albero AVL
- 13. stampa un albero binario su un lato
- 14. BIT: utilizzando un albero indicizzato binario?
- 15. breadth-first attraversamento di un albero in javascript
- 16. Costruire un albero binario bilanciato con foldr
- 17. Come implementare un albero non binario
- 18. Creazione albero somma di albero binario Scala
- 19. Albero binario Ricerca in ampiezza
- 20. Come molti attraversamenti devono essere conosciuti per costruire un BST
- 21. Albero di attraversamento fatto da DefaultMutableTreeNode
- 22. Trasferimento ad albero binario
- 23. Albero binario dall'albero generale
- 24. Attraversamento una struttura ad albero generale partendo da un nodo arbitrario in C#
- 25. Programmazione genetica ad albero binario
- 26. C# - Albero binario semplice
- 27. stampa confine albero binario
- 28. Differenza tra albero binario completo e albero binario bilanciato
- 29. albero binario rappresentata utilizzando matrice
- 30. "Trovare tutto il codice in un dato binario equivale al problema di interruzione." Veramente?
Se si assegna solo l'attraversamento "inorder", è possibile costruire molti alberi binari diversi. Cioè, non puoi descrivere un albero "unico" usando solo "inorder". – Aziz