数据结构B树的设计与实现

数据结构B树的设计与实现

B树的插入算法在编写过程中还是觉得比较难写的，主要的问题是，结点的分裂，
对叶子结点的分裂和对非叶节点的分裂不一样，还有就是当ptr->parent==NULL,
需要新建父结点，而新建的结点始终是树的根结点，还有结点分裂过程中子树指
针的变化还是很复杂的，不过终于实现了，分享一下我的代码，可以直接运行，
本程序没有包含我编写的其他头文件，代码如下，大家多多讨论：
另外，由于B树不同于其他的树，所有我考虑了一下，还是采用缩进格式来显示
B树了，因为每个结点有多个关键码，所以用广义表形式不显示不好。

#ifndef BTREE_H
#define BTREE_H

#include
#include
const int maxValue=10000;

/////////////////////////////////////////////////
//BTreeNodeB树的结点的定义
/////////////////////////////////////////////////
template
struct BTreeNode
{
int n; //结点中关键码的个数
BTreeNode* parent; //当前结点的父结点的指针

T* key; //m+1个元素存放关键码,其中key[0]和key[m]没有用
BTreeNode** //子树指针的结点数组(一共有m棵子树),m+1个元素
subTree; //最后一个元素subTree[m]在插入溢出的时候使用
int** recptr; //每个索引项中指向数据区相应记录起始地址的指针数组
BTreeNode(int m) //构造函数
{
n=0; //关键码个数初始化为0
parent=NULL; //父结点指针初始化为空
key=new T[m+1]; //开辟关键码数组的空间
subTree=new //开辟子树的指针数组的内存空间
BTreeNode*[m+1]; //从p0,p1,p2,...p(m-1)共m棵子树
for(int i=0;i<=m;i++)
subTree[i]=NULL; //子树数组先全部初始化为空
};
bool Insert(const T& x //把一个关键码插入到当前的B树结点中
,BTreeNode* p) //也把附带的新建的右子树的指针插入subTree[]中
{
for(int i=1;i<=n;i++) //寻找插入关键码的位置
{
if(x break;
};
for(int j=n;j>=i;j--) //挪处新的插入位置来
key[j+1]=key[j];
key[i]=x; //插入结点
n++;

for(j=n;j>=i;j--) //把新分裂开来的右子树结点插入subTree[]中
subTree[j+1]=subTree[j];
subTree[i]=p;
return true;
};
void Display() //显示当前结点所有关键码
{
for(int i=1;i<=n;i++)
cout< };
};
/////////////////////////////////BTree定义结束

/////////////////////////////////////////////////
//Triple结构 返回搜索结果用的三元组
/////////////////////////////////////////////////
template
struct Triple
{
BTreeNode* r; //结点指针
int i; //关键码在当前结点中的序号
int tag; //tag=0:搜索成功,tag=1:搜索失败
};
////////////////////////////////Triple结构结束

/////////////////////////////////////////////////
//BTree B树的定义;
//m阶B树的根至少有两个子树，
//其他的结点至少应该有int(m/2)+1个子树
//所有的失败结点都在一个层次上
/////////////////////////////////////////////////
template
class BTree
{
private:
BTreeNode* root; //树根结点指针
int m; //即B树的阶数
public:
BTree(int x) //空构造函数,构造一棵空x路的搜索树
{root=NULL;m=x;};
BTree(int x,BTreeNode* r)
{root=r;m=x;}; //用指定的树根来初始化当前的m路搜索树
void Insert( //在树指定父结点的情况下插入一个结点
BTreeNode* pa, //指定要出入的位置的父结点
BTreeNode* subTree, //要插入的结点的指针
int i); //表示插入到pa的第i个子树的位置

Triple //搜索指定关键码x对应的结点
Search(const T& x);
void RootFirst( //递归:以先根的方式遍历当前的搜索树
BTreeNode* subTree);
void RootFirst() //调用上面的递归函数
{RootFirst(root);};
bool Insert(const T& x); //B树的插入操作
void Display(
BTreeNode* p,int i); //递归:以缩进的格式显示当前的B树
void Display() //调用上面的递归函数
{cout<<"*****当前B树的缩进结构显示*****:"< Display(root,1);};
};
//////////////////////////////////////B树声明结束

/////////////////////////////////////////////////
//RootFirst()公有成员函数
//以先根的方式递归遍历当前B树
/////////////////////////////////////////////////
template
void BTree::RootFirst(BTreeNode* st)
{
if(st!=NULL)
{
int n=st->n;
cout<<"当前结点有"< <<"个关键码:"< for(int k=1;k<=n;k++) //输出当前结点的所有的关键码
cout<key[k]<<" ";
cout< for(int i=0;i<=n;i++) //递归输出所有的子树
RootFirst(st->subTree[i]);
};
};
//////////////////////////////RootFirst()函数结束

/////////////////////////////////////////////////
//Search()公有成员函数 搜索具有指定关键码的
//的结点并且以三元组的形式进行返回,如果没有搜索
//成功就把该关键码插入到当前驻留的结点中去
/////////////////////////////////////////////////
template
Triple BTree::Search(const T& x)
{
Triple result; //结果三元组
BTreeNode* ptr=root; //从根结点开始搜索
BTreeNode* pre;

int i;
while(ptr!=NULL)
{
for(i=1;i<=ptr->n;i++) //在结点内部进行顺序搜索
{
if(ptr->key[i]==x) //如果找到
{
result.r=ptr; //当前查找驻留的结点指针
result.i=i; //查找成功的关键码
result.tag=1; //是否查找成功
return result;
};
if(ptr->key[i]>x) //查找失败
break;
};
pre=ptr;
ptr=ptr->subTree[i-1]; //从失配的关键码左边的子树继续查找
};

result.r=pre;
result.i=i; //可以在i-1和i之间进行插入
result.tag=0; //查找失败

return result;
};
/////////////////////////////////Search()函数结束

/////////////////////////////////////////////////
//Insert()公有成员函数 B树的插入操作
//把指定的关键码插入到B树中,使得仍然满足B树的要求
//首先对B树进行搜索,如果关键码已经存在则插入失败,
//否则执行插入，并按B树要求进行调整
//一般来说,执行插入的肯定是在叶子结点上进行
//但是如果查找成功的话,可能在非叶子结点上就结束了
/////////////////////////////////////////////////
template
bool BTree::Insert(const T& x)
{

if(root==NULL) //如果当前的B树是空的
{
root=new BTreeNode(m); //新建一个结点
root->Insert(x,NULL); //把关键码插入到key[]数组第一个位置
return true;
};


Triple Tp; //查找结果三元组
Tp=Search(x);
int IsIn=Tp.tag;
if(IsIn==1) //关键码已经存在
{
cout<<"关键码已存在!"< return false; //插入失败
};


BTreeNode* ptr=Tp.r; //查找失败而驻留的结点
int loc=Tp.i-1; //在k[loc]后进行插入
int pkey=x;
BTreeNode* p=NULL; //随关键一起要插入的右子树的根结点
do
{
ptr->Insert(pkey,p); //把关键码和相关的新分裂的右结点插入当前结点
if(ptr->n>m-1) //如果关键码溢出,则需要进行调整
{

int k=ptr->key[m/2+1]; //提取出要上提的关键码
BTreeNode* right //建立分裂后右边的结点
=new BTreeNode(m);
right->n=ptr->n-m/2-1; //右结点的关键码个数
for(int i=m/2+2;i<=ptr->n;i++)
right->key[i-m/2-1] //把右半边的关键码复制进入右结点
=ptr->key[i];
for(i=m/2+1;i<=ptr->n;i++)
{
right->subTree[i-m/2-1]
=ptr->subTree[i]; //把相应的分裂后的右结点子树指针复制入新结点
}
ptr->n=m/2; //修改原结点使之成为左结点
right->parent
=ptr->parent; //新分裂的结点
p=right; //p是随k一起上提的新建分裂右结点指针
pkey=k;


if(ptr->parent==NULL) //如果当前结点没有父结点,就新建父结点
{
BTreeNode* newp //新建一个父结点
=new BTreeNode(m);
newp->key[1]=k; //插入新关键码
newp->subTree[0] //新关键码左边的子树
=ptr;
newp->subTree[1] //新关键码右边的子树
=right;
newp->n=1; //新关键码个数为1
ptr->parent=newp; //设置父结点指针
right->parent=newp;
root=newp;
return true; //插入成功并结束
}
else //如果有父结点存在
ptr=ptr->parent; //把上提的关键码继续插入父结点
}
else //不溢出则插入成功
return true;
}while(ptr!=NULL);

return true;
};
/////////////////////////Insert()公有成员函数结束

/////////////////////////////////////////////////
//Display()公有成员函数
//递归:显示当前B树的缩进格式
/////////////////////////////////////////////////
template
void BTree::Display(BTreeNode* p,int i)
{
if(p!=NULL)
{
for(int j=0;j cout<<" "; //控制缩进的格数
cout<<"当前结点是:关键码个数"<n<<" "
<<"关键码的内容是";
for(int k=1;k<=p->n;k++)//显示当前结点所有关键码
cout<key[k]<<" ";
cout< for(k=0;k<=p->n;k++) //递归显示子树,递归向后缩进
Display(p->subTree[k],i+5);
};
};
////////////////////////////////Display()函数结束

#endif

#include"BTree.h"

/////////////////////////////////////////////////
//main()函数 测试B树的程序
/////////////////////////////////////////////////
int main()
{
BTree BT(3);
BT.Insert(53); //依此在B树中插入关键码
BT.Insert(75);
BT.Insert(139);
BT.Insert(49);
BT.Insert(145);
BT.Insert(36);
BT.Insert(101);
BT.Insert(150);
BT.Insert(170);
BT.Insert(25);
BT.Insert(13);

BT.Display(); //显示当前B树的内容
return 0;
};
///////////////////////////////////main()函数结束追问头文件发一下

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息