1

我已经建立了一个 BST，它包含一个名称作为主要数据，以及与该名称相关的权重（当插入信息时，它以 Tom - 150 的形式输入，但由 Tom 在树中排序）。我需要能够确定谁的体重最低，但我不知道该怎么做。下面是类和 add 方法的代码，我还有很多其他的，但不觉得有必要发布它们，因为它们看起来不相关（如果需要我可以）。 

    #include <iostream>

using namespace std;

class tNode
{
public:
string name;
int wt;
tNode *left, *right;

tNode()
{
    left = right = 0;
}

tNode(string name, int wt, tNode *l = 0, tNode *r = 0)
{
    this->name = name;
    this->wt = wt;
    left = l;
    right = r;
}
};

class bSTree
{
public:
tNode *root;

bSTree()
{
    root = 0;
}

bool add(string name, int wt)
{
    tNode *temp = root, *prev = 0;
    while (temp != 0)
    {
        prev = temp;
        if (name < temp->name)
        {
            temp = temp->left;
        }
        else
        {
            temp = temp->right;
        }
    }

    if (root == 0)
    {
        root = new tNode(name, wt);
    }
    else if (name < prev->name)
    {
        prev->left = new tNode(name, wt);
    }
    else if (name > prev->name)
    {
        prev->right = new tNode(name, wt);
    }
    else
    {
        return false;
    }
    return true;
}

无论如何，这样做的技术是什么？我通过尽可能地从树的左侧向下找到最低的名称值（按字母顺序），但我不能 100% 确定找到最低权重的技术，因为树不是按权重排序的。我没有经验，因为我想使用 c++，我唯一能想到的就是遍历每个权重，将数据输入到 int，然后对 int 进行排序以找到最低的。我无法想象这是正确的方法，或者至少是最有效的方法。任何帮助总是受到赞赏。谢谢！

编辑：这是我到目前为止想出的：

void searchWeight(tNode* temp)
{
    // DETERMINE LOWEST WEIGHT CONTAINED IN TREE

    if (temp != 0)
    {
    cout << temp->wt << endl;
    searchWeight(temp->left);
    searchWeight(temp->right);
    }
}

这会将所有权重输出到控制台，但我不确定如何遍历每个权重并确定最低的。我试过在哪里放另一个 if 语句

 if(currwt < minwt)
    minwt = currwt

但最终不能正确输出。

4

2 回答 2

2

您不必对树进行排序以获得具有最小权重的节点。只需遍历树并存储最低重量和最低重量的人。如果当前节点的权重小于最小权重，则更新这两个变量。在遍历结束时，您将拥有最低的权重。

伪代码看起来像，

minWeight = 0
minWeightPerson = ""

for each node in the tree:
    if ( minWeight > weight of current node):
        minWeight = weight of current node
        minWeightPerson = person in current node

return minWeightPerson
于 2013-11-08T04:37:19.077 回答
1

您将需要遍历整个 BST，因为您不是按树的主键搜索。您可以使用任何树遍历算法。

如果您需要按权重搜索很多次（并且仅仅搜索整个树还不够快），那么构建一个“索引”是值得的，即第二个 BST 指向第一个 BST，但按辅助键排序。

遍历树一次将是O(n)，但遍历树 m 次将是O(m*n)。将构建第二棵不同索引的二叉搜索树O(n*log(n))，然后搜索第二棵树的m次数将是O(m*log(n))，整个操作就是这样O(n*log(n)+m*log(n)) = O((n+m)*log(n))。

于 2013-11-08T04:38:39.007 回答