插入新节点时的AVL TREE Malloc Function

Question

我最近在 C 中成功创建了一个 bst..然后我的尝试是创建一个 AVL ..这样做的第一步是添加一个额外的每个节点中的组件 bf（平衡因子）..我按如下方式进行。

    struct tnode{
        int info;
        struct tnode*left;
        struct tnode*right;
        int bf;//new field for avl tree..
                };

每次 malloc 在插入时为新节点分配一个地址...我将其信息部分分配给用户输入的值..将左右指针设置为 NULL.In 除此之外，它还分配了 bf 新节点的0..插入第一个节点（即根节点）后程序在下一次的malloc部分失败甚至为 newnode 分配一个内存...只要我删除 newnode->bf=0 的部分..问题就消失了.. 为什么会这样？下面是我的主要函数和 add() 函数，它将整数作为输入并将其插入到根节点为 'root' 全局声明的树中。

    int main(){
    int choice,val;
    deci:
    printf("\n1.Insert");
    printf("\n2.Display");
    printf("\n3.Search.");
    printf("\n4.Delete");
    printf("\n5.Naa..");
    scanf("%d",&choice);
    switch(choice){
            case 1:printf("\nEnter element to add:");
                    scanf("%d",&val);
                    add(val);

                    //display();
                    break;
            case 2:display();
                    break;
            case 3:printf("\nEnter element to search for:");
                    scanf("%d",&val);
                    search(val);
                    break;

            case 4:printf("\nEnter element to Delete: ");
                    scanf("%d",&val);
                    deletei(val);
                    display();
                    break;
            case 5:return 0;

            }
    goto deci;
    return 0;
    }


    void add(int val){
    struct tnode * newnode=(struct tnode * )malloc(sizeof(struct tnode *));
    newnode->info=val;
    newnode->left=newnode->right=NULL;
    newnode->bf=0;//problem making,problem solved removing this statement
    if(root==NULL){
            root=newnode;

                    }                       
    else{
        struct tnode*tree=root;
        struct tnode*ptree=NULL;
    while(tree!=NULL){
                    if(val<tree->info){
                                        ptree=tree;
                                        tree=tree->left;

                    }
                    else{
                        ptree=tree;
                        tree=tree->right;
                    }                       


        }   
    if(val<ptree->info){

                ptree->left=newnode;
                tree=ptree->left;


        }
else{
ptree->right=newnode;   
tree=ptree->right;

    }
    }


    }

Answer 1

您的第一个主要错误是您只为 add() 中的 newnode 地址分配了 space。您应该将其转换为：

struct tnode * newnode=(struct tnode * )malloc(sizeof(struct tnode));

在这种情况下，您为所需节点分配了整个 space。

PS。也请退出 'goto' 指令，因为使用它是一种不好的做法。

Answer 2

您的问题出在这一行：

struct tnode * newnode = (struct tnode *) malloc(sizeof(struct tnode *))

来自 C reference for malloc

Allocates size bytes of uninitialized storage

If allocation succeeds, returns a pointer to the lowest (first) byte in the allocated memory block

所以malloc分配一个内存块和returns一个指向这个块开始的指针。 malloc 的参数是您要分配的内存块的大小。

在您的情况下，您将通过 sizeof(struct tnode *)。因此，您正在为指向类型 struct tnode 的值的指针分配足够的内存。如果要为 struct tnode 本身分配内存，请将 sizeof 更改为 sizeof(struct tnode)。那么固定线应该是这样的

struct tnode * newnode = (struct tnode *) malloc(sizeof(struct tnode))

插入新节点时的AVL TREE Malloc Function

AVL TREE Malloc Functionwhen inserting a new node

c

malloc

pointers

avl-tree

null-pointer