java - 从树中获取随机节点

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

编辑:使用广度优先搜索

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 );，此时您的 temp 变量包含错误的答案。

编辑:我决定尝试快速修复您的 BFS 实现(快速 = 未经测试)。请注意，我试图使我的代码尽可能接近您的代码，因此我避免对您的算法进行任何更改。

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

编辑2:决定也修复您的其他版本(仍在尝试非常接近您的原始设计)。

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