时间戳

首页 > 解决方案 > 在树中插入（键，值）时，节点不形成树结构

c - 在树中插入（键，值）时，节点不形成树结构

问题描述

我正在尝试创建 avl 树，它从文件中一对一地读取（键，值）并根据键的数据形成树。

首先，将元组读入键和值并将它们传递给创建函数，在该函数中我使用结构初始化了一个树

typedef struct AVLTree{
    int  size;      // count of items in avl tree
    AVLTreeNode *root; // root
} AVLTree;

AVLTree *newAVLTree()
{
    AVLTree *T;
    T = malloc(sizeof (AVLTree));
    assert (T != NULL);
    T->size = 0;
    T->root = NULL;
    return T;
}

然后我最初将树的根的值为 NULL 的值分配给结构如下所示的 AVLTreeNode：

typedef struct AVLTreeNode {
    int key; //key of this item
    int  value;  //value (int) of this item
    int height; //height of the subtree rooted at this node
    struct AVLTreeNode *parent; //pointer to parent
    struct AVLTreeNode *left; //pointer to left child
    struct AVLTreeNode *right; //pointer to right child
} AVLTreeNode;

//data type for AVL trees
typedef struct AVLTree{
    int  size;      // count of items in avl tree
    AVLTreeNode *root; // root
} AVLTree;

// create a new AVLTreeNode
AVLTreeNode *newAVLTreeNode(int k, int v )
{
    AVLTreeNode *new;
    new = malloc(sizeof(AVLTreeNode));
    assert(new != NULL);
    new->key = k;
    new->value = v;
    new->height = 0; // height of this new node is set to 0
    new->left = NULL; // this node has no child
    new->right = NULL;
    new->parent = NULL; // no parent
    return new;
}

现在，对于我从文件中读取的每个键值对，我将其传递给 create 函数并检查以下 3 个条件：

void insert_in_tree(int key, int value, struct AVLTreeNode **node){


    // if the tree is empty
    if(*node == NULL){
        node = newNode;
    }
    // insert on left if the data in the key is less than the data in the node.
    else if (key<(*node)->key){
        insert_in_tree(key,value,&(*node)->left);
    }
    // insert on right if the data in the key is greater than the data in the node.
    else if(key>(*node)->key)
    {
        insert_in_tree(key,value,&(*node)->right);
    }

}

PS：不要担心 newAVLTreeNode 中的“值”部分，因为稍后我将使用它来处理重复项。

使用上面的代码，我希望树会形成，但这并没有发生。经过进一步调查和调试，我发现虽然 insert_in_tree 使用新的键和值传递，但节点也是新的，而不是已经创建的节点。

AVLTree *CreateAVLTree(const char *filename)
{
    //Inititalising a new tree
    AVLTree *tree = newAVLTree();
// initialising the head to root of tree i.e. null
    AVLTreeNode *head = tree->root;
    int key, value;
    FILE* file = fopen(filename, "r"); // open a file
    if(file == NULL) {
        return 1;                                   // error checking
    }
    while (fscanf (file, " (%d,%d)", &key, &value) == 2)  // check for number of conversions
    //  space added  here ^
    {
        insert_in_tree(key, value, &head);
        //printf("%d,%d\n", key, value);
    }
    fclose(file);

    return tree;
}

int main() //sample main for testing
{
    AVLTree *tree1;
    tree1=CreateAVLTree("File1.txt");
    //PrintAVLTree(tree1);
    return 0;
}

我试图尽可能详细，但如果您不明白，请随时问我问题。很高兴回答。请帮忙。 节点已形成，但树仍为 NULL

标签： cavl-tree

解决方案

米哈伊尔快到了，但没有发现内存泄漏。我在下面更正：

void insert_in_tree(int key, int value, struct AVLTreeNode **node){
    // if the tree is empty
    if(*node == NULL){
        *node = newAVLTreeNode(key, value);
    }
    // insert on left if the data in the key is less than the data in the node.
    else if (key<(*node)->key){
        insert_in_tree(key,value,&(*node)->left);
    }
    // insert on right if the data in the key is greater than the data in the node.
    else if(key>(*node)->key)
    {
        insert_in_tree(key,value,&(*node)->right);
    }
}

作为修复的摘要：

  • 您需要将指针传递给放置新分配节点的位置，因为 C 通过值传递。这就是所谓的“双指针”。

  • 您在每次递归调用时都分配了内存，但只有在知道插入位置时才需要这样做。

推荐阅读