二叉搜索树键/值对 - 我知道的价值，但不是关键C++

我有一个简单的问题，我很困惑。我知道在二叉搜索树中有一个键/值对的概念，以及它在构建时的外观。二叉搜索树键/值对 - 我知道的价值，但不是关键C++

我不确定如何在这样的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); 
}

任何帮助，将不胜感激。

来源

2013-03-16 Faizan

你应该说明你正在编程什么语言（计算机语言），还有语言作为你的问题的标签。 – Annabel 2013-03-16 20:28:44

对不起。我已经完成了编辑。 – Faizan 2013-03-16 20:32:15

如果您正在搜索* values *，则可以在您的实现/概念中交换* key *和* value *，或者根本不需要存储密钥并仅使用该值。 – Cat 2016-06-06 08:29:35

如果您想通过值而不是密钥进行搜索，则无法利用树为二进制的事实搜索树。所以你没有别的选择，只能用BFS遍历整个树。

来源

2013-03-16 20:40:04

感谢您的回复。那就是我的想法，但不确定。我仍然不知道该怎么做。这显然不是不必使用密钥的事实真正有用的东西。这意味着如果我们得到这样一棵树，并且被要求搜索一个值而不是一个密钥，那么除了标准搜索方法，我们没有其他办法，并且二叉搜索树的概念会消失？坏。 – Faizan 2013-03-17 00:41:17

二进制搜索树（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); 
    }

在PARAMS是节点：要搜索的值：树& 关键的根。

因此，我们通常可以根据所需的密钥进行搜索，但不能根据与密钥关联的值进行搜索。

来源

2013-03-16 20:39:57 Srikanth

感谢Srikanth的回应，但正如我在问题中所说的那样，我没有跟踪关键是什么。我只想计算BST中某个特定值出现的次数，而不必知道任何密钥。 – Faizan 2013-03-16 21:08:43

二叉搜索树键/值对 - 我知道的价值，但不是关键C++

回答

相关问题