遍历树叶节点而不遍历全树

Question

在具有父子指针的通用树结构中，是否可以遍历叶节点而不遍历整棵树？例如，从最左边的叶节点开始。想法是在深树上进行优化。

Answer 1

没有。要到达每一片叶子，您必须遍历每个节点。

因为树是无环的，所以没有冗余路径。因此，没有 "extra" 种到达地点的方法，因此也没有捷径可走。每个节点要么是 (a) 叶子，要么 (b) 在通往一个或多个叶子的关键路径上。

必须以某种方式增强数据结构以优化叶遍历。

Answer 2

如果用普通的 c++ 指针方式表示树，根指向子节点，则无法实现，因为树是无环图。

如果您以不同的方式表示树（比如使用数组的堆），您可以只遍历子项，因为它们在数组中处于偏移量。

请注意，平衡 二叉树的叶子占树大小的一半，因此仅遍历叶子不会增加复杂性。对于 balanced 三元树和其他几乎完整的 n 元树，该分数是一个更大的数字。