在没有完整树遍历的情况下遍历树叶节点

Question

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

Answer 1

哈哈要到达每个叶子，您必须遍历每个节点。

因为树是非循环的，所以没有冗余路径。因此，没有“额外”的方法来获得位置，因此也没有捷径可走。每个节点要么是（a）叶，要么是（b）到一个或多个叶的关键路径上。

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

Answer 2

如果用普通的c指针方式表示树，并且根指向子级，则无法实现这一点，因为树是一个非循环图。

如果您以不同的方式表示树（例如使用数组作为堆），您只能遍历子级，因为它们位于数组中的偏移量处。

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