在我的二叉搜索树中搜索问题

Question

问题出在功能 bin_search 上。它在函数 insert 上稳定运行。但是，它在函数 search 上被冻结。我认为如果在 insert 上没问题，在 search 上应该没问题，但事实并非如此。这是我的代码...

"bst.h":

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    int key;
    void *data;
    struct Node *left, *right;
    void (*destroy)(void *data);
} node;

typedef struct Tree {
    node *head;
    char name;
} tree;

#define key(node) node->key
#define data(node) node->data
#define left(node) node->left
#define right(node) node->right
#define destroy(node) node->destroy
#define tree_head(tree) tree->head

"functions.c":

#include "bst.h"

int bin_search(node *curr, int key, int cnt, node **found) {
    cnt++; printf("cnt+\n");
    
    if (curr == NULL) {
        return -1;
    } else if (curr->key == key) {
        printf("curr_key = key\n"); return cnt;
    }

    if (curr->key < key) {
        printf("curr_key < key\n");
        if (curr->right == NULL) {
            *found = curr;

            return -(cnt + 1);
        }

        return bin_search(curr->right, key, cnt, found);
    } else {
        printf("curr_key > key\n");
        if (curr->left == NULL) {
            *found = curr;
            
            return -(cnt + 1);
        }

        return bin_search(curr->left, key, cnt, found);
    }
}

int insert(tree *root, int key, void *data, void (*destroy)(void *data)) {
    if (root->head == NULL) {
        node* new_node = (node *)malloc(sizeof(node));
        left(new_node) = NULL; right(new_node) = NULL; destroy(new_node) = destroy; key(new_node) = key; data(new_node) = data;
        tree_head(root) = new_node;
        
        printf("created first node\n"); return 1;
    }

    int cnt; node **found;
    if ((cnt = bin_search(root->head, key, 0, found)) < 0) {
        node* new_node = (node *)malloc(sizeof(node));
        left(new_node) = NULL; right(new_node) = NULL; destroy(new_node) = destroy; key(new_node) = key; data(new_node) = data;

        if ((*found)->key < key) {
            (*found)->right = new_node;
        } else {
            (*found)->left = new_node;
        }

        printf("created a node at %d\n", -cnt); return 1;
    } else {
        printf("already exists in tree"); return -1;
    }
}

int search(tree *root, int key, void **data) {
    if (root->head == NULL) {
        printf("tree is empty\n"); return -1;
    }

    int cnt; node **found;
    if ((cnt = bin_search(root->head, key, 0, found)) < 0) {
        return -1;
    } else {
        if ((*found)->key < key) {
            *data = (*found)->right->data;
        } else {
            *data = (*found)->left->data;
        }
        
        return cnt;
    }
}

"main.c":

#include "bst.h"

#define MAX_NUM 8
#define MAX_LEGNTH 200

int main() {
    // create a tree
    tree root; root.head = NULL; root.name = 'a';

    FILE *inpt = fopen("list.txt", "r"); char buffer[MAX_LEGNTH];

    int count = 0;
    while (fgets(buffer, MAX_LEGNTH, inpt) != NULL) {
        printf("adding: %d\n", atoi(buffer)); insert(&root, atoi(buffer), buffer, NULL);
        count++;
    }
    fclose(inpt);

    int result; void **found;
    result = search(&root, 2, found); printf("%d\n", result);  // problem in here!!

    return 0;
}

我的 'search' 功能有什么问题。我找不到。

Answer 1

除了完全 non-standard 使用 sizeof(void) 之外，您没有提供正确的 out-parameter 进行搜索。 found 参数的要点是在发现前景密钥时接收节点指针。这...

int cnt; 
node **found; // <== LOOK HERE
if ((cnt = bin_search(root->head, key, 0, found)) < 0) {

不是这样做的方法。应该这样做：


int cnt; 
node *found = NULL;
if ((cnt = bin_search(root->head, key, 0, &found)) < 0) {
//                                        ^^^^^^

之后所有对 found 的引用都应该通过 found->，而不是 (*found)->

此错误出现在您代码中的三个不同位置。最后一个是semi-broken，但还是坏了。

void **found = (void *)malloc(sizeof(void));
int result = search(&root, 2, found); 
printf("%d\n", result);

应该用这个：

void *found = NULL;
int result = search(&root, 2, &found); 
printf("%d\n", result);

我不能说您的其余代码是否有问题，坦率地说，我们不是在做 online-debugger。 使用本地调试器工具；这就是他们的目的。但是上面列出的项目肯定是有问题的。

在我的二叉搜索树中搜索问题

Problem searching in my Binary Search Tree

c

binary-search-tree