c - 下面的二叉搜索树插入方法有什么问题？

Question

///// 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 接受参数 key、data 和 bst(BStree 类型，是指向 BStree_node 的指针)。因此，为了使用递归插入新节点，我使用 (*bst) 调用 bst_insert_helper 方法，它是指向根节点的指针，对吧？

然后 bst_insert_helper 方法递归地找到插入节点的位置。显然这段代码有错误，但我不确定错误在哪里。

我在想也许我需要构建一个辅助方法，每次都接受一个新的子树而不是一个节点，但我不明白这与在链接时仅接受一个节点有什么不同。

Answer 1

您不需要构建一个助手。事实上，您需要失去一个。您的入口函数采用 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 程序员希望看到星号，它是指针操作的名片。