7

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

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

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

4

2 回答 2

4

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

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

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

希望这可以帮助！

于 2013-03-11T18:02:33.003 回答
0

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
于 2013-03-11T18:02:35.383 回答