從樹中獲取隨機節點

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; 
}