c - C中的插入二叉搜索树

Question

我一直卡在二叉搜索树的插入部分。我对嵌套结构感到很困惑。该程序的基本思想是创建一个 bst，它能够保存按值存储的名称和 double 值(显然)。

例子:我要存储

简3.14

约翰 3.233

路加福音 6.4

迈克 1.4

所以 bst 看起来像

                 3.14
                 /   \
              1.4    3.233
                       \
                        6.4

但是我在处理代码的 insertHelper 递归部分时遇到了问题。哈希表是我稍后将尝试实现的代码的额外部分。感谢您的帮助!

typedef struct name_val // holds name and value
{
    char *name;
    double value;
}NAME_VAL;

typedef struct node //binary search tree
{
    NAME_VAL *nV;
    struct node *left;
    struct node *right;
}NODE;

struct tmap_struct  //handle for bst and hashtable
{
    int nL; //nodes on left
    int nR; //nodes on right
    NODE *root;
    NODE **table;
};


int tmap_insert(TMAP_PTR hashTree, char * name, double val)
{
    if(hashTree->root == NULL)
    {
        NODE *bst = (NODE *)malloc(sizeof(NODE));
        NAME_VAL *root = (NAME_VAL *)malloc(sizeof(NAME_VAL));
        bst->nV = root;
        bst->nV->value = val;
        strcpy(bst->nV->name, name);
        hashTree->root = bst;
        hashTree->nL = 0;
        hashTree->nR = 0;
    }

    else 
        insertHelper(hashTree->root, val, name);

}

void insertHelper(TMAP_PTR hashTree, int val, char * name)
{
    if(val < hashTree->root->nV->value)
    {
        if(hashTree->root->left == NULL)
        {
            hashTree->root->left = (NODE *)malloc(sizeof(NODE));
            hashTree->root->left->nV = (NAME_VAL *) malloc(sizeof(NAME_VAL));
            strcpy(hashTree->root->left->nV->name, name);
            hashTree->root->nV->value = val;
            (hashTree->nL)++;
        }

        else
            insertHelper(hashTree->root->left, val, name);
    }

    else
    {
        if(hashTree->root->right == NULL)
        {
            hashTree->root->right = (NODE *)malloc(sizeof(NODE));
            hashTree->root->right->nV = (NAME_VAL *)malloc(sizeof(NAME_VAL));
            strcpy(hashTree->root->left->nV->name,name);
            hashTree->root->nV->value = val;
            (hashTree->nR)++;
        }

        else
            insertHelper(hashTree->root->right, val, name);
    }
}

Answer 1

我怀疑这个编译。这是您遇到的问题吗？

据我所知，您为 insertHelper 的第一个参数声明了错误的类型。它应该采用 NODE* 值，而不是 TMAP_PTR 值。那是因为您总是使用树外的节点来调用它。

所以函数的第一部分应该是这样的:

void insertHelper(NODE *node, int val, char * name)
{
    if(val < node->nV->value)
    {
        if(node->left == NULL)
        {
            node->left = (NODE *)malloc(sizeof(NODE));
            node->left->nV = (NAME_VAL *) malloc(sizeof(NAME_VAL));
            strcpy(node->left->nV->name, name);
            node->left->nV->value = val;
        }

        else
            insertHelper(node->left, val, name);
    }

    //.....

请注意，我删除了这一行:

(hashTree->nR)++;

跟踪这些信息几乎没有意义，除非您可能在节点级别进行。

但如果必须的话，您可以让 insertHelper 递归地返回一个正值或负值以指示它插入的是哪一侧。但这没有意义。右边是什么？您可能已将其插入到树左半部分的节点右侧。

如果您将此信息存储在每个节点上，您可以在从 insertHelper 返回时递归更新上面的节点。也许这就是你想要做的。平衡树实现做类似的事情 - AVL 树在节点存储树的最大深度，并使用它来进行分支旋转以进行重新平衡。