### 2-3 tree Algorism bug(memory allocation)

i am trying to bulid 2-3 tree insertion function,it seem successfully in the beginning(from 1 to 14),but when i input 15,the output will beocme infinite and the program crashed.I used 3days to debug but still cannot find out the problem(maybe memory allocation?),thx!
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227`` ``````#include #include #define m 3 //n=number of data,m=max child,rounding up((m-1)/2)-1=indegree){ printf("%d\n",(*B)->data[i]); i++; } for(i=0;i<(*B)->indegree+1;i++){ printf("%d:",i); printbtree((*B)->pointer[i]); } } void list_Init(int *a){ int i; for(i=0;ii;j--){ a[j]=a[j-1]; b[j+1]=b[j]; } if(!pre) cur->indegree++; a[i]=data; b[i]=cur->pointer[0]; b[i+1]=cur->pointer[1]; bNode **q=cur->pointer[0]; if(q){ (*q)->parent=pre; } q=cur->pointer[1]; if(q){ (*q)->parent=pre; } } void InitBNode(bNode **N){ (*N)=(bNode*)malloc(sizeof(bNode)); int i; (*N)->indegree=0; for(i=0;ipointer[i]=NULL; } (*N)->parent=NULL; list_Init((*N)->data); } bNode** B_Tree_Search(bNode **B,bNode*** pre,int ele){ int i=0; if((*B)==NULL){ return NULL; } while(i<(*B)->indegree){ if(ele>(*B)->data[i]){ i++; } else if (ele<(*B)->data[i]&&(*B)->pointer[i]!=NULL){ *pre=B; return B_Tree_Search((*B)->pointer[i],pre,ele); } else{ break; } } if(i==m-1&&(*B)->pointer[i]!=NULL||(*B)->pointer[i]!=NULL){//if the pointer is not null,then can go to the next stage,otherwise stay at the same stage *pre=B; return B_Tree_Search((*B)->pointer[i],pre,ele); } else{ return B; } } void split(bNode **cur){//e,g, [6,7,8] spilie to (left)<6>,(root)<7>,<8>(right) bNode **a=(bNode**)malloc(sizeof(bNode*)); InitBNode(a); (*a)->data[0]=(*cur)->data[0]; (*a)->pointer[0]=(*cur)->pointer[0]; (*a)->pointer[1]=(*cur)->pointer[1]; (*a)->indegree++; bNode **c=(bNode**)malloc(sizeof(bNode*)); InitBNode(c); (*c)->data[0]=(*cur)->data[2]; (*c)->pointer[0]=(*cur)->pointer[2]; (*c)->pointer[1]=(*cur)->pointer[3]; (*c)->indegree++; bNode **b=(bNode**)malloc(sizeof(bNode*)); *b=NULL; InitBNode(b); (*b)->data[0]=(*cur)->data[1]; (*b)->pointer[0]=a; (*b)->pointer[1]=c; (*b)->indegree++; (*b)->parent=(*cur)->parent; (*c)->parent=b; (*a)->parent=b; free(*cur); (*cur)=*b; if((*cur)->parent){ AInsertion(cur,(*cur)->parent); } } void AInsertion(bNode **cur,bNode **pre){//****** (*pre)->indegree++; list_Insert(*cur,(*pre)->data,(*pre)->pointer,(*cur)->data[0],pre);//current node,previous data array,previoud pointer array,previous node if((*pre)->indegree==m){ split(pre); } } void Insertion(bNode **pre,bNode **cur,int data){ int i,n; list_Insert((*cur),(*cur)->data,(*cur)->pointer,data,NULL);//current node,current data array,previous pointer,data,previous node if(pre){ (*cur)->parent=pre; } else{ (*cur)->parent=NULL; } if((*cur)->indegree==m){ split(cur); } } void B_Tree_Insertion(bNode **B){//this B not equal to main B int data; bNode **pre=NULL,**cur=NULL; int i; for(i=1;i<30;i++){//<--15 chagne to 16,problem will occur pre=NULL; cur= B_Tree_Search(B,&pre,i);//pre to store the address of B Insertion(pre,cur,i); } } int main(){ int choice; bNode *B=(bNode*)malloc(sizeof(bNode)); InitBNode(&B); B_Tree_Insertion(&B); printbtree(&B); printf("\n\n"); }``````
Last edited on

However, working thru it, it's a bit of a mess.

To begin with, I assume `B` is your tree. Clearly, it should be a `struct bNode*`, not a `struct bNode**`.

You call `InitBNode`, but never define it. I expect it should something like be:
 ``12345`` ``````void InitBNode(struct bNode** node) { *node = (struct bNode*)calloc(1, sizeof(struct bNode)); if (!*node) exit(1); }``````

Then you call `B_Tree_Insertion`, which I would expect to insert a value into the tree, but it doesn't take a value as a parameter, just the tree.
Last edited on
thx, i correct it but it still doesn't work, i try to delete line 150`free(*cur);`, the program stop crash but the output is weird, can you tell me the reason of that?thx a lot!!!
Last edited on
I think you're being a little careless.

Consider `main()`. You've written:
 ``1234567891011121314151617181920212223242526`` ``````void list_Init(int *a){ int i; for (i = 0; i < m; i++) { a[i] = INT_MAX; } } void InitBNode(bNode **N) { (*N) = (bNode*)malloc(sizeof(bNode)); int i; (*N)->indegree = 0; for (i = 0; i < m+1; i++) { (*N)->pointer[i] = NULL; } (*N)->parent=NULL; list_Init((*N)->data); } int main() { bNode *B=(bNode*)malloc(sizeof(bNode)); InitBNode(&B); // ... ``````

Why are your variables uppercase? But more importantly, what happens to `B` in `main()`?
thx all of u, i solve it finally.
Windows 7 VS windows 10?
Hallo guys

There is an issue hear i would like to talk about. As most of you might already know Microsoft has already already announced windows 10 a few days ago. I am a windows 7 user and i a have been using it for years now and have got tired of it and i now want a change. I am planning to upgrade to windows 10 once it comes out but my question is will windows 10 be better than windows 7? Or will it be a dumb like windows 8?

I hope some of you may have some idea since you have seen the technical preview Microsoft has released on windows 10 a few days ago .