Assegnazione di una profondità a ciascun nodo

Question

Ho letto alcuni altri articoli qui che sembravano simili, ma non rispondevano del tutto al mio problema. Mi è stata data una domanda per un incarico per assegnare ad ogni nodo di un albero binario la sua rispettiva profondità. Non riesco a capirlo.

Per riferimento questo è il mio codice:

struct treeNode { 
    int item; 
    int depth; 
    treeNode *left; 
    treeNode *right; 
}; 
typedef treeNode *Tree; 

int assignDepth(Tree &T, int depth) 
{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 
     T->depth = depth; 
     depth = assignDepth(T->right, depth++); 
    } 
    else //leaf 
     return depth--; 
} 

ho provato a fare funzionare attraverso con carta e penna e sembrava OK, ma la mia scrivania controllando le competenze sono chiaramente carente.

Qualcuno può indicarmi la direzione giusta, per favore? Questa è la prima volta che uso gli alberi e la ricorsione non è il mio punto di forza.

Risposta:

void treecoords(Tree &T, int depth) 
{ 
    static int count = -1; //set to -1 so the precrement before assignment doesn't give the wrong values 
    if(T!=NULL) 
    { 
     treecoords(T->left, depth+1); //depth decrements automatically once this function call is removed from the stack 
     count++; 
     T->x = count; 
      T->y = depth; 
     treecoords(T->right, depth+1); 
    } 
} 

Answer 1

È don' t bisogno

else //leaf 
    return depth--; 

Inoltre non vuole incrementare la variabile di profondità, basta passare la profondità + 1 per la prossima iterazione.

Inoltre, non è necessario restituire un valore.

Prova questa:

void assignDepth(Tree T, int depth) 
{ 
    if(T!=NULL) 
    { 
     assignDepth(T->left, depth+1); 
     T->depth = depth; 
     assignDepth(T->right, depth+1); 
    } 
} 

Answer 2

Beh, per cominciare, si sta utilizzando post-incremento/decremento, probabilmente significava ++depth/--depth per l'assegnazione a destra e l'altro di ritorno;

Inoltre, perché passare un puntatore come variabile di riferimento?

Answer 3

int assignDepth(Tree &T, int depth) 

Hai definito Tree come un puntatore a un treeNode. Non è necessario passarlo per riferimento. È possibile modificare il nodo puntato comunque.

{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 

Il suffisso ++ assicura che si sta passando l'originale depth verso il basso. Non è quello che vuoi. Incrementare depth prima di questo e dimenticarsi di restituirlo come risultato di una funzione.

T->depth = depth; 

Questo è OK.

 depth = assignDepth(T->right, depth++); 

Simile come per il precedente chiamata ricorsiva, solo che qui non si deve modificare depth a tutti perché è già stato incrementato.

} 
    else //leaf 
     return depth--; 

Non è necessario restituire alcuna informazione di profondità (o è un requisito non dichiarato?).

} 

Acclamazioni & hth.,

Answer 4

1. Una volta raggiunto un nodo foglia, non si preoccupano di sua profondità più, quindi il valore di ritorno sembra fare nulla.

2. In due istruzioni:

   depth = assignDepth(T->left, depth++); 
   // and 
   depth = assignDepth(T->right, depth++); 
   

Hai comportamento indefinito di modificare depth due volte senza un punto sequenza intermedio (anche se sembra che ci dovrebbe essere, c'è non un punto sequenza tra i lati destro e sinistro di un incarico).

Answer 5

1. Perché si ritorna quando il nodo è NULL. Secondo le vostre specifiche non è necessario restituire alcuna profondità

2. In altri casi è sufficiente aumentare la profondità e inviare alla chiamata di funzione. Quello che segue è la mia versione del codice

   assignDepth void (Albero & T, int profondità) { se (T == null) ritorno; altro { T-> profondità = profondità; se (T-> left! = NULL) assignDepth (T-> left, depth + 1); se (T-> right! = NULL) assignDepth (T-> right, depth + 1); }}

Answer 6

Ho un design leggermente più complicato con diversi tipi di nodi e fatto questo, così ho pensato quota id.

Se si dispone di un albero che varia nel tipo Nodo su nodo (Binario, Unario ecc.), È opportuno semplificare il metodo tradizionale per evitare che gli IF incorporati scorretti controllino il tipo di nodi.

due funzioni:

• 1: Dalla radice, attraversano ciascun nodo e controllare la sua distanza dalla radice chiamando recursivly stessa e aggiungendo 1 per ciascun genitore. Dare a ogni nodo una variabile di profondità per archiviarlo.
• 2: dal set completo di Nodi nella struttura eseguire un controllo MAX in corrispondenza della profondità di ciascun nodo, il numero più alto sarà uguale alla profondità dell'albero .

L'elaborazione in questo modo rimuove il controllo esplicito del tipo e conta semplicemente il nodo, indipendentemente dal fatto che abbia uno, due o cento figli.

Spero che questo aiuti qualcuno!