Percorso radice-foglia più breve

Question

Qual è il modo più semplice, preferibilmente usando la ricorsione, per trovare il percorso radice-foglia più breve in un BST (Binary Search Tree). Preferiva Java, pseudocodice ok.

Grazie!

Answer 1

Descrizione generale:

Utilizza una Ricerca per primo (BFS) anziché una Ricerca prima profondità (DFS) . Trova il primo nodo senza figli.

Usando un DFS potresti essere fortunato su alcuni alberi di input (ma non c'è modo di sapere che sei fortunato, quindi devi ancora cercare l'intero albero), ma usare il metodo BFS è molto più veloce e puoi trovare una soluzione senza toccare tutti i nodi.

Per trovare il percorso radice-foglia, è possibile seguire il primo nodo senza figlio trovato fino alla radice utilizzando il riferimento principale. Se non è presente alcun riferimento principale archiviato in ciascun nodo, è possibile tenere traccia dei nodi principali mentre si ricorre verso il basso. Se il tuo elenco è in ordine inverso, puoi metterlo tutto in pila e poi saltarlo fuori.

pseudo-codice:

Il problema è molto semplice; ecco il pseudo codice per trovare la lunghezza più piccola:

1. Mette il nodo radice sulla coda.

Ripeti finché la coda non è vuota e non è stato trovato alcun risultato:

2. Estrai un nodo dall'inizio della coda e controlla se non ha figli. Se non ha figli, tu hai finito hai trovato il percorso più breve.
3. Altrimenti, spingi tutti i bambini (a sinistra, a destra) sulla coda.

Ricerca di tutti i percorsi più brevi:

Per trovare tutti i percorsi più brevi è possibile memorizzare la profondità del nodo insieme al nodo all'interno della coda. Quindi continuerai l'algoritmo per tutti i nodi nella coda con la stessa profondità.

Alternativa:

Se invece decidessi di usare un DFS, dovresti cercare nell'intero albero per trovare il percorso più breve. Ma questo potrebbe essere ottimizzato mantenendo un valore per il più breve finora e controllando solo la profondità dei nodi futuri fino a quando non si trova un nuovo più breve o fino a quando non si raggiunge il più breve finora. Il BFS è comunque una soluzione molto migliore.

Answer 2

Questo è in C ++, ma è così semplice che puoi convertirlo facilmente. Basta cambiare da min a max per ottenere la massima profondità dell'albero.

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

Giusto per spiegare cosa sta facendo, sta contando dal nodo foglia (restituisce 0 quando trova una foglia) e ritorna alla radice. Fare questo per i lati sinistro e destro dell'albero e prendere il minimo ti darà il percorso più breve.

Answer 3

L'ampiezza della prima ricerca è esattamente ottimale in termini di numero di vertici visitati. Devi visitare tutti i vertici che visiteresti in una prima ampia ricerca solo per dimostrare che hai la foglia più vicina!

Tuttavia, se hai il mandato di ricorrere alla ricorsione, l'approccio di Mike Thompson è quasi quello giusto da usare - ed è leggermente più semplice.

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf 

Answer 4

static int findCheapestPathSimple (radice TreeNode) {

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}