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

EN

对于均匀的情况，如果你知道每个节点的深度，你可以向左选择概率大小(左)/size(这)，向右选择概率大小(右)/size(这)，否则选择当前节点。每个结合点的单个随机数应该足够了：

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)。

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