C语言实现二叉搜索树(BST)添加首个节点后树无法更新问题

问题描述 #

我正在用C语言实现二叉搜索树，但添加第一个元素后，树无法正常更新——打印时仅首个元素可见，后续添加的元素似乎未写入原树。相关代码如下：

节点定义 #

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

typedef struct Node node_t;

有问题的add_element函数 #

void add_element(node_t **head, int element) {
    if (*head == NULL) {
        node_t *new_node = (node_t *) malloc(sizeof(node_t));
        if (new_node == NULL) {
            printf("Not enough memory\n");
            return;
        }
        new_node->value = element;
        new_node->left = NULL;
        new_node->right = NULL;
        *head = new_node;
    } else {
        node_t *dummy = *head;
        if (dummy->value >= element) {
            dummy = dummy->left;
            add_element(&dummy, element);
        } else {
            dummy = dummy->right;
            add_element(&dummy, element);
        }
    }
}

打印及主函数代码 #

void log_tree(node_t *head) {
    if (head == NULL) {
        return;
    }
    log_tree(head->left);
    printf("%d - ", head->value);
    log_tree(head->right);
}

void print_menu(node_t *head) {
    printf("This is a BST implementation.\n");
    
    log_tree(head);
    printf("\n");
    printf("1. Add element\n");
    printf("2. Remove element\n");
    printf("3. Search Element\n");
    printf("4. Exit\n");
}

int main() {
    node_t *head = NULL;
    int run = 1;
    int choice, val;
    while (run) {
        print_menu(head);
        printf("Enter your choice: ");
        scanf("%d", &choice);
        printf("\n");
        switch (choice) {
            case 1:
                printf("Enter new element: ");
                scanf("%d", &val);
                printf("\n");
                add_element(&head, val);
                break;
            case 2:
                printf("Enter element to be removed: ");
                scanf("%d", &val);
                printf("\n");
                remove_element(&head, val);
                break;
            case 3:
                printf("Enter the element you want to search: ");
                scanf("%d", &val);
                printf("\n");
                search_element(head, val);
                break;
            case 4:
                run = 0;
                break;
            default:
                break;
        }
    }
    return 0;
}

错误分析 #

问题出在add_element函数的else分支：

• 局部指针dummy = *head是原节点指针的副本，后续将dummy指向dummy->left或dummy->right，再把&dummy传入递归调用时，修改的只是这个局部指针的指向，不会影响原树中父节点的left或right成员——相当于修改了一个副本的地址，原节点的指针根本没被更新。

修复后的add_element函数 #

直接传递父节点left或right成员的地址，让递归调用能直接修改原节点的指针：

void add_element(node_t **head, int element) {
    if (*head == NULL) {
        node_t *new_node = (node_t *) malloc(sizeof(node_t));
        if (new_node == NULL) {
            printf("Not enough memory\n");
            return;
        }
        new_node->value = element;
        new_node->left = NULL;
        new_node->right = NULL;
        *head = new_node;
    } else {
        node_t *dummy = *head;
        if (dummy->value >= element) {
            // 直接传递left指针的地址，递归修改原节点的left成员
            add_element(&(dummy->left), element);
        } else {
            // 直接传递right指针的地址，递归修改原节点的right成员
            add_element(&(dummy->right), element);
        }
    }
}

补充说明 #

• 在C语言中，若要修改一个指针变量本身的指向（比如让它指向新分配的内存），必须传递该指针的地址（即双指针）。
• 修复后的代码通过&(dummy->left)直接传入父节点left成员的内存地址，递归时修改*head就是修改原节点的left或right成员，从而正确更新树的结构。

内容的提问来源于stack exchange，提问作者Junky Man