Nell'albero sottostante,
typedef struct lcrsNode{
void *item;
struct lcrsNode *parent;
struct lcrsNode *firstChild;
struct lcrsNode *nextSibling;
}lcrsNode;
typedef struct Tree{
lcrsNode *root;
int size; // Number of nodes;
}Tree;
Quali sono i vantaggi del mantenimento del puntatore genitore in un nodo ad albero? Aiuta ad eseguire DFS senza ricorsione o stack esplicito?
DFS o Prima ricerca di profondità è una forma di tree traversal
DFS significa che devi discendere i bambini il più lontano possibile, quindi risalire al genitore per farlo di nuovo (vedi linea tratteggiata). È difficile da fare se il nodo non punta al genitore. Se non è così, devi in qualche modo ricordare dove il genitore è, per così dire, ricorsione o pila esplicita. Se il nodo conosce il suo genitore, allora è sufficiente una semplice iterazione per implementare un DFS.
Se questo è per un compito a casa, ricorda che il tuo istruttore può cercare e trovare questo con la massima facilità possibile. Mostra che puoi pensarci da solo.
Leggi altre domande sui tag c data-structures trees