第十五周 项目3 B-树的基本操作

/*   
文件名称：main.cpp  
  
作者       :孙彩虹  
  
完成日期：2015年12月11日  
  
*/

 
　　实现B-树的基本操作。基于序列{4, 9, 0, 1, 8, 6, 3, 5, 2, 7}完成测试。
　　（1）创建对应的3阶B-树b，用括号法输出b树。
　　（2）从b中分别删除关键字为8和1的节点，用括号法输出删除节点后的b树。

#include 
#include 
#define MAXM 10                     //定义B-树的最大的阶数
typedef int KeyType;                //KeyType为关键字类型
typedef struct node                 //B-树结点类型定义
{int keynum;                     //结点当前拥有的关键字的个数KeyType key[MAXM];              //key[1..keynum]存放关键字,key[0]不用struct node *parent;            //双亲结点指针struct node *ptr[MAXM];         //孩子结点指针数组ptr[0..keynum]
} BTNode;
typedef struct                      //B-树的查找结果类型
{BTNode *pt;                     //指向找到的结点int i;                          //1..m,在结点中的关键字序号int tag;                        //1:查找成功,O:查找失败
}  Result;
int m;                              //m阶B-树,为全局变量
int Max;                            //m阶B-树中每个结点的至多关键字个数,Max=m-1
int Min;                            //m阶B-树中非叶子结点的至少关键字个数,Min=(m-1)/2
int Search(BTNode *p,KeyType k)
{//在p->key[1..keynum]中查找i,使得p->key[i]<=kkey[i+1]int i=0;for(i=0; ikeynum && p->key[i+1]<=k; i++);return i;
}
Result SearchBTree(BTNode *t,KeyType k)
{/*在m阶t树t上查找关键字k,返回结果(pt,i,tag)。若查找成功,则特征值tag=1,指针pt所指结点中第i个关键字等于k；否则特征值tag=0,等于k的关键字应插入在指针Pt所指结点中第i和第i+1个关键字之间*/BTNode *p=t,*q=NULL; //初始化,p指向待查结点,q指向p的双亲int found=0,i=0;Result r;while (p!=NULL && found==0){i=Search(p,k);              //在p->key[1..keynum]中查找i,使得p->key[i]<=kkey[i+1]if (i>0 && p->key[i]==k)    //找到待查关键字found=1;else{q=p;p=p->ptr[i];}}r.i=i;if (found==1)                   //查找成功{r.pt=p;r.tag=1;}else                            //查找不成功,返回K的插入位置信息{r.pt=q;r.tag=0;}return r;     

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！