用C语言插入二叉树

Question

我一直被困在二叉树的插入部分。我对嵌套结构感到非常困惑。这个程序的基本思想是创建一个bst，它能够保存按值存储的名称和双精度值(显然)。

示例:我想存储

简3.14

约翰3.233

卢克6.4

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

Answer 2

您必须调整我的算法(除了不需要的模板和类之外，它几乎是标准的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(){}
}