C Implementing a Binary Search Tree

Question

I've been trying to implement a bst, in C. I think I'm almost there, but in my add node function, I create a temporary node called current to store the current node which is visited in the tree. Then when I modify the current node, my orignal pointer is not modified after the function finishes.

I've read up about this, and I think I may need a pointer of a pointer, but I stil don't quite know how to updated original struct.

A day before another person came with the same exercise. Add the homework tag... — Manos, Oct 21 '11 at 08:51
Don't cast the return value of `malloc` : http://stackoverflow.com/questions/1565496/specifically-whats-dangerous-about-casting-the-result-of-malloc — gnud, Oct 21 '11 at 09:21
why do you think the problem is there? btw wtf is this: `struct node **current = &(*string)->root;` ? — Karoly Horvath, Oct 21 '11 at 09:24
I don't think the problem is there - that's why it's a comment, not an answer :) — gnud, Oct 21 '11 at 10:04
I don't see a question. I see "I think I may need a pointer of a pointer", followed by a bunch of code. Do you have a question? — abelenky, Oct 21 '11 at 15:01

score 1 · Accepted Answer · answered Oct 21 '11 at 14:08

1

You are right that the problem has to do with the pointer to a pointer in bstlist_add. Here's an example that should help you figure out what you need to change in your code.

int a=10;
int b=20;

void noChange(int * pSomeInt);
void change(int ** ppSomeInt);

int main(int argc,char * argv[])
{
    int * pMainInt=&a;

    noChange(pMainInt);
    //pMainInt will still point to a

    //since the parameter to change is int **, we have to use & here
    change(&pMainInt);
    //pMainInt now points to b

    return 0;
}

void noChange(int * pSomeInt)
{
    //while pSomeInt is a pointer, it is a copy of pMainInt, not a pointer to it 
    //so this creates a pointer to the parameter, pSomeInt, itself
    int ** ppSomeInt=&pSomeInt;

    //so this changes the parameter, pSomeInt
    *ppSomeInt=&b;
}

void change(int ** ppSomeInt)
{
    //ppSomeInt is a pointer to pMainInt, which is itself an int *
    //so *ppSomeInt is pMainInt and not a copy of it
    *ppSomeInt=&b;
}

answered Oct 21 '11 at 14:08

IronMensan

6,761
1
26
35

Thanks all I was looking for was an example or an explanation, I dont know why some users such as Manos are so pushy. – user557240 Oct 21 '11 at 15:10
Just, one last thing. As I have to implement a specific header and therefore can't change the parameter to Bst ** bst, should I make another separate function, or is there a better way to do this? – user557240 Oct 21 '11 at 15:21
1

@user557240: It's an SO thing about homework integrity. If you don't tag homework problems correctly, someone might spoil the assignment by completing it for you. So always tag homework problems and provide what you've got so far (even/especially if it's not correct). People are likely to help you over your immediate stumbling block (and provide ancillary commentary like the malloc return value) without spoiling the assignment. – ccoakley Oct 21 '11 at 15:24
@user557240: You don't need to change the function signature to bstree_add. bstTree points to a bst that points to a root. You can change the root of that bst without needing to point to a different bst. So bstTree is fine. – ccoakley Oct 21 '11 at 15:33
@ccoakley, Thanks, I'll remember to add appropriate tags next time. I'm going to try and code it now. – user557240 Oct 21 '11 at 15:43
Also, the thing that has confused me, it that I've seen many implementations where no pointer of a pointer is used. I've tried following the code, but I don't know how their implementation works. http://www.stanford.edu/~blp/avl/libavl.html/BST_operations.c.txt I thought I was doing something similar. – user557240 Oct 22 '11 at 15:34

C Implementing a Binary Search Tree

1 Answers1