从二叉树中随机选择节点 [英] Randomly select a node from a Binary Tree

问题描述

我的树类：

public class BT<E>{
   E value;
   BT<E> 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;
   }

在生成树之后，我将如何从树返回随机节点？我知道我生成的每个树的深度和节点数。

推荐答案

丹尼斯和杰伦的算法很容易实现，但是O(n)。我相信我的O(log n)算法稍微复杂一些。

每个节点都需要平等的被选中机会。因此，在某些树T中，设LN(T)为左树中的节点数，RN(T)为右树中的节点数，N(T)为总节点数，包括此节点(因此N(T) = 1 + LN(T) + RN(T))。从0 to N(T) - 1中选择一个随机数R。如果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()从方法中提升出来，但算法是相同的。

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

这篇关于从二叉树中随机选择节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！