从树中获取随机节点

Question

我的方法是假设从BST返回一个随机节点，但它不能正常工作，我不确定原因。该方法假设在递增计数器的同时使用前序遍历来遍历树。一旦计数器等于随机生成的数字，则假定返回该节点。

// get random node 
public Node getRandomNode(Node root) { 

    // get random value between 0 to size of BST 
    Random ran = new Random(); 
    int ranNum = ran.nextInt(size + 1); 
    Node temp = root; 
    System.out.println("random number is: " + ranNum); 

    root = getRandomNode(ranNum, temp); 
    return root; 
} 

int count = 0; 

public Node getRandomNode(int ranNum, Node temp) { 

    // traverse through the tree and increment count until count is the 
    // random number, 
    // in which case return the node it is on 
    if (temp != null && count != ranNum) { 
     count++; 
     temp = getRandomNode(ranNum, temp.left); 
     System.out.println(temp.data); 
     temp = getRandomNode(ranNum, temp.right); 

    } 
    // if count is equal to the randomly generated number 
    return temp; 
} 

编辑： 使用BFS

public Node getRandomNode(int ranNum, int count, Node temp) { 

    if(temp == null) 
     return null; 

    Queue<Node> q = new LinkedList<Node>(); 
    q.add(temp); 
    count++;  

    while(!q.isEmpty() && count != ranNum) { 

     Node n = q.remove(); 
     System.out.println(" " + n.data); 

     if(count == ranNum) { 
      System.out.println("final node: " + n.data); 
      return n; 
     } 

     if(n.left != null) { 
      q.add(n.left); 
      count++; 
     } 
     if(n.right != null) { 
      q.add(n.right); 
      count++; 
     } 
    } 

    return temp; 
} 

Answer 1

你的问题是在你的递归调用。假设随机数为1，那么您会期望返回的结果是从左侧子树到达的第一个节点。您的代码将显示temp = getRandomNode(ranNum, temp.left);，并且此时temp变量保留正确的答案，则您说temp = getRandomNode(ranNum, temp.right);，此时，您的临时变量将保留不正确的答案。

编辑： 我决定试着快速修复你的BFS实现（quick =未经测试）。请注意，我试图尽可能让自己的代码尽可能接近您的代码，所以我避免对您的算法进行任何更改。

public Node getRandomNode(Node temp, int ranNum) { 

    if(temp == null) 
     return null; 

    Queue<Node> q = new LinkedList<Node>(); 
    q.add(temp); 
    int count = 0; 

    while(!q.isEmpty() && count <= ranNum) { 

     Node current = q.remove(); 
     System.out.println(" " + result.data); 

     if(count == ranNum) { 
      System.out.println("final node: " + n.data); 
      return n; 
     } 

     if(n.left != null) { 
      q.add(n.left); 
     } 
     if(n.right != null) { 
      q.add(n.right); 
     } 
     count++ 
    } 

    return null; 
} 

EDIT2： 决定修复你的其他版本，以及（仍然试图坚持非常接近原来的设计）。

// get random node 
public Node getRandomNode(Node root) { 

    // get random value between 0 to size of BST 
    Random ran = new Random(); 
    int ranNum = ran.nextInt(size + 1); 
    System.out.println("random number is: " + ranNum); 

    return getRandomNode(ranNum, root); 
} 

int count = 0; 

public Node getRandomNode(int ranNum, Node node) { 

    // traverse through the tree and increment count until count is the 
    // random number, 
    // in which case return the node it is on 
    if (node == null || count == ranNum) { 
     return node; 
    } 
    count++; 
    temp = getRandomNode(ranNum, temp.left); 
    if (temp != null) { 
     return temp; 
    } 
    return getRandomNode(ranNum, temp.right); 
} 

Answer 2

您的实现不是完全随机的，因为您正在基于计数（随机选取）检索随机节点，但未随机遍历！ 当且仅当树为空时，树应该返回null。 ，因为您已经根据树的大小生成了随机数。

这棵树有两条路径，无论是右边还是左边......任何一条路都应该是随机的！ 而且应该通过其中一个方法调用（除非该分支已用完）。 我改变了从字段到计数变量的方法参数'因为它似乎是一个温度，并且与类 没有任何关系，因此您不必重置每次使用该类的计数，这是一个好习惯。 *另一个值得关注的问题是，如果一边的边数小于另一边的数值，那么该函数将退出，因为节点是 如果这在左边发生，则它将返回null温度，但如果它发生在另一方面，它可能会返回null！ 的方式认为这是伪代码，我从来没有测试:)

public Node getRandomNode(Node root) { 
Random ran = new Random(); 
int ranNum = ran.nextInt(size + 1); 
Node temp = root; 
System.out.println("random number is: " + ranNum); 

root = getRandomNode(ranNum, temp,0); 
return root; 
} 



public Node getRandomNode(int ranNum, Node temp, int count) { 

    // traverse through the tree and increment count until count is the 
    // random number, 
    // in which case return the node it is on 
    if (temp != null && count != ranNum) { 
     count++; 
     Random pathRan = new Random(); 
     int pathNo= pathRan.nextInt(2); 
     Node temp2 = null; 
     if(pathNo == 0){//if 0 go to left 
     temp2 = getRandomNode(ranNum, temp.left,count); 
     if(temp2 == null){//this means that this path has nodes less than count ,so try the right. 
      temp2 = getRandomNode(ranNum, temp.right,count); 
     } 


     }else{//go to right 
     temp2 = getRandomNode(ranNum, temp.right,count); 
     if(temp2 == null){//this means that this path has nodes less than count ,so try the left. 
      temp2 = getRandomNode(ranNum, temp.left,count); 
     } 
     } 
     return temp2; 
    } 
    // if count is equal to the randomly generated number 
    return temp; 
}