Attraversamento dell'albero: a partire dalle foglie con solo indicatori parentali?

Question

È concettualmente possibile avere un albero in cui lo attraversi iniziando da un dato nodo foglia (anziché dal nodo radice) e usa i puntatori genitore per arrivare alla radice?

Lo chiedo da quando ho visto qualcuno implementare un albero e hanno usato un array per contenere tutti i nodi foglia/nodi esterni e ciascuno dei nodi foglia/esterni punta solo ai loro nodi padre e quei genitori puntano al loro genitore nodo ecc. fino ad arrivare al nodo radice che non ha genitori. La loro implementazione quindi richiederebbe di iniziare da una delle foglie per arrivare da qualche parte nell'albero e non si potrebbe andare "giù" dall'albero dato che i suoi nodi dell'albero non hanno alcun indicatore di bambini, ma solo indicatori genitore.

Ho trovato questa implementazione interessante dal momento che non ho visto nulla di simile ma ero curioso di poterlo considerare ancora come un "albero". Non ho mai visto un albero in cui inizi la traversata alle foglie, invece della radice. Inoltre, non ho mai visto un albero in cui i nodi dell'albero abbiano solo indicatori parentali e nessun puntatore ai bambini.

Answer 1

Sì, questa struttura esiste. Viene spesso chiamato .

Gli stack di spaghetti sono utili per rappresentare la relazione "è una parte di". Ad esempio, se si desidera rappresentare una gerarchia di classi in un modo che renda efficiente l'upcasting, è possibile rappresentare la gerarchia di classi come uno stack di spaghetti in cui il nodo per ogni tipo memorizza un puntatore al proprio tipo genitore. In questo modo, è facile scoprire se un upcast è valido semplicemente camminando verso l'alto dal nodo.

Sono spesso utilizzati anche nei compilatori per tracciare le informazioni di ambito. Ogni nodo rappresenta un ambito nel programma e ogni nodo ha un puntatore al nodo che rappresenta lo scope di un livello sopra di esso.

Spero che questo aiuti!

Answer 2

Se viene fornita una matrice A di nodi foglia, è possibile effettuare un attraversamento. Se viene dato un solo nodo foglia, non so come attraversare l'albero. Pseudocodice:

// initial step 
add all nodes in A to a queue Q 

//removeNode(Q) returns pointer to node at front of Q 
while((node = removeNode(Q)) != NULL) 
    /* do your operation on node */ 
    add node->parent to Q