从二叉树中随机选择一个节点

我的树类:

public class BT{
   E value;
   BT left, right;

   public BT(E value)
   {
      this.value=value;
   }   

   public BT (E value, BT left, BT right) 
   {
      this.value = value;
      this.left = left;
      this.right = right;
   }

在生成树之后,如何从树中返回随机节点？我知道我生成的每棵树的节点的深度和数量.

因此,使用Random Integer方法并返回0和树大小之间的整数.

然后在树上进行广度/深度优先遍历,使用计数器,当它到达随机整数时返回节点.

Random rand = new Random();
int randomNum = rand.nextInt(treesize);
int count = -1;
Node randNode;

public static void getRandomTraversal(Node root){

    count++;

    if(count == randomNum)
        randNode = root;

    if(root.leftChild != null)
        getRandomTraversal(root.leftChild);

    if(root.rightChild != null)
        getRandomTraversal(root.rightChild);
}

或者,您可以将count删除为全局,并将其作为参数添加到递归函数中.虽然当树有多个孩子时,二元树并不容易.

Dennis和Jeroen的算法易于实现，但是O(n)。我相信我有一个O(log n)稍微复杂一些的算法。

每个节点都需要被选择的机会均等。因此，在某棵树上T，令其LN(T)为左侧树中RN(T)的节点数，为右侧树中的节点数，并N(T)为总节点数（包括该节点（so N(T) = 1 + LN(T) + RN(T)））。R从中选择一个随机数0 to N(T) - 1。如果为R == 0，则返回此节点。如果为1 <= R <= LT(N)，则将此方法在左侧子树上递归。否则，请在右侧子树上递归此方法。

未经测试的代码（假设BT有一种.size()可在中使用的方法O(1)）：

public BT randomNode() {
    int r = new Random().nextInt(this.size());
    if (r == 0) {
        return this;
    } else if (left != null && 1 <= r && r <= left.size()) {
        return left.randomNode();
    } else {
        return right.randomNode();
    }
}

当然，您可以执行一些new Random()方法，例如将方法从方法中提升出来，但是算法是相同的。

编辑：修复了左子树为空时的空指针异常。