c++ - 二进制搜索树键/值对 - 我知道值但不知道键 C++

Question

我有一个很困惑的简单问题。我知道在二叉搜索树中使用键/值对是什么概念，以及该树在构建时的样子。

如果我不知道它的键是什么，我不确定如何在这样的 BST 中搜索值？

例如:

假设我有一个充满整数(作为值)和唯一整数(作为键)的二叉搜索树。假设我想计算一个特定整数(比如说:200)在这个 BST 中出现的次数。所以据我所知，200 是“值”而不是“键”。因此我根本不知道 key 。

现在如何搜索整个 BST 中的所有“200”？它现在变成一个简单的 BST 而我根本不需要 key 吗？但是同样，树是使用“键”而不是值排列到左 child 和右 child 。

我还可以为您提供有关如何初始化 BST 的代码示例:

void insertNode(TreeNode *&p, int key, int value)
{
  if (p == NULL) {
    p = new TreeNode;
    p->key = key;
    p->value = value;
    p->left = NULL;
    p->right = NULL;
    return;
  }

  if (key < p->key)
    insertNode(p->left, key, value);
  else
    insertNode(p->right, key, value);
}

如有任何帮助，我们将不胜感激。

Answer 1

如果您想按值而不是键进行搜索，则不能利用树是二叉搜索 树这一事实。因此，您别无选择，只能使用例如 BFS 遍历整个树。