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

Question

从概念上讲,通过从给定的叶子节点(而不是根节点)开始并使用父指针到达根目录,可以在其中遍历它的树吗？

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

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

Answer 1

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

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

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

你也可以这样想区块链。每个块都存储对其父块的反向引用。通过从任何块开始并向后追踪到根，您可以恢复该块编码的状态。

希望这可以帮助！