Inserting in a Binary Search Tree

问题:

I've made a binary search tree

struct BTNode
{
    int info;
    struct BTNode *left,*right;
};

I've wrote a code to insert a node in the tree

void insert(struct BTNode *root,int data)
{
    struct BTNode *ptr;
    struct BTNode *n=malloc(sizeof(struct BTNode));
    n->info=data;
    n->left=NULL;
    n->right=NULL;
    if(root==NULL)
    root=n;
    else{
    ptr=root;
    while(ptr!=NULL){
        if(data<ptr->info){
            if(ptr->left==NULL)
            ptr->left=n;
            else
            ptr=ptr->left;
        }
        else if(data>ptr->info){
            if(ptr->right==NULL)
            ptr->right=n;
            else
            ptr=ptr->right;
        }
    }
    }
}

and a main() function

int main()
{
    struct BTNode *root=NULL;
    int choice,data;
    printf("\n1.Insert 2.Preorder 3.Exit\n");
    scanf("%d",&choice);
    switch(choice){
        case 1:
        printf("\nWrite the data: ");
        scanf("%d",data);
        insert(root, data);
        break;

But when I try to insert a node, my program crashes. Any hints what's the problem?

回答1:

You should be passing in a pointer to your root pointer if you want to be able to change where your root pointer points (sorry if that got a bit convoluted).

What you'll want is something like this:

void insert(struct BTNode **root,int data)
{
...
    if(*root == NULL) {
        *root = n;
    }
...
}

And then when you call it, you'd pass in the address to your root pointer:

int main()
{
    struct BTNode *root=NULL;
    int data;
    ...
    scanf("%d", &data);
    insert(&root, data);
    ...
}

Also note above: you should be passing in the address of your variable to scanf. Maybe that was just a typo as you transferred since you did that properly with your choice var.

回答2:

As other people have said, modifying a pointer that was a parameter won't have any effect outside of the method.

C passes pointers by value not by reference. Meaning the pointer you're dealing with in the function is a different pointer that just points to the same thing. You have to pass a pointer to a pointer like the answer above me.

I wish I could've just commented this explanation but I guess I need reputation to do that..