数据结构-B树的完整实现

数据结构B树的完整实现，自己写的，看完后一定有所启发。

#include“BTREE.h“
#include 
#include 
#include  


Status InitBTree（BTree &t）{
//初始化B树 
    t=NULL;
    return OK;
}


int SearchBTNode（BTNode *pKeyType k）{
//在结点p中查找关键字k的插入位置i 
    int i=0;
    for（i=0;ikeynum&&p->key[i+1]<=k;i++）;
    return i;
}


Result SearchBTree（BTree tKeyType k）{
/*在树t上查找关键字k返回结果（ptitag）。若查找成功则特征值
tag=1关键字k是指针pt所指结点中第i个关键字；否则特征值tag=0
关键字k的插入位置为pt结点的第i个*/

    BTNode *p=t*q=NULL; 							//初始化结点p和结点qp指向待查结点q指向p的双亲
    int found_tag=0;                        		//设定查找成功与否标志 
	int i=0;                 
    Result r;                             			//设定返回的查找结果 
    
    while（p!=NULL&&found_tag==0）{
        i=SearchBTNode（pk）;              			//在结点p中查找关键字k使得p->key[i]<=kkey[i+1]
        if（i>0&&p->key[i]==k）    		  			//找到待查关键字
            found_tag=1;                    		//查找成功 
        else{                               		//查找失败 
            q=p;                            
            p=p->ptr[i];
        }
    }

    if（found_tag==1）{                   			//查找成功
        r.pt=p;
        r.i=i;
        r.tag=1;
    }
    else{                            				//查找失败
        r.pt=q;
		r.i=i;
        r.tag=0;
    }
    return r;                       				//返回关键字k的位置（或插入位置）
}


void InsertBTNode（BTNode *&pint iKeyType kBTNode *q）{
//将关键字k和结点q分别插入到p->key[i+1]和p->ptr[i+1]中
    int j;
    for（j=p->keynum;j>i;j--）{  						//整体后移空出一个位置
        p->key[j+1]=p->key[j];
        p->ptr[j+1]=p->ptr[j];
    }
    p->key[i+1]=k;
    p->ptr[i+1]=q;
    if（q!=NULL） 
		q->parent=p;
    p->keynum++;
}


void SplitBTNode（BTNode *&pBTNode *&q）{
//将结点p分裂成两个结点前一半保留后一半移入结点q
    int i;
	int s=（m+1）/2;
    q=（BTNode *）malloc（sizeof（BTNode））;    			//给结点q分配空间
	 
    q->ptr[0]=p->ptr[s];                   			//后一半移入结点q
    for（i=s+1;i<=m;i++）{
        q->key[i-s]=p->key[i];
        q->ptr[i-s]=p->ptr[i];
    }
    q->keynum=p->keynum-s;                
    q->parent=p->parent;
    for（i=0;i<=p->keynum-s;i++） 					//修改双亲指针 
        if（q->ptr[i]!=NULL） 
			q->ptr[i]->parent=q;
    p->keynum=s-1;                 					//结点p的前一半保留修改结点p的keynum
}


void NewRoot（BTNode *&tKeyType kBTNode *pBTNode *q）{
//生成新的根结点t原p和q为子树指针
    t=（BTNode *）malloc（sizeof（BTNode））;       		//分配空间 
    t->keynum=1;
    t->ptr[0]=p;
    t->ptr[1]=q;
    t->key[1]=k;
    if（p!=NULL） 									//调整结点p和结点q的双亲指针 
		p->parent=t;
    if（q!=NULL） 
		q->parent=t;
    t->parent=NULL;
}


void InsertBTree（BTree &tint iKeyType kBTNode *p）{
/*在树t上结点q的key[i]与key[i+1]之间插入关键字k。若引起
结点过大则沿双亲链进行必要的结点分裂调整使t仍是B树*/
    BTNode *q;
    int finish_tagnewroot_tags;                   //设定需要新结点标志和插入完成标志 
    KeyType x;
    if（p==NULL）                      				//t是空树
        NewRoot（tkNULLNULL）;         			//生成仅含关键字k的根结点t
    else{
        x=k;
        q=NULL;
        finish_tag=0;       
        newroot_tag=0;
        while（finis

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-01-07 01:39  BTree\
     目录           0  2017-12-28 00:12  BTree\.git\
     文件           6  2017-12-25 12:00  BTree\.git\COMMIT_EDITMSG
     文件         307  2017-12-25 12:01  BTree\.git\config
     文件          73  2017-12-25 12:00  BTree\.git\description
     文件          23  2017-12-25 12:00  BTree\.git\HEAD
     目录           0  2017-12-28 00:12  BTree\.git\hooks\
     文件         478  2017-12-25 12:00  BTree\.git\hooks\applypatch-msg.sample
     文件         896  2017-12-25 12:00  BTree\.git\hooks\commit-msg.sample
     文件         189  2017-12-25 12:00  BTree\.git\hooks\post-update.sample
     文件         424  2017-12-25 12:00  BTree\.git\hooks\pre-applypatch.sample
     文件        1642  2017-12-25 12:00  BTree\.git\hooks\pre-commit.sample
     文件        1348  2017-12-25 12:00  BTree\.git\hooks\pre-push.sample
     文件        4898  2017-12-25 12:00  BTree\.git\hooks\pre-rebase.sample
     文件         544  2017-12-25 12:00  BTree\.git\hooks\pre-receive.sample
     文件        1492  2017-12-25 12:00  BTree\.git\hooks\prepare-commit-msg.sample
     文件        3610  2017-12-25 12:00  BTree\.git\hooks\update.sample
     文件         361  2017-12-25 12:00  BTree\.git\index
     目录           0  2017-12-28 00:12  BTree\.git\info\
     文件         240  2017-12-25 12:00  BTree\.git\info\exclude
     目录           0  2017-12-28 00:12  BTree\.git\logs\
     文件         154  2017-12-25 12:00  BTree\.git\logs\HEAD
     目录           0  2017-12-28 00:12  BTree\.git\logs\refs\
     目录           0  2017-12-28 00:12  BTree\.git\logs\refs\heads\
     文件         154  2017-12-25 12:00  BTree\.git\logs\refs\heads\master
     目录           0  2017-12-28 00:12  BTree\.git\logs\refs\remotes\
     目录           0  2017-12-28 00:12  BTree\.git\logs\refs\remotes\origin\
     文件         145  2017-12-25 12:01  BTree\.git\logs\refs\remotes\origin\master
     目录           0  2017-12-28 00:12  BTree\.git\objects\
     目录           0  2017-12-28 00:12  BTree\.git\objects\47\
     文件         139  2017-12-25 12:00  BTree\.git\objects\47\2915c74ddb456a6d6c9bb344b4e7b1f5b24a28
............此处省略24个文件信息