6

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

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

例如：

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

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

我还可以为您提供如何初始化 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);
}

任何帮助，将不胜感激。

4

2 回答 2

7

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

于 2013-03-16T20:40:04.087 回答
1

二叉搜索树（BST）对于存储数据以进行快速访问、存储和删除非常有用。二叉搜索树中的数据存储在树节点中，并且必须与它们关联一个序数值或键；这些键用于构造树，使得左子节点的值小于父节点的值，右子节点的值大于父节点的值。有时，键和数据是一回事。

典型的键值包括简单的整数或字符串，键的实际数据将取决于应用程序。让我们考虑一个存储字符串/双精度对的二叉搜索树。也就是说，键是字符串值，与键关联的数据是双精度值。开发人员可以使用字符串值搜索树。

在这种情况下，一个基本的递归搜索算法将如下所示：

 node search (node, key) {
   if node is null then return null;

   if node.key = key then
      return node

   if key < node then
      return search (node.left, key);
   else
      return search (node.right, key);
  }

其中参数是node : 树的根 & key : 要搜索的值。

所以通常我们可以根据需要的键而不是键的关联值进行搜索。

于 2013-03-16T20:39:57.313 回答