Trova l'occorrenza successiva in un albero

Question

Trova l'occorrenza successiva in un albero

#1 da (2 voti)

2

Avere un albero con profondità e larghezza variabili. Qual è il miglior algoritmo per trovare la prossima occorrenza del nodo in quell'albero.

Next = Cerca sul lato destro dell'albero (come nella prima ricerca della larghezza)

I criteri di selezione per la prossima occorrenza dell'albero sono modificabili in diverse situazioni.

Ad esempio, in un punto, voglio trovare l'occorrenza successiva del nodo che contiene il valore uguale al nodo corrente.

In un altro, voglio selezionare il valore successivo che è inferiore al valore corrente.

Una volta trovata la prossima occorrenza, il programma può terminare e restituire il valore o il nodo.

          5
     6           9
 10  7  0      5 6 8
5  6   9 5

Supponiamo di avere un puntatore al nodo (depth = 4, value = 5, parent = 10) ... quando eseguo la ricerca voglio ottenere il puntatore al nodo (depth = 4, value = 5, parent = 0).

Diciamo che non c'è, allora voglio ottenere il nodo (depth = 1, value = 5, rootNode).

algorithms search

posta Boopathi Rajaa 01.07.2011 - 20:22

fonte

1 risposta

Leggi altre domande sui tag algorithms search

Il modo più efficace per trovare le entità in una griglia? Condivisione dei dati inter-processo e inter-thread [chiusa]

score 2 · Accepted Answer

Vuoi una ricerca in profondità modificata. La modifica è che deve avere il codice per capire dove si trova nella ricerca, quindi procedere da lì.

Supponiamo che ogni nodo abbia un parent e children . Quindi vuoi fare qualcosa di simile:

def find_next_in_tree(node, relation):
    answer = do_depth_first_search(node, relation)
    if answer:
        return answer
    while node.parent:
        old_node = node
        node = node.parent
        children = node.children

        # Find where node is in children.
        i = 0
        while i < children.length:
            if old_node == children[i]:
                break
            i += 1

        # Search remaining children
        i += 1
        while i < children.length:
            answer = do_depth_first_search(children[i], relation)
            if answer:
                return answer
            i += 1
    return None