Come trovare sotto-alberi nell'albero non binario

Question

Come trovare sotto-alberi nell'albero non binario

Naviga le tue risposte

#1 da (1 voti)

5

Ho un albero non binario.
Voglio trovare tutti i "sotto-alberi" che sono connessi a root.

Il sottoalbero è un gruppo di collegamenti di nodi ad albero.

ognigruppoècoloratonelpropriocolore.

Qualesarebbel'approcciomigliore?Eseguilaricorsioneversol'altoeversol'altoperogninodo?

Lastrutturadeidatidiognitreenodeèunalistadibambini,lalistadeigenitori.(iltipodibambiniegenitorisonotreenodes)

Chiarificazione:

Gruppodefinitoseesisteunasortadi"chiusura" tra i nodi in cui la radice stessa non fa parte della chiusura.
Come puoi vedere dal grafico non puoi viaggiare da rosa ad altri nodi (NON puoi usare root).
Dal nodo marrone puoi viaggiare fino al suo bambino così da formare un altro gruppo.

Finalmente puoi viaggiare da qualsiasi nodo ciano ad altri nodi ciano così da formare un altro gruppo

java algorithms trees

posta kenny 10.01.2012 - 10:15

fonte

1 risposta

Leggi altre domande sui tag java algorithms trees

C'è stato un lavoro formale che paragonasse la facilità di manutenzione a livello di linguaggio di programmazione? I DSL personalizzati sono ancora validi?

score 1 · Answer 1

Potresti usare un algoritmo BFS (un algoritmo grafico spiegato su Wikipedia ), a partire dal nodo che vuoi per rendere root.

L'algoritmo si comporta in questo modo:

procedure BFS(G,v,btree):
      create a queue Q
      enqueue v onto Q
      mark v
      btree = new Tree(v);//Create a tree structure with v as root
      while Q is not empty:
          t ← Q.dequeue()
          btree.add(t) // Here its where you add elements to your tree
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q

Quando Q è vuoto significa che hai elaborato tutti i possibili nodi e che tutti sono stati aggiunti al tuo albero binario (btree).

Una volta che hai il tuo btree puoi applicare qualsiasi semplice algoritmo per ottenere quello che ti serve