Un albero binario contiene un altro albero?

Question

ragazzi Va bene, mi è stato chiesto a questa domanda in un'intervista oggi e va in questo modo:

"Dillo, se un albero binario è contenuto all'interno di un altro albero binario o meno (contiene implica sia nella struttura ed il valore dei nodi)"

ho pensato alla seguente approccio:

appiattire l'albero più grande come:

{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}} 

(ho fatto in realtà scrivere il codice per questo, {-} implica vuoto lef t o destra sotto-albero, ogni sotto-albero è racchiuso all'interno di {} paranthesis)

Ora per i più piccoli sotto-albero abbiamo bisogno di corrispondere a questo modello:

{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}} 

dove {.*} denota un vuoto o non sottostruttura vuota.

Nel momento in cui ho pensato, si tratterebbe di un semplice motivo di associazione di espressioni regolari in java, ma sono confuso. In realtà ora mi sento, ho appena trasformato il problema (creato un mostro da un altro).

C'è un semplice regex di un rivestimento per abbinare questi modelli? Capisco che potrebbero esserci altri approcci per risolvere questo problema e questo potrebbe non essere il migliore. Mi chiedo solo se questo è risolvibile.

Answer 1

Non sono sicuro di cosa significasse esattamente l'intervistatore "contenuto in un altro albero binario". Se l'intervistatore chiedeva un metodo per controllare se A è una sottostruttura di B, qui è un metodo che non richiede regex affatto:

• appiattire gli alberi A e B con preordine attraversamento per ottenere le stringhe, dire , Prea e preb
• Appiattire gli alberi a e B con ordine simmetrico per ottenere le stringhe, per esempio, INA e INB
• Assicurati di includere l'ipotesi nulla lascia nelle stringhe così (usando spazi bianchi, per esempio)
• Controlla se preA è una sottostringa di preB AND inA è una sottostringa di inB

Il motivo per cui si desidera includere le foglie nulle è perché quando più nodi hanno lo stesso valore, il preordine e l'inorder potrebbero non essere sufficienti. Ecco un esempio:

  A 
     A  A 
    B  B  C 
C   D  B 
D   C  D 

È inoltre possibile controllare questo fuori:

checking subtrees using preorder and inorder strings

visualizzato anche questo per più informazioni anticipato e simmetrico attraversamenti di alberi binari:

http://en.wikipedia.org/wiki/Tree_traversal

Ora, se non intendesse solo sottoalberi, il problema potrebbe diventare più complicato a seconda di ciò che l'intervistatore significato da una "parte". Potresti considerare la domanda come un problema di isomorfismo del sottografo (gli alberi sono solo un sottoinsieme di grafici) e questo è NP-completo.

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

Ci possono essere migliori approcci in quanto gli alberi sono molto più ristretto e più semplice di grafici.

Answer 2

È possibile farlo utilizzando un controllo di stringa come descritto nelle altre risposte, e utilizzando solo uno attraversamento (pre-ordine, in ordine, o post-ordine), a condizione che si stampa il entirity di ogni nodo nella struttura, non solo i loro valori. Ad esempio, un albero binario è o

• l'albero vuoto, che verrà stampare come null, o
• un valore e due alberi, che stampiamo come (value left-tree right-tree), dove left-tree e right-tree sono sostituiti dalla rappresentazione dei sottoalberi sinistro e destro.

Ogni albero ha ora una rappresentazione stampata univoca, e quindi un albero T è una sottostruttura di un albero S se e solo se la rappresentazione di stringa di T è una sottostringa della stringa rappresentazione di S.

Per esempio, l'albero

A 
/\ 
    B C 
/\ 
D E 

è rappresentato come

(A (B (D null null) (E null null)) (C null null)) 

e si può verificare che le sottostrutture di questo albero hanno stringhe

(A (B (D null null) (E null null)) (C null null)) 
(B (D null null) (E null null)) 
(D null null) 
(E null null) 
(C null null) 

ciascuno dei quali è un sottostringa della stringa per l'intero albero.

Gli unici avvertimenti sono casi in cui le rappresentazioni di stringa dei valori interferiscono con la serializzazione degli alberi (ad esempio, le stringhe di valori contengono spazi, o parentesi, & c.), Quindi per rendere robusto, si ' d vuole prendere le misure appropriate con delimitatori o fughe.

Si noti inoltre che non tutte le stringhe che costituiscono una sottostringa di un albero corrispondono a una sottostringa di un albero. Ad esempio, la stringa null) (E è una sottostringa dell'albero, ma non corrisponde a un sottoalbero dell'albero; solo quando una stringa s è la rappresentazione di un albero t significa che se s è una stringa della stringa s' di un albero t' che t è una sottostruttura t '.

Answer 3

In senso stretto, regex non è in grado di gestire le parentesi nidificate. L'annidamento può essere abbinato utilizzando recursive regular expressions, ma il motore regex di Java non supporta le espressioni ricorsive.In Perl o PHP, si potrebbe usare un qualcosa di simile modello

{(?:(?R)|-)}\w{(?:(?R)|-)} 

per abbinare qualche struttura ad albero, ma non sarebbe ancora in grado di specificare i valori di nodi figlio a livelli specifici.

Quindi, purtroppo non esiste una riga semplice di regex che risolverà questo problema. Regex non è lo strumento necessario per questo lavoro.

Al fine di rispondere a questa domanda, consiglio costruire il vostro albero di grandi dimensioni e di piccolo albero, quindi chiamando largeTree.contains(smallTree) utilizzando la seguente classe:

public class BTreeNode 
{ 

public String value; 
public BTreeNode left; 
public BTreeNode right; 

public bool contains(BTreeNode tree) 
{ 
    bool retVal = visit(tree, this); 

    if (!retVal && left != null) 
    retVal = left.contains(tree.left); 

    if (!retVal && right != null) 
    retVal = right.contains(tree.right); 

    return retVal; 
} 

private bool visit(BTreeNode small, BTreeNode large) 
{ 
    bool retVal; 

    if (small == null) 
    { 
    retVal = true; 
    } 
    else if (small.value.equals(large.value)) 
    { 
    retVal = visit(small.left, large.left) && visit(small.right, large.right); 
    } 
    else 
    { 
    retVal = false; 
    } 

    return retVal; 
} 

} 

caso peggiore, un attraversamento del piccolo albero sarà eseguita per ogni nodo dell'albero grande, che è O(m * log n) dove m è la dimensione dell'albero grande e n è la dimensione dell'albero piccolo. il caso peggiore si può ottenere quando tutti gli elementi dell'albero grande e quello piccolo sono uguali e il piccolo albero è in realtà un nodo più grande dell'albero grande.