Traversée d'arbres - commençant à partir de feuilles avec seulement des pointeurs parents?

Question

Est-il conceptuellement possible d'avoir un arbre où vous le traversez en commençant à un nœud feuille donné (plutôt que le nœud racine) et d'utiliser des pointeurs parent pour atteindre la racine? Je demande cela depuis que j'ai vu quelqu'un implémenter un arbre et ils ont utilisé un tableau pour contenir tous les nœuds feuilles/nœuds externes et chacun des nœuds feuille/externes pointent uniquement vers leurs nœuds parents et ceux parent vers leur parent nœud etc. jusqu'à ce que vous arriviez au nœud racine qui n'a pas de parents. Leur implémentation nécessiterait donc que vous commenciez à l'une des feuilles pour vous rendre n'importe où dans l'arbre et que vous ne puissiez pas descendre l'arbre car ses nœuds d'arbre n'ont pas de pointeurs enfants, seulement des pointeurs parents.

J'ai trouvé cette implémentation intéressante puisque je n'ai rien vu de tel mais j'étais curieux de savoir si cela pouvait encore être considéré comme un "arbre". Je n'ai jamais vu un arbre où l'on commence la traversée des feuilles au lieu de la racine. Je n'ai également jamais vu un arbre où les nœuds de l'arbre ont seulement des pointeurs parents et pas de pointeurs enfants.

Answer 1

Oui, cette structure existe. Il est souvent appelé .

Les empilements de spaghettis sont utiles pour représenter la relation "fait partie de". Par exemple, si vous voulez représenter une hiérarchie de classe d'une manière qui rend la diffusion ascendante efficace, vous pouvez représenter la hiérarchie de classes comme une pile spaghetti dans laquelle le nœud de chaque type stocke un pointeur sur son type parent. De cette façon, il est facile de trouver si un upcast est valide en remontant simplement le noeud.

Ils sont également souvent utilisés dans les compilateurs pour suivre les informations de portée. Chaque nœud représente une étendue dans le programme, et chaque nœud a un pointeur sur le nœud représentant l'étendue d'un niveau au-dessus.

Espérons que cela aide!

Answer 2

Si un tableau A de nœuds feuille est donné, la traversée est possible. Si seulement un seul nœud feuille est donné, je ne sais pas comment traverser l'arbre. Pseudocode:

// 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