Узлы двоичного дерева с индексом - PullRequest
Новая
       6

Узлы двоичного дерева с индексом

0 голосов
/ 29 апреля 2018

Мне нужно сделать оптимизированный поиск вектора с использованием бинарного дерева поиска. например, у меня есть vector<int> номера, где я храню {5,4,3,2,1} затем я копирую эти 1,2,3,4,5 в двоичное дерево и должен вернуть индекс, где он хранится в векторе Например, search (4) должен будет возвращать 1, потому что числа [1] = 4 Я попытался дать индекс узлов, но они не совпадают в конце Есть ли лучшее решение или как правильно дать индекс для узлов дерева 

struct node {
    int data;
    int index;
    node* left;
    node* right;
};
    node* insert(int x, node* t) {
    if(t == NULL) {
        t = new node;
        t->data = x;
        t->index = 0;
        t->left = t->right = NULL;
    }
    else if(x < t->data) {
        t->left = insert(x, t->left);
        t->index += 1;
    }

    else if(x > t->data) {
        t->right = insert(x, t->right);
        t->index += 0;
    }
    return t;
}

node* find(node* t, int x)  {
    if(t == NULL)
        return NULL;
    else if(x < t->data) {
        return find(t->left, x);
    }
    else if(x > t->data) {
        return find(t->right, x);
    }

    else
        return t;
}

int main() {
    BST t;
    vector<int> storage;
    for ( int i =0; i< 10; i++) {
        storage.push_back(rand()%100 +1);
        t.insert(storage[i]);
    }
    t.display();
    t.search(15);
}

1 Ответ

0 голосов
/ 29 апреля 2018 
    node* insert(int x, node* t, int index)
{
    if(t == NULL)
    {
        t = new node;
        t->data = x;
        t->index = index;
        t->left = t->right = NULL;
    }
    else if(x < t->data)
    {
        t->left = insert(x, t->left, index);

    }

    else if(x > t->data)
    {
        t->right = insert(x, t->right, index);

    }

    return t;
}
...