Determinare se un albero binario è sottostruttura di un altro albero binario utilizzando le stringhe pre-ordine e in ordine

Question

Voglio sapere se l'albero binario T2 è una sottostruttura di albero binario T1. Ho letto che si potevano costruire rappresentazioni di stringhe per T2 e T1 usando gli attraversamenti in preordine e in ordine e se le stringhe T2 sono sottostringhe delle stringhe T1, T2 è un sottoalbero di T1.

Sono un po 'confuso da questo metodo e non sono sicuro della sua correttezza.

Da wiki: "Un sottoalbero di un albero T è un albero costituito da un nodo in T e tutti i suoi discendenti in T."

Nel seguente esempio:

T2: 
    1 
/\ 
2 3 

T1: 
    1 
/\ 
2 3 
    \ 
     4 

Se costruiamo le stringhe per T2 e T1:

preordine T2: "1,2,3"
preordine T1: "1,2, 3,4"
simmetrico T2: "2,1,3"
simmetrico T1: "2,1,3,4"

le corde T2 sono sottostringhe di T1, in modo da utilizzare il metodo sottostringa corrispondente d descritto sopra, dovremmo concludere che T2 è un sottoalbero di T1.

Tuttavia, T2 per definizione non deve essere una sottostruttura di T1 poiché non ha tutti i discendenti del nodo radice di T1.

C'è una discussione correlata here, che sembra concludere che il metodo sia corretto.

Mi manca qualcosa qui?

Answer 1

Domanda molto interessante. Sembri corretto. Suppongo che il problema da lei menzionato sia dovuto a diverse definizioni di sottostruttura in math (graph theory) e in informatica. Nella teoria dei grafi T2 è un sottostruttura corretta di T1.

Answer 2

La definizione di sottoalbero di un albero deve essere uguale alla definizione di sottostringa di una stringa. Pensa in questo modo: 1. la sottostringa ha inizio-con, contiene e termina con. 2. La struttura ad albero deve avere anche la stessa definizione, ma generalizzata per adattarsi alla struttura dei dati Albero. 3. La generalizzazione è da 1 dimensionale per stringa a 2 dimensionale per albero.

Answer 3

Sto leggendo lo stesso libro e dubito anche della sua soluzione. Mi è venuto in mente un altro contro-esempio che non rientra nella potenziale interpretazione che menziona il pasticcio dell'utente (di una sottostruttura che non richiede necessariamente tutti i discendenti).

Si consideri il seguente alberi

T2: 
    B 
/\ 
A C 

T1: 
    C 
/\ 
    B C 
/
A 

preordine T2: 'BAC'
preordine T1: 'CBAC'
ordine simmetrico T2: 'ABC'
ordine simmetrico T1: 'ABCC'

Ancora una volta, le stringhe T2 sono sottostringhe delle loro controparti T1 e tuttavia T2 non è in alcun modo un sottoalbero di T1. Forse nell'autore aveva escluso i duplicati e menzionato espressamente la sua definizione di sottostruttura poteva essere giusto, ma tralasciando quell'informazione non ci resta altra scelta che considerarla una soluzione sbagliata.

Answer 4

Na ... Questo approccio non è corretto. Perché diversi alberi possono avere la stessa traversata. Per esempio qui nell'esempio citato, l'albero è

  26 
     / \ 
     10  3 
    / \  \ 
    4  6  3 
    \ 
    30 

e sottoalberi candidati sono

10 
/\ 
4 6 
\ 
30 

e

30 
/\ 
4 10 
\ 
6 

avere lo stesso ordine simmetrico come 4,30,10, 6 ma il secondo non è sottostruttura

Answer 5

Supponendo che tu abbia preso questo dal libro "Crac re the Coding Interview ", l'autore menziona anche che per distinguere tra nodi con gli stessi valori, si dovrebbero anche stampare i valori nulli.

Ciò consentirebbe anche di risolvere il problema con la definizione di una sottostruttura (che è corretto, come descritto anche nel libro)

preordine T2: "1, 2, null, null, 3, null, null" preorder T1: "1, 2, null, null, 3, null, 4, null, null" inorder T2: "null, 2, null, 1, null, 3, null" inorder T1: "null, 2, null, 1, null, 3, null, 4, null"

come si può vedere, T2 non è una sottostruttura di T1