Come trovare il vicino più vicino a destra in un albero?

Question

Come trovare il vicino più vicino a destra in un albero?

#1 da (1 voti)
#2 da (0 voti)

4

Data una classe:

public class Node
{
  public List nodes[];
  public Node right;   //NULL for now
}

Qual è il modo migliore per riempire l'elemento "giusto" di tutti i nodi dell'albero?

                        N
                        |
                        |
                      / | \
                    /   |   \
                  C1--->C2-->C3
                  / \         \
                 /   \         \
                C11->C12 -----> C31

algorithms trees

posta qasimzee 03.09.2015 - 02:23

fonte

2 risposte

Leggi altre domande sui tag algorithms trees

Algoritmo per determinare la migliore combinazione di tenere insieme gli studenti nelle loro stanze da campo OAuth 2.0 - L'identificatore del client deve essere univoco per ciascun utente o solo per tipo di cliente?

score 1 · Answer 1

Puoi fare BFS normale dove ad ogni livello determini il diritto di ogni nodo, qualcosa come questo pseudocodice.

while(queue of nodes is not empty) {
  get size of queue into curLevelNodes
  while(curLevelNodes is not zero) {
    get current node into curNode
    if there is a next node in the same level get it into nxtNode
    curNode->right = nxtNode

    don't forget to push the children of curNode to the queue

    remove curNode from the queue

    decrement curLevelNodes by one
  }
}

Direi di rendere la variabile right come puntatore.

L'unico problema qui è che non c'è alcuna garanzia su quale nodo avrà ragione di quale nodo, seguirà solo l'ordine di inserimento.

score 0 · Answer 2

Un modo per strutturare questo è usare un array multidimensionale. In questo modo, una dimensione può rappresentare colonne e le altre righe. Quindi, la posizione dell'array [11,127] punta al nodo della colonna 11, riga 127. Ciò rende anche molto semplice la visualizzazione della struttura in uno spazio 2D.

Per trovare il nodo a destra di un altro, basta incrementare la dimensione della colonna dei nodi di destinazione, ad esempio:

var rightNeighbour = nodes[thisNode.Column +1, thisNode.Row]