C二叉搜索树中具有多种数据类型的搜索功能

Question

我有一个以 id 作为键的 BST，如下所示：

struct node
{
    int id;
    char name[100];
    struct node *right;
    struct node *left;
};

这是搜索 id 的代码：

struct node* search(struct node *root, int x)
{
    if(root==NULL || root->id==x)
        return root;
    else if(x>root->id)
        return search(root->right, x);
    else
        return search(root->left,x);
}

但是如果我想搜索一个名字怎么办？可能吗？有什么建议吗？谢谢

Answer 1

由于二叉树是根据键int id排序的，所以需要遍历树的所有节点，使用字符串函数strcmp.

例如

#include <string.h>

//...

struct node* search(struct node *root, const char *name )
{
    if(root==NULL || strcmp( root->name, name ) == 0 )
    {
        return root;
    }
    else 
    {
        struct node *target = search(root->left, name);
        return target != NULL ? target : search(root->right, name);
    }
}

Answer 2

当然可以。您可以为此使用 strcmp 或您自己的任何其他函数。但是，BST 是在键 id 上创建的，因此您不会从 BST 提供的降低的搜索复杂性中受益。

Answer 3

我以前确实遇到过这个问题，我最终重写了自己的 BS 实现并进行了一些改进。所以我所做的是为每个单词生成一个特定的数字（令牌）（基本上像散列但带有数字），每当我想搜索一个单词时，它都会转换为数字令牌然后正常使用 BS 算法。

假设哈希算法是这样工作的

根据其字母顺序，每个字母都有一个 pre-defined 值 A->1 B->1...
单词中的字母顺序起着一定的作用，例如单词 yap 不能与 pay 相同，所以我们可以做的是取值 i = 1 所以每当我们标记一个字母我们将该标记添加到 i 所以下一个字母的标记我们将被提高到 i 或类似的东西
我们还必须计算标点符号

#include <math.h>
...
/* 
---------------------- NOTE ----------------------
 YOU PROBABLY WILL NEED TO IMPLEMENT A HASHMAP
 TO STORE THE ALPHABET LETTERS PRE-DEFINED VALUE,
 I'LL ASSUME THAT IT ALREADY EXISTS AND I WILL
 USE THIS METHOD TO GRAB THE VALUE
 get_value(hashmap,value);
 I'LL ALSO ASSUME THAT EVERY VALUE THE METHOD
 ABOVE RETURN EXISTS IN THE HASHMAP
-------------------------------------------------
*/
struct AlphabetOrderHashMap* hashmap = new_alphabet_order_hashmap();
int hash(char* word){
  int token = 0;
  int prev_letter_token = 1; // to address the letter order in the word
  for(int i =0;i < strlen(word);i++){
    prev_letter_token = hashletter(word[i],prev_letter_token);
    token +=  prev_letter_token
  }
  return token;

}
int hashletter(char letter,int i){
  int token = 0;
  token += (int)(pow(get_value(hashmap,letter),i) / (int)letter)
  return token;
}
...

然后我相信你可以从这里解决。所以与其将单词作为 char[] 放入树中，不如使用 token 会更好。

您也可以用令牌替换 ID，这样您只需搜索一次

C二叉搜索树中具有多种数据类型的搜索功能

Search function with multiple data type in C binary search tree

c

recursion

search

binary-search-tree

function-definition

假设哈希算法是这样工作的