1

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

示例：我想存储

简 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);
    }
}
4

2 回答 2

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 树将树的最大深度存储在节点上，并使用它来进行分支旋转以进行重新平衡。

于 2013-04-30T03:03:40.363 回答
1

你必须适应我的（除了不需要的模板和类之外，它几乎是标准的 C），但它是一个类似的算法：（我相信，我没有出于自己的目的查看任何来源。）

template<typename T>
class BST {
    protected:
        typedef struct node_t {
            struct node_t * dir[2];
            T data; 
        } node;

        node * root;

        void insert_node(node * active_node, T data){ //call with node *root;
            int next = data < active_node->data ? 0 : 1;
            if(active_node->dir[next] == NULL){
                active_node->dir[next] = new node;
                active_node->dir[next]->dir[0] = NULL;
                active_node->dir[next]->dir[1] = NULL;
                active_node->data = data;
            } else
                insert_node(active_node->dir[next], data);
        }

    public:
        BST() : root(new node){root->dir[0] = NULL; root->dir[1] = NULL; root->data = 0;}
       ~BST(){}
}
于 2013-04-30T04:00:56.013 回答