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
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.
Se si assegna solo l'attraversamento "inorder", è possibile costruire molti alberi binari diversi. Cioè, non puoi descrivere un albero "unico" usando solo "inorder". – Aziz