如何从树中获取随机节点？

Question

看起来很简单，但我发现实现起来很棘手。我需要它来解决我正在尝试实现的简单遗传编程问题。给定一个节点，该函数应该返回该节点本身或其任何子节点，以便选择一个节点的概率相对于其深度呈正态分布（因此该函数应该主要返回中间节点，但有时返回根本身或最低节点）那些 - 但如果这使它变得更加复杂，那么这并不是真正必要的，如果以相同的概率选择所有节点，那就足够了）。

谢谢

Answer 1

对于统一情况，如果您知道每个节点的深度，则可以使用概率 size(left)/size(this) 向左移动，使用概率 size(right)/size(this) 向右移动，否则选择当前节点。每个时刻一个随机数就足够了：

int r = rand() % size(this);
if (r < size(left)) { /* go left */ }
else if (r > size(left)) { /* go right */ }
else { /* pick this node */ }

事实上，通过一些调整，您可能可以将一个随机数向下传递以在每个节点上使用。经过一番思考，是的，你可以：如果你向左走，则使用未修改的 r ；如果向右走，则从 r 中减去 (size(left) - 1)。

对于正态分布，只需使用平均值为深度一半的正态分布随机变量来提前选择深度，然后回到上述算法。请注意，这将根据其子树的相对大小在中间节点之间分布，而不是均匀分布。