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

Question

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

首先，将元组读入键和值并将它们传递给create函数，我在其中初始化了一个具有该结构的树

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中的'value'部分，因为我稍后将使用它处理重复项。

使用上面的代码，我希望树形成，但没有发生。经过进一步的调查和调试，我发现当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;
}

我试着尽可能详细，但如果你不明白，请随时问我问题。很高兴回答。请帮助。

Answer 1

更多已经在答案中描述的修正：

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

在CreateAVLTree中你（现在）将节点树设置为head但是你错过了更新tree->root，一个简单的方法是不使用临时var头但是直接使用tree->root：

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

    fclose(file);

    return tree;
}

当文件无法打开时，我还用return 1;替换了无效的return NULL;。

注意字段大小没有设置，也许它必须包含节点列表的大小，在这种情况下只需在tree->size += 1;调用附近添加insert_in_tree

如果我添加定义来打印结果：

void PrintNodes(struct AVLTreeNode * l)
{
  if (l == NULL)
    printf("()");
  else {
    putchar('(');
    PrintNodes(l->left);
    printf(" %d %d %d ", l->key, l->value, l->height);
    PrintNodes(l->right);
    putchar(')');
  }
}

void PrintAVLTree(AVLTree * tree)
{
  printf("%d elements : ", tree->size);
  PrintNodes(tree->root);
  putchar('\n');
}

并将PrintAVLTree(tree1);放在主要，编译和执行中的注释中：

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra -Wall t.c
pi@raspberrypi:/tmp $ cat File1.txt 
(2, 50) (4, 30) (9, 30) (10, 400) (-5, -40)
(7, 20) (19, 200) (20, 50) (-18, -200) (-2, 29)
(2, 67) (4, 35) (9, 45) (-18, 100)
pi@raspberrypi:/tmp $ ./a.out
14 elements : (((() -18 -200 0 ()) -5 -40 0 (() -2 29 0 ())) 2 50 0 (() 4 30 0 ((() 7 20 0 ()) 9 30 0 (() 10 400 0 (() 19 200 0 (() 20 50 0 ()))))))

Answer 2

米哈伊尔几乎在那里，但没有发现内存泄漏。我在下面更正：

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通过值传递。这被称为“双指针”。
• 你在每次递归调用时都分配了内存，但是一旦知道要插入的位置，你只需要这样做。

Answer 3

在函数insert_in_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);
    }
}

此外，如果node != NULL此函数导致内存泄漏，因为它分配新节点但不保存指向它的指针。

顺便说一下，你想要创造的不是AVL树，而是binary search tree。