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

Question

从概念上讲，是否可以通过从给定的叶节点(而不是根节点)开始遍历树并使用父指针到达根来遍历树？

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

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

Answer 1

是的，这种结构是存在的。它通常被称为 spaghetti stack .

Spaghetti stacks 对于表示“is a part of”关系很有用。例如，如果您想以一种使向上转换有效的方式表示类层次结构，那么您可以将类层次结构表示为意大利面条式堆栈，其中每种类型的节点都存储一个指向其父类型的指针。这样，只需从节点向上走就可以很容易地确定向上转换是否有效。

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

希望这可以帮助!