二叉搜索树插入函数不更新二叉搜索树

Question

我正在尝试获取一个文本文件，并将其转换为二进制搜索树。下面是我的函数，它接收文本文件并将其传递给bst_insert：

bst* get_counts(char *filename) {
    bst* new = create_bst();
    FILE *fp;
    char buffer[500];
    char* delim = " .,'/'\n;?><:";
    char* token;
    if (!(fp = fopen(filename, "r"))) {
        fprintf(stderr, "Could not open file.");
        exit(0);
    }

    while(fgets(buffer, 500, fp)) {
        token = strtok(buffer, delim);
        while (token) {
            wordcount* w = (wordcount*)malloc(sizeof(wordcount));
            w->count = 0;
            strcpy(w->word, token);
            bst_insert(new, (void*)w, compare_words);
            token = strtok(NULL, delim);
        }
    }

    fclose(fp);
    return new;;
}

下面是调用bst_insert的bst_insert：

void bst_insert(bst *tree, void *item, int (*compare)(void *, void *))
{
    if (tree)
        tree->root = bstnode_insert(tree->root, item, compare);
}



bstnode* bstnode_insert(bstnode *node, void *item,
                        int (*compare)(void *, void *))
{
    bstnode *new_node = (bstnode*)malloc(sizeof(bstnode));
    new_node->item = item;
    new_node->rsub = NULL;
    new_node->lsub = NULL;

    if (!node) {
        node = (bstnode*)malloc(sizeof(bstnode));
        node->item = item;
        node->rsub = NULL;
        node->lsub = NULL;
        return node;
    }
    wordcount *w1 = (wordcount*) item;
    wordcount *w2 = (wordcount*)node->item;
    int comp = compare(w1->word, w2->word);

    if (comp < 0) {
        if (node->lsub)
            node->lsub = bstnode_insert(node->lsub, item, compare);
        else {
            node->lsub = new_node;
        }
    }
    else if (comp > 0) {
        if (node->rsub)
            node->rsub = bstnode_insert(node->rsub, item, compare);
        else {
            node->rsub = new_node;
        }
    } else {
       bstnode_insert(node->rsub, item, compare);
    }
    return node;
}

由于某种原因，我的函数最终只创建了树的第一个节点，我不确定为什么。我想让它生成整个节点。

Answer 1

下面是一个(最小的)二叉树实现：

首先是创建树的函数：

Tree_t* create_dynamic_tree()
{
    Tree_t* my_tree = NULL;
    my_tree = (Tree_t*) malloc(sizeof(Tree_t));
    my_tree->number_of_nodes = 0;
    my_tree->root = NULL;
    my_tree->max_key = 0;
    return my_tree;
}

一棵树在哪里

typedef struct Tree_t
{
    int number_of_nodes;
    Node_t* root;
}Tree_t;

一个节点是：

struct Node_t
{
    void* data;
    int key;
    Node_t* left_child;
    Node_t* right_child;
};

现在你需要一个函数来添加数据，应该是这样的：

int data_add(Tree_t* tree_dest , void* data , int* data_key)
{
    if(tree_dest == NULL || data == NULL )
    {
        return -1;
    }
    int key = 0;
    Node_t* parent;
    key = *data_key;
    if(key<0)
    {
        return -2;
    }
    if(tree_dest->number_of_nodes == 0)
    {
        Node_t* temp = NULL;
        temp = (Node_t*) malloc(sizeof(Node_t));
        temp->data = data;
        temp->key = key;
        temp->left_child = NULL;
        temp->right_child = NULL;

        tree_dest->number_of_nodes++;
        tree_dest->root = temp;
        return key;
    }
    exists_t existance = not_exist;
    exists_t* exist_ptr = NULL;
    exist_ptr = &existance;

    if(is_key_exists(tree_dest , &parent ,key , exist_ptr) == 0)
    {
        if(existance == exist)
        {
            return -1;
        }
        else
        {
            if(insert_node(tree_dest , &parent ,data , key) == -1)
            {
                return -1;
            }
        }
    }
    if(tree_dest->max_key < key)
    {
        tree_dest->max_key = key;
    }
    //free(parent);
    return key;
}

上面的函数使用以下函数：

--is_key_exists()

int is_key_exists(Tree_t* the_tree ,  Node_t** parent , int key , exists_t* exist_t)
{
    if(the_tree == NULL )
    {
        return -1;
    }
    Node_t* root = the_tree->root;
    search_node_parent(the_tree , &root , parent , key);
    if(root != NULL)
    {
        *exist_t = exist;
        return 0;
    }
    else
    {
        *exist_t = not_exist;
        return 0;
    }
}

--insert_node()

int insert_node(Tree_t* tree_dest , Node_t** parent ,void* data , int key)
{
    if(tree_dest == NULL || data == NULL || parent == NULL )
    {
        return -1;
    }
    Node_t* new_node = NULL;
    new_node = (Node_t*) malloc(sizeof(Node_t));
    new_node->data = data;
    new_node->key = key;
    new_node->left_child = NULL;
    new_node->right_child = NULL;

    if(key < (*parent)->key )
    {
        (*parent)->left_child = new_node;
    }
    if(key > (*parent)->key)
    {
        (*parent)->right_child = new_node;
    }
    tree_dest->number_of_nodes++;
    if(tree_dest->max_key < key)
    {
        tree_dest->max_key = key;
    }
    return 0;
}

我在这里做的是获取void* data，一个指向所需内容的指针(您在这里使用的char*或结构/联合)，将数据封装在一个节点中，并使用id (在本例中可能是文件中的行数)将其添加到树中。我希望这篇文章能帮助你，或者将来任何需要一个(基本的)树实现的人。这就是你所需要的insertion.Next步骤，如果你想要一棵平衡的树，就需要重新散列。

谢谢。