C/C++实现BST时结构体分配后未赋值的故障排查

本质是C/C++的函数参数值传递规则导致的。指针作为参数传递给函数时，传的是指针本身的副本，函数内部修改这个副本的指向，不会影响函数外部原指针的指向。
你调用pushBSTNode时传入tree->root，此时函数形参node只是一个和tree->root值相同的临时指针变量，你在node == NULL时给node赋值新创建的节点地址，只是修改了这个临时变量的值，完全不会改变tree->root本身的指向，所以退回到上层函数后tree->root还是NULL，自然插入无效。

可以选择以下任意一种方案修复，都符合你C风格为主、仅用少量C++特性的要求：

方案1：使用二重指针（纯C兼容） #

通过传递指针的地址，让函数可以直接修改外部原指针的指向：

1. 修改bstree.hpp中pushBSTNode的声明：

bool pushBSTNode(BSTNode** node, BSTNode* parent, BSTData* data);

2. 修改bstree.cpp中pushBSTNode的实现：

bool pushBSTNode(BSTNode** node, BSTNode* parent, BSTData* data) {
    if (*node == NULL) {
        *node = createBSTNode(data, parent);
        if (*node == NULL) return false;
        return true;
    } else {
        ssize_t delta = compareBSTData(data, (*node)->data);
        if (delta < 0) {
            return pushBSTNode(&((*node)->left), *node, data);
        } else if (delta == 0) {
            return false;
        } else if (delta > 0) {
            return pushBSTNode(&((*node)->right), *node, data);
        }
    }
    return false;
}

3. 修改pushBST中对pushBSTNode的调用，传入root指针的地址：

bool pushBST(BST* tree, const char* val_cstr, int val_int) {
    if (tree == NULL) return false;

    BSTData* data = createBSTData(val_cstr, val_int);
    if (data == NULL) return false;
    // 根节点的父节点为NULL，修正原来传tree->root的错误
    bool retval = pushBSTNode(&(tree->root), NULL, data);
    return retval;
}

方案2：使用C++指针引用（更简洁，符合你的编译要求） #

如果不想用二重指针，可以用C++的引用特性修饰形参，函数内部修改形参会直接同步到外部原指针：

1. 修改bstree.hpp中pushBSTNode的声明：

bool pushBSTNode(BSTNode*& node, BSTNode* parent, BSTData* data);

2. 修改bstree.cpp中pushBSTNode的实现：

bool pushBSTNode(BSTNode*& node, BSTNode* parent, BSTData* data) {
    if (node == NULL) {
        node = createBSTNode(data, parent);
        return node != NULL;
    }
    ssize_t delta = compareBSTData(data, node->data);
    if (delta < 0) {
        return pushBSTNode(node->left, node, data);
    } else if (delta == 0) {
        return false;
    } else if (delta > 0) {
        return pushBSTNode(node->right, node, data);
    }
    return false;
}

3. pushBST的调用不需要修改，直接传tree->root即可。

• bstree.hpp中BSTData结构体的val_int成员后面漏了分号，会导致编译报错
• 你当前代码没有实现compareBSTData函数，需要补充，示例实现如下：

// 放在bstree.cpp中，头文件要同步加声明
ssize_t compareBSTData(BSTData* a, BSTData* b) {
    return a->val_int - b->val_int;
}

• 原来pushBSTNode里的判断else if (delta > 1)是笔误，应该改为delta > 0，否则两个节点值差1的时候不会走右分支插入

内容的提问来源于stack exchange，提问作者404 Name Not Found