Costruire un albero con attraversamento di prenotazione dato

Question

Viene fornito un tipo speciale di albero in cui tutte le foglie sono contrassegnate con L e altre sono contrassegnate con N. Ogni nodo può avere 0 o al massimo 2 nodi. Viene dato il preordine trasversale dell'albero.

Assegna un algoritmo per costruire l'albero da questa traversata.

Answer 1

Questo è l'algoritmo di preorder di attraversamento:

Preorder(T) 
    if (T is not null) 
    print T.label 
    Preorder(T.left) 
    Preorder(T.right) 

Cerchiamo di trovare un algoritmo per un ingresso di NNLLNL.

Ovviamente l'etichetta della radice viene stampata per prima. Quindi sai che la radice ha l'etichetta N. Ora l'algoritmo ricorre nella sottostruttura di sinistra. Questo è anche N secondo l'input. Recurse sul sottoalbero sinistro di quello, che è L. Ora devi tornare indietro, perché hai raggiunto una foglia. La successiva posizione nell'input è anche L, quindi il nodo corrente ha un figlio destro etichettato con L. Backtrack una volta. Backtrack di nuovo, perché hai aggiunto tutti i figli del nodo corrente (max 2 figli). Ora sei di nuovo alla radice. Devi andare bene, perché sei già andato a sinistra. Secondo l'input, questo è N. Quindi il figlio destro della radice è N. Il figlio di sinistra sarà L. Questo è il tuo albero:

 N 
    / \ 
    N  N 
/\ /
    L L L 

Si noti che la soluzione non è necessariamente unica, ma questo vi porterà una possibile soluzione.

Pseudocode:

k = 0 
input = ... get preorder traversal vector from user ... 
Reconstruct(T) 
    if input[k] == N 
    T = new node with label N 
    k = k + 1 
    Reconstruct(T.left) 
    Reconstruct(T.right) 
    else 
    T = new node with label L 
    T.left = T.right = null 
    k = k + 1 

chiamata con un nodo nullo.

Domanda di follow-up: dato sia il preordine che l'inorder traversal di un albero binario contenente etichette di nodi distinti, come è possibile ricostruire in modo univoco l'albero?