Что не так со следующим методом вставки в двоичное дерево поиска? - PullRequest
Новая
       19

Что не так со следующим методом вставки в двоичное дерево поиска?

0 голосов
/ 23 ноября 2018 
///// bst.h /////

typedef struct BStree_node {
    Key key;
    Data data;
    struct BStree_node *left, *right;
}
BStree_node;

typedef BStree_node** BStree;


///// bst.c /////

BStree_node *new_node(Key key, Data data) {
    BStree_node *node;
    node = (BStree_node *) malloc(sizeof(BStree_node));
    node->key = key;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void bs_tree_insert(BStree bst, Key_Type key, Data_Type data) {
    bst_insert_helper(*bst, key, data);
}

void bst_insert_helper(BStree_node *node_ptr, Key_Type key, Data_Type data) {
    if ( node_ptr == NULL ) {
        node_ptr = new_node(key, data);
    }
    else {
        if ( key_comparison(key, node_ptr->key) < 0 )
            bst_insert_helper(node_ptr->left, key, data);
        else if ( key_comparison(key, node_ptr->key) > 0 )
            bst_insert_helper(node_ptr->right, key, data);
        else
        ;
    }
}

Я запутался, что не так с этим кодом.

Исходный метод bs_tree_insert принимает ключ параметров, данные и bst (типа BStree, который является указателем на узел BStree_node).Итак, чтобы использовать рекурсию для вставки нового узла, я вызвал метод bst_insert_helper с (* bst), который является указателем на корневой узел, верно?

Затем метод bst_insert_helper рекурсивно находит место для вставки узла.Видимо этот код имеет ошибку, но я не уверен, где.

Я думаю, может быть, мне нужно было бы создать вспомогательный метод, который бы каждый раз принимал новое поддерево вместо узла, но я не понимаю, как это будет отличаться от простого взятия узла таким, какой он есть.связаны между собой.

Ответы [ 2 ]

0 голосов
/ 23 ноября 2018

Вам не нужно создавать помощника.На самом деле вам нужно потерять один.Ваша функция ввода принимает BStree_node** (неудобно скрытый в псевдониме типа), и это именно то, что вам нужно вставить с изменением указателя вызывающего абонента, передаваемого по адресу, без изменений. 

void bs_tree_insert(BStree bst, Key_Type key, Data_Type data) 
{
    if (*bst == NULL)
    {
        *bst = create_new_node(key, data);
    }
    else
    {
        int cmp = key_comparison(key, (*bst)->key);
        if (cmp < 0)
            bst_tree_insert(&(*bst)->left, key, data);
        else if (0 < cmp)
            bst_tree_insert(&(*bst)->right, key, data);
        // else equivalent; no duplicates
    }
}

Тот факт, чтоесли вы скрываете типы указателей в псевдонимах, это сложнее , а не проще для понимания.Я настоятельно предлагаю избегать этого.Программисты на C хотят видеть звездочки, визитную карточку операций с указателями.

0 голосов
/ 23 ноября 2018

Вы также забыли добавить равные. Пожалуйста, добавьте, чтобы создать метод также

...