- #include <string.h>
- #include <stdlib.h>
- #include <stdio.h>
- #include <assert.h>
- typedef int (*compFunc)(int,int);
- #define ROOT 1
- #define LEAF 2
- #define INTERNAL 4
- typedef struct node{
- int type;
- struct node* parent;
- #ifdef _DEBUG
- int * keys;
- #elif
- void** keys;
- #endif
- int size;
- } node;
- typedef struct leafNode{
- int type;
- struct node* parent;
- #ifdef _DEBUG
- int * keys;
- #elif
- void** keys;
- #endif
- int size;
- } leafNode;
- typedef struct internalNode{
- int type;
- struct node* parent;
- #ifdef _DEBUG
- int * keys;
- #elif
- void** keys;
- #endif
- int size;
- struct node** childs;
- int index;
- } internalNode;
- typedef struct btree{
- struct node *root;
- compFunc comp;
- int num;
- } btree;
- #include <queue>
- using namespace std;
- /*输出B tree,第一行是根节点,第二行是第二层的节点,节点之间用\\t分隔,接下来每一行是
- 第二层节点的每个节点的孩子,例如第三行是第二层第一个节点的孩子*/
- void dump(node* root){
- queue<node*> q;
- q.push(root);
- q.push(NULL);
- node sn;
- sn.type=-1;
- while(!q.empty()){
- node* n=q.front();
- q.pop();
- if(n==NULL)
- printf("\\n");
- else if(n->type==-1)
- printf("\\t");
- else {
- int i;
- internalNode* in;
- for(i=0;i<n->size;++i){
- printf("%d ",n->keys[i]);
- if(n->type&INTERNAL){
- in=(internalNode*)n;
- q.push(in->childs[i]);
- q.push(&sn);
- }
- }
- if(n->type&INTERNAL) {
- q.push(in->childs[in->size]);
- q.push(NULL);
- }
- }
- }
- }
- static node* leafNodeCreate(btree* b,node* parent){
- leafNode* leaf=(leafNode*)malloc(sizeof(leafNode));
- if(leaf==NULL)
- return NULL;
- #ifdef _DEBUG
- leaf->keys=(int*)malloc(sizeof(int)*b->num);
- #elif
- leaf->keys=(void**)malloc(sizeof(void*)*b->num);
- #endif
- if(leaf->keys==NULL) {
- free(leaf);
- return NULL;
- }
- leaf->size=0;
- leaf->type=LEAF;
- leaf->parent=parent;
- return (node*)leaf;
- }
- static node* internalNodeCreate(btree* b,node* parent){
- struct internalNode* node=(struct internalNode*)malloc(sizeof(struct internalNode));
- if(node==NULL)
- return NULL;
- #ifdef _DEBUG
- node->keys=(int*)malloc((sizeof(int))*b->num);
- #elif
- node->keys=(void**)malloc((sizeof(void*))*b->num);
- #endif
- if(node->keys==NULL) {
- free(node);
- return NULL;
- }
- node->childs=(struct node**)malloc((sizeof(void*))*(b->num+1));
- if(node->childs==NULL) {
- free(node->keys);
- free(node);
- return NULL;
- }
- node->size=0;
- node->type=INTERNAL;
- node->parent=parent;
- return (struct node*)node;
- }
- struct btree* btreeCreate(int num,compFunc comp){
- btree* b=(btree*)malloc(sizeof(btree));
- if(b==NULL)
- return NULL;
- b->num=num;
- b->root=leafNodeCreate(b,NULL);
- if(b->root==NULL){
- free(b);
- return NULL;
- }
- b->root->type|=ROOT;
- b->comp=comp;
- return b;
- }
- #define LESS 0
- #define GREATER 1
- static int binarySearch(int* keys,int len,int key,compFunc comp){
- if(len==0) return 0;
- int lastComp=0,op1=-1,op2=-1;
- int left=0,right=len-1,middle;
- int result;
- while(left<=right){
- if(left==right) lastComp=1;
- middle=(left+right)/2;
- result=comp(key,keys[middle]);
- if(result<0) {
- if(lastComp==0) op1=LESS;
- else op2=LESS;
- right=middle-1;
- }
- if(result>0) {
- if(lastComp==0) op1=GREATER;
- else op2=GREATER;
- left=middle+1;
- }
- if(result==0) return -1;
- }
- if(op2==LESS) return middle;
- if(op2==GREATER) return middle+1;
- }
- static int splitNode(struct btree* b,struct node* n,int toInsert,struct node* leftChild,struct node* rightChild,int* toInsert2,struct node** out){
- int len;
- int middle=(b->num)/2;
- struct node* created;
- struct internalNode* in;
- if(n->type&LEAF){
- len=binarySearch(n->keys,n->size,toInsert,b->comp);
- created=(struct node*)leafNodeCreate(b,n->parent);
- }
- else{
- in=(struct internalNode*)n;
- len=in->index;
- created=(struct node*)internalNodeCreate(b,n->parent);
- }
- assert(b->num==n->size);
- if(len<middle){
- *toInsert2=n->keys[middle];
- memcpy(created->keys,n->keys+middle+1,(b->num-middle-1)*sizeof(int));
- memmove(n->keys+len+1,n->keys+len,(middle-len)*sizeof(int));
- n->keys[len]=toInsert;
- n->size=middle+1;
- created->size=b->num-middle-1;
- }else {
- *toInsert2=n->keys[middle];
- if((len-middle)>1) {
- memcpy(created->keys,n->keys+middle+1,(len-middle-1)*sizeof(int));
- created->keys[len-middle-1]=toInsert;
- }else {
- created->keys[0]=toInsert;
- }
- if(len!=b->num)
- memcpy(created->keys+len-middle,n->keys+len,(b->num-len)*sizeof(int));
- n->size=middle;
- created->size=b->num-middle;
- }
- if(n->type&INTERNAL){
- internalNode* createdIn=(internalNode*)created;
- if(len<middle){
- memcpy(createdIn->childs,in->childs+middle+1,(b->num+1-middle-1)*sizeof(int));
- memmove(in->childs+len+2,in->childs+len+1,(middle+1-len)*sizeof(int));
- assert(in->childs[len]==leftChild);
- in->childs[len+1]=rightChild;
- }else {
- if((len-middle)>1) {
- memcpy(createdIn->childs,in->childs+middle+1,(len+1-middle-1)*sizeof(int));
- createdIn->childs[len+1-middle-1]=rightChild;
- }else {
- createdIn->childs[0]=rightChild;
- }
- if(len!=b->num) {
- memcpy(createdIn->childs+len-middle+1,in->childs+len+1,(b->num-len)*sizeof(int));
- }
- }
- for(int i=0;i<createdIn->size+1;++i)
- createdIn->childs[i]->parent=(node*)createdIn;
- }
- if(n->type &ROOT) {
- internalNode* newRoot=(internalNode*)internalNodeCreate(b,NULL);
- newRoot->type |=ROOT;
- created->parent=(node*)newRoot;
- n->parent=(node*)newRoot;
- n->type=created->type;
- b->root=(node*)newRoot;
- newRoot->size=1;
- newRoot->keys[0]=*toInsert2;
- newRoot->childs[0]=n;
- newRoot->childs[1]=created;
- dump((node*)newRoot);
- return 0;
- }
- *out=created;
- return 1;
- }
- static void insertNode(btree* b,struct node* n,int toInsert,struct node* leftChild,struct node* rightChild){
- if(n->size==b->num){
- #ifdef _DEBUG
- struct internalNode* in=(struct internalNode*)n;
- assert( (leftChild==NULL) || (leftChild==in->childs[in->index]));
- #endif
- int toInsert2;
- struct node* out;
- int flag=splitNode(b,n,toInsert,leftChild,rightChild,&toInsert2,(struct node**)&out);
- if(flag)
- insertNode(b,n->parent,toInsert2,n,out);
- return ;
- }
- int len;
- struct internalNode* in;
- if(n->type&LEAF){
- len=binarySearch(n->keys,n->size,toInsert,b->comp);
- }
- else{
- in=(struct internalNode*)n;
- len=in->index;
- }
- if(n->size-len!=0)
- memmove(n->keys+len+1,n->keys+len,(n->size-len)*sizeof(int));
- n->keys[len]=toInsert;
- if(n->type&INTERNAL) {
- assert(in->childs[len]==leftChild);
- if(n->size-len!=0) memmove(in->childs+len+2,in->childs+len+1,(in->size-len)*sizeof(int));
- in->childs[len+1]=rightChild;
- }
- n->size++;
- }
- static void insertLeaf(btree* b,node* n,int toInsert){
- insertNode(b,n,toInsert,NULL,NULL);
- }
- int btreeInsert(btree* b,int key){
- node* n=b->root;
- int index;
- while(!(n->type&LEAF)){
- internalNode* in=(internalNode*)n;
- index=binarySearch(in->keys,in->size,key,b->comp);
- in->index=index;
- n=in->childs[index];
- }
- insertLeaf(b,n,key);
- return 0;
- }
- int compare(int a,int b){
- int tmp1=(int)a;
- int tmp2=(int)b;
- if(tmp1<tmp2)
- return -1;
- if(tmp1>tmp2)
- return 1;
- return 0;
- }
- int main(){
- /*btree* b=btreeCreate(4,compare);
- for(int i=0;i<20;++i){
- btreeInsert(b,i);
- if(i>10)
- dump(b->root);
- }*/
- btree* b=btreeCreate(4,compare);
- for(int i=19;i>=0;--i){
- btreeInsert(b,i);
- if(i<15)
- dump(b->root);
- }
- system("pause");
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/090720149927.html
来源: http://www.codesnippet.cn/detail/090720149927.html