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

18 浏览
0 Comments

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

在一棵树中，我们可以从给定的叶节点（而不是根节点）开始遍历，使用父指针到达根节点是可能的，这个概念是可行的吗？

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

我发现这个实现非常有趣，因为我从来没有看到过这样的实现，但我很好奇这是否仍然可以视为“树”。我从来没有看到过从叶子开始遍历的树，而不是从根开始遍历的树。我也从来没有看到过树节点只有父指针而没有子节点指针的树。

admin 更改状态以发布 2023年5月23日
0

2 答案

0 Comments

如果给定了叶节点数组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

0
0 Comments

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

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

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

你也可以这样看待区块链。每个区块都存储了其父区块的后向引用。通过从任何一个区块开始向后追踪到根，就可以恢复由该区块编码的状态。

希望这可以帮助你！

0