Esercizio 6preorder e postorder compatibili

Richiami

In un albero ordinato (vedi Visite di alberiVisite in preorder e postorder come schemi generali (template) da adattare; complessità Theta(n + somma dei costi di visita) perché la somma dei figli è n-1; esempi (indice di un libro, spazio occupato in un file system); profondità con il preorder, altezza con il postorder; antenato comune più basso.Visite di alberi →):

• il preorder visita prima il nodo e poi i sottoalberi dei figli da sinistra a destra: la radice è la prima della sequenza;
• il postorder visita prima i sottoalberi dei figli e poi il nodo: la radice è l'ultima;
• ogni sottoalbero occupa un blocco contiguo di nodi in entrambe le sequenze: in preorder inizia con la sua radice, in postorder finisce con la sua radice.

1. Quale può essere il postorder

La radice è $A$ (prima in preorder), quindi deve essere l'ultima in postorder.

• $BAFECD$: l'ultimo è $D$, non $A$ $\Rightarrow$ impossibile.
• $CDAEFB$: l'ultimo è $B$ $\Rightarrow$ impossibile.
• $CDBFEA$: l'ultimo è $A$; verificato al punto 2 che esiste un albero compatibile $\Rightarrow$ possibile.

2. Ricostruzione dell'albero

Preorder $ABCDEF$, postorder $CDBFEA$. Tolta la radice $A$ restano $BCDEF$ (preorder) e $CDBFE$ (postorder); bisogna spezzarle in blocchi che corrispondono ai sottoalberi dei figli di $A$.

• Il primo figlio di $A$ è $B$ (primo in preorder dopo $A$). In postorder il blocco del suo sottoalbero finisce con $B$: $CDB$. Quindi il sottoalbero di $B$ contiene $\{B, C, D\}$, con preorder $BCD$ e postorder $CDB$.
  • Tolta la radice $B$: preorder $CD$, postorder $CD$. Se $C$ avesse $D$ come discendente, in postorder $D$ precederebbe $C$; poiché in postorder $C$ viene prima, $C$ e $D$ sono due foglie fratelli, figli di $B$.
• Il blocco rimanente è $EF$ in preorder e $FE$ in postorder: $E$ è la radice (primo in preorder, ultimo in postorder) e $F$ è suo figlio.

L'albero è:

        A
      /   \
     B     E
    / \     \
   C   D     F

Controllo: preorder $A, B, C, D, E, F$ ✓; postorder $C, D, B, F, E, A$ ✓. L'albero è anche unico: $B$ non può essere una foglia, perché allora sarebbe il primo in postorder, mentre il primo è $C$. (Verificato enumerando tutti i $42$ alberi ordinati con preorder $ABCDEF$ e radice $A$: solo questo ha postorder $CDBFEA$; per $BAFECD$ e $CDAEFB$ non ce ne sono.)

Osservazione generale

Due nodi $X, Y$ con $X$ prima di $Y$ in preorder: se in postorder $X$ viene dopo $Y$, $X$ è antenato di $Y$; se viene prima, $X$ sta a sinistra di $Y$ (non è un antenato). In un albero ordinato (non binario) preorder e postorder insieme determinano l'albero in modo unico (verificato su tutti i $42$ alberi di $6$ nodi: i postorder sono tutti distinti); in un albero binario no, perché un unico figlio può essere il sinistro o il destro.

Errori comuni

• Non controllare che la radice sia l'ultima del postorder: scarta subito due delle tre sequenze.
• Confondere postorder con l'inverso del preorder: sono diversi (in generale $CDBFEA \ne$ inverso di $ABCDEF$).
• Dimenticare che ogni sottoalbero è un blocco contiguo in entrambe le sequenze.