时间戳

首页 > 解决方案 > C++ 如何生成 10,000 个唯一随机整数以存储在 BST 中？

c++ - C++ 如何生成 10,000 个唯一随机整数以存储在 BST 中？

问题描述

我正在尝试生成 10,000 个 1 到 20,000 范围内的唯一随机整数以存储在 BST 中，但不确定执行此操作的最佳方法。

我看到了一些关于如何使用数组或向量的好建议，但不适用于 BST。我有一个contains方法，但我不相信它会在这种情况下工作，因为它用于搜索并返回关于找到所需数字需要多少次尝试的结果。下面是我得到的最接近的，但它不喜欢我的==操作员。使用数组并将数组存储在 BST 中会更好吗？或者有没有更好的方法来使用下面的代码，以便在生成数字时将它们直接存储在树中？

for (int i = 0; i < 10000; i++) 
{
    int random = rand() % 20000;
    tree1Ptr->add(random);
    for (int j = 0; j < i; j++) {
        if (tree1Ptr[j]==random) i--;
        }
    }

标签： c++randombinary-search-treeuniquerandom-seed

解决方案

您的代码中有几个问题。但是，让我们直接进入痛点。

主要问题是什么？

从您的代码中，很明显这tree1Ptr是一个指针。原则上应该指向树的一个节点，它有两个指针，一个指向左节点，一个指向右节点。

所以在你的代码的某个地方，你应该有： 

tree1Ptr = new Node;   // or whatever the type of your node is called

但是，在您的内部循环中，您只是像使用数组一样使用它：

for (int i = 0; i < 10000; i++) 
{
    int random = rand() % 20000;
    tree1Ptr->add(random);
    for (int j = 0; j < i; j++) {
        if (tree1Ptr[j]==random)  //<============ OUCH !!
            i--;
    }
}

编译器不会抱怨，因为它是有效的语法：您可以在指针上使用数组索引。但是你要确保你不会越界（所以在这里，j 保持 <1）。

其他备注

顺便说一下，在内部循环中，你只想说如果找到数字就必须重试。如果已经找到号码，您可以break内部循环，以免继续。

您还应该播种随机数生成器，以避免始终以相同的顺序运行程序。

如何解决？

你真的需要加深对BST的理解。在节点中导航需要与当前节点中的值进行比较，并根据结果，使用左指针或右指针继续迭代，而不使用索引。但是在这里解释太长了。所以可能你应该找一个教程，比如这个

推荐阅读