Ricerca della sottostruttura in un albero

Question

#1 da (2 voti)

3

Ho un albero:

    a
   / \
  b   c
 / \
d   f
   / \ 
  g   h

E il modello:

    x
   / \
  y   z
 / \
q   p

Come output mi piacerebbe avere:

x: a
y: b
z: c
q: d
p: f

e

x: b
y: f
z: c
q: g
p: h

C'è qualche algoritmo che potrei esaminare?

trees graph

posta zie1ony 25.02.2013 - 22:46

fonte

1 risposta

Leggi altre domande sui tag trees graph

score 2 · Accepted Answer

Appiattisci il tuo pattern in una vasta serie di tuple tra cui il nome nodo , profondità e indice , come:

(a,0,0), (b,1,0), (c,1,1), (d,2,0)...
Attraversa (o appiattisci) l'albero di input in ordine di larghezza, utilizzando idealmente lo stesso metodo.
L'n-esimo elemento dell'array di pattern corrisponderà all'elemento n-es nell'albero di input, assumendo che ce ne sia uno. Puoi utilizzare i valori di profondità e indice di ciascuna tupla per saltare avanti finché qualcosa non corrisponde.

Ci sono esempi di codice di attraversamento di ampiezza davvero buoni dappertutto, dovrebbe essere facile trovarne uno nella lingua che preferisci.