Как организовать поиск в двоичном Б-дереве, если вершины не имеют целочисленных значений?

начинающий, непонимающий, не могу найти. Везде примеры поиска вершины по ключу с деревом имеющего числа в вершинах, т.е. при поиске мы сравниваем два числа. А если у меня вершины это указатели на структуру с данными где нет ни id ни чего того, что можно было бы сравнить. Есть структура, которую нельзя изменять(по заданию): book. Которую загоняю в дерево: tree. Теперь каждая вершина это одна запись из БД (вроде удобно). Пользователь вводит название улицы и дату заселения, и надо найти с помощью дерева поиска удовлетворяющие записи. А как, если у ключа нет индификатора, кроме "ленина", а в алгоритме мы сравниваем ключ с полем данных.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <io.h>
#include <Windows.h>

const int len_file = 4000;

struct adres_book
{
    char fio[32]; // Фио
    char street[20]; // Улица
    unsigned short int home; // Номер дома
    unsigned short int flat; // Квартиры
    char date[8]; // Дата заселения
} book;

struct tree {
    int id; // Использую для построения дерева
    struct adres_book date; // По сути поля данные
    int balance;
    tree * left;
    tree * right;
};

tree * node_new(int ind, adres_book date) {         
    tree * node = new tree;
    if (!node)
        return NULL;
    node->id = ind;
    node->date = date;              
    node->balance = 0;
    node->left = NULL;              
    node->right = NULL;
    return node;
}

tree * tree_insert(tree * p, int ind, adres_book date, boolean &Vr, boolean &Hr) {  Двоичное Б-дерево   
    tree * q;
    if (p == NULL) {
        p = node_new(ind, date);
        Vr = true;
        return p;
    }
    if (p->id > ind) {                                              
        p->left = tree_insert(p->left, ind, date, Vr, Hr);
        if (Vr) {
            if (p->balance == 0) {
                q = p->left;
                p->left = q->right;
                q->right = p;
                p = q;
                q->balance = 1;
                Vr = false;
                Hr = true;
            }
            else {
                p->balance = 0;
                Hr = true;
            }
        }
        else {
            Hr = false;
        }
    }
    else if (p->id < ind) {                                         
        p->right = tree_insert(p->right, ind, date, Vr, Hr);
        if (Vr) {
            p->balance = 1;
            Vr = false;
            Hr = true;
        }
        else if (Hr) {
            if (p->balance > 0) {
                q = p->right;
                p->right = q->left;
                p->balance = 0;
                q->balance = 0;
                q->left = p;
                p = q;
                Vr = true;
                Hr = false;
            }
            else {
                Hr = false;
            }
        }
    }
    return p;
}

int SearchKey(tree *p, int key) // В предыдущей лабе функция поиска 
{                               //несла просто логический характер
    while (p != NULL) {
        if (key < p->id)
            p = p->left; 
        else if (key > p->id)
            p = p->right; 
        else
            break;
    }
    if (p != NULL)
        return 1;
    return 0;
}

int main()
{
    FILE * fp = fopen("BASE4.DAT", "rb");
    tree * p = NULL;
    boolean Hr;                     
    boolean Vr;                     

    if (fp == NULL) {
        printf("Error File!\n");
        system("pause");
        exit(1);
    }
    int ind = 1;
    fread(&book, sizeof(book), 1, fp);
    while (ind <= 10) {
        Hr = true;
        Vr = true;
        p = tree_insert(p, ind, book, Vr, Hr);
        ind++;
        puts("");
    }
    char search_street[31] = " ";
    char search_date[8] = " ";
    printf("\nEnter key: ");//Тут я завис, вводим улицу и дату, надо найти всех кто 
    //scanf("%s", search_street);//живет на ней не ранее этой даты. Не понимаю как   
    //SearchKey(search_street);//организовать поиск в дереве по таким ключам
    printf("\n%d\n", ind);
    fclose(fp);
    system("pause");
}

файл БД