I have a BST with id as a key as follows:

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

Here is the code to search an 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);
}

But what if I want to search for a name? Is it possible? Any suggestion? Thanks

CodePudding user response：

Ofcourse it is possible. You can use strcmp or any other function of your own for that. However the BST is created on the key id so you aren't going to benefit from the reduced search complexity which BST provides.

CodePudding user response：

As the binary tree is ordered based on the key int id then you need to traverse all nodes of the tree to find a node with the specified name using the string function strcmp.

For example

#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);
    }
}

CodePudding user response：

I actually had this issue before, I ended up rewriting my own implementation of BS alongside some improvements. so what I did was generating a specific number(token) for each word (basically like hashing but with numbers), and whenever I wanna search for a word, it gets transformed to numerical tokens then use the BS algorithm normally.

let's say the hashing algorithm works this way

• Every letter will have a pre-defined value according to its alphabetical order A->1 B->1...
• The letters order in the word plays a role for example the word yap cannot be the same as pay so what we can do is having a value i = 1 so whenever we tokenize one letter we add that token to i so next letter's token we'll be raised to the power of i or something similar
• We also have to put in count ponctuations

#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;
}
...

and then I believe you can work it out from here. so instead of putting the word in the tree as char[], using the token will be better.

you can also replace the id by the token so you'll only have to search once