树遍历-从只有父指针的叶子开始？

Question

从概念上讲，是否可能有一个树，您可以从给定的叶节点（而不是根节点）开始遍历它，并使用父指针到达根？

我问这个问题是因为我看到有人实现了一个树，他们使用一个数组来保存所有叶节点/外部节点，每个叶节点/外部节点只指向它们的父节点，而那些父节点指向它们的父节点等等，直到你到达没有父节点的根节点。因此，它们的实现要求您从一片叶子开始，到达树中的任何地方，并且您不能“向下”树，因为她的树节点没有任何子指针，只有父指针。

我发现这个实现很有趣，因为我没有见过类似的东西，但我很好奇它是否仍然可以被视为一棵“树”。我从来没有见过一棵树是从叶子而不是根开始遍历的。我还从未见过树节点只有父指针而没有子指针的树。

Answer 1

如果给定叶节点的数组A，则可以进行遍历。如果只给出一个叶子节点，我不知道如何遍历树。伪代码：

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

Answer 2

是的，这种结构是存在的。它通常被称为意大利面条堆。

意大利面堆对于表示“是的一部分”关系很有用。例如，如果您希望以一种使升级高效的方式表示类层次结构，那么可以将类层次结构表示为一个意大利面堆栈，每个类型的节点在其中存储指向其父类型的指针。这样，只需从节点向上走，就可以很容易地发现向上投射是否有效。

它们还经常在编译器中用于跟踪作用域信息。每个节点表示程序中的一个作用域，每个节点都有一个指向该节点的指针，该节点表示其上一级的作用域。

希望这能有所帮助！