谈谈B树的关键码算法编写的一点体会。
前几天发的那个BTree<T>::Insert(const T& x)在逻辑上有点问题，在这里做点修正，再说点体会，前几天写的算法在插入少数的关键码
时没有出现问题，因为关键码个数少，没有出现结点的二次分裂，
在后来的调试中，对于二次分裂出现后，parent指针就出现了问题，
在叶子结点分裂后，关键码上提继续插入父结点的时候，父结点仍然
溢出，再次进行分裂时，对于刚分裂出来的right结点的子结点中的
parent指针仍然指向分裂前的那个结点，而分裂前的那个结点指针在
分裂后成了左结点的指针，所以此时出现了问题，（我是在插入很多
关键码后才发现的），后来我先后想出了两个办法：
（1）我另外写了递归算法ParentAdjust()函数，即每次分裂后对所有
的结点的parent指针进行一次调整，可这样效率太低了，对于实际应用
中访问磁盘的次数就太多了，后来作了以下的改进，即（2）所谈，
（2）在Insert()算法中，我在每次结点分裂后，把新分裂出来的right
新结点的所有子结点进行一轮回访，把他们的parent指针设置成right,
也就是说在分裂后，还得把right的子结点重新从磁盘中调出来，我计算
了一下，新分裂的right的子结点的个数是固定的m-int(m/2)个，也就是
说每分裂一次要回访磁盘m-int(m/2)。
修改后的代码如下，这回已经调试通过，无论怎么插入都没有任何问题：
#ifndef BTREE_H
#define BTREE_H
#include<iostream.h>
#include<stdlib.h>
const int maxValue=10000;
/////////////////////////////////////////////////
//BTreeNode<T>B树的结点的定义
/////////////////////////////////////////////////
template<class T>
struct BTreeNode
{
int n; //结点中关键码的个数
BTreeNode<T>* parent; //当前结点的父结点的指针
T* key; //m+1个元素存放关键码,其中key[0]和key[m]没有用
BTreeNode<T>** //子树指针的结点数组(一共有m棵子树),m+1个元素
subTree; //最后一个元素subTree[m]在插入溢出的时候使用
int** recptr; //每个索引项中指向数据区相应记录起始地址的指针数组
BTreeNode(int m) //构造函数
{
n=0; //关键码个数初始化为0
parent=NULL; //父结点指针初始化为空
key=new T[m+1]; //开辟关键码数组的空间
subTree=new //开辟子树的指针数组的内存空间
BTreeNode<T>*[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<T>* p) //也把附带的新建的右子树的指针插入subTree[]中
{
for(int i=1;i<=n;i++) //寻找插入关键码的位置
{
if(x<key[i])
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<<key[i]<<" ";
};
};
/////////////////////////////////BTree<T>定义结束
/////////////////////////////////////////////////
//Triple<T>结构 返回搜索结果用的三元组
/////////////////////////////////////////////////
template<class T>
struct Triple
{
BTreeNode<T>* r; //结点指针
int i; //关键码在当前结点中的序号
int tag; //tag=0:搜索成功,tag=1:搜索失败
};
////////////////////////////////Triple<T>结构结束
/////////////////////////////////////////////////
//BTree<T> B树的定义;
//m阶B树的根至少有两个子树，
//其他的结点至少应该有int(m/2)+1个子树
//所有的失败结点都在一个层次上
/////////////////////////////////////////////////
template<class T>
class BTree
{
private:
BTreeNode<T>* root; //树根结点指针
int m; //即B树的阶数
public:
BTree(int x) //空构造函数,构造一棵空x路的搜索树
{root=NULL;m=x;};
BTree(int x,BTreeNode<T>* r)
{root=r;m=x;}; //用指定的树根来初始化当前的m路搜索树
void Insert( //在树指定父结点的情况下插入一个结点
BTreeNode<T>* pa, //指定要出入的位置的父结点
BTreeNode<T>* subTree, //要插入的结点的指针
int i); //表示插入到pa的第i个子树的位置
Triple<T> //搜索指定关键码x对应的结点
Search(const T& x);
void RootFirst( //递归:以先根的方式遍历当前的搜索树
BTreeNode<T>* subTree);
void RootFirst() //调用上面的递归函数
{RootFirst(root);};
bool Insert(const T& x); //B树的插入操作
void ParentAdjust(
BTreeNode<T>* ptr); //子树父结点指针的重新调整
void ParentAdjust() //调用上面的函数
{ParentAdjust(root);};
void Display(
BTreeNode<T>* p,int i); //递归:以缩进的格式显示当前的B树
void Display() //调用上面的递归函数
{cout<<"*****当前B树的缩进结构显示*****:"<<endl;
Display(root,1);};
};
//////////////////////////////////////B树声明结束
/////////////////////////////////////////////////
//RootFirst()公有成员函数
//以先根的方式递归遍历当前B树
/////////////////////////////////////////////////
template<class T>
void BTree<T>::RootFirst(BTreeNode<T>* st)
{
if(st!=NULL)
{
int n=st->n;
cout<<"当前结点有"<<n
<<"个关键码:"<<endl;
for(int k=1;k<=n;k++) //输出当前结点的所有的关键码
cout<<st->key[k]<<" ";
cout<<endl<<endl;
for(int i=0;i<=n;i++) //递归输出所有的子树
RootFirst(st->subTree[i]);
};
};
//////////////////////////////RootFirst()函数结束
/////////////////////////////////////////////////
//Search()公有成员函数 搜索具有指定关键码的
//的结点并且以三元组的形式进行返回,如果没有搜索
//成功就把该关键码插入到当前驻留的结点中去
/////////////////////////////////////////////////
template<class T>
Triple<T> BTree<T>::Search(const T& x)
{
Triple<T> result; //结果三元组
BTreeNode<T>* ptr=root; //从根结点开始搜索
BTreeNode<T>* 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<class T>
bool BTree<T>::Insert(const T& x)
{
/*如果当前的B树是空的,就新建之*/
if(root==NULL) //如果当前的B树是空的
{
root=new BTreeNode<T>(m); //新建一个结点
root->Insert(x,NULL); //把关键码插入到key[]数组第一个位置
return true;
};
/*如果当前的B树不空,就搜索该树*/
Triple<T> Tp; //查找结果三元组
Tp=Search(x);
int IsIn=Tp.tag;
if(IsIn==1) //关键码已经存在
{
cout<<"关键码已存在!"<<endl;
return false; //插入失败
};
/*插入关键码直到结点关键码不溢出为止*/
BTreeNode<T>* ptr=Tp.r; //查找失败而驻留的结点
int loc=Tp.i-1; //在k[loc]后进行插入
int pkey=x;
BTreeNode<T>* p=NULL; //随关键一起要插入的右子树的根结点
int firstSplit=1; //是否是叶子结点分裂的标志
do
{
ptr->Insert(pkey,p); //把关键码和相关的新分裂的右结点插入当前结点
if(ptr->n>m-1) //如果关键码溢出,则需要进行调整
{
/*以下处理结点的分裂*/
int k=ptr->key[m/2+1]; //提取出要上提的关键码
BTreeNode<T>* right //建立分裂后右边的结点
=new BTreeNode<T>(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; //新分裂的结点
for(i=0;i<=right->n;i++)//回访right的所有子结点，重新设置parent指针
{
BTreeNode<T>*& p= //把刚分裂出来的right结点的子结点parent指针重新调整
right->subTree[i];
if(p!=NULL)
p->parent=right;
}
p=right; //p是随k一起上提的新建分裂右结点指针
pkey=k;
/*如果当前的结点没有父结点*/
if(ptr->parent==NULL) //如果当前结点没有父结点,就新建父结点
{
BTreeNode<T>* newp //新建一个父结点
=new BTreeNode<T>(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()公有成员函数结束
/////////////////////////////////////////////////
//ParentAdjust()公有成员函数 父结点指针的调整
//递归:调整以ptr为根的所有子树的所有的结点父指针
/////////////////////////////////////////////////
template<class T>
void BTree<T>::ParentAdjust(BTreeNode<T>* ptr)
{
if(ptr!=NULL)
{
for(int i=0;i<=ptr->n;i++) //递归调整每个子树
{
if(ptr->subTree[i]!=NULL)
{
ptr->subTree[i]->parent
=ptr; //设置父结点指针
ParentAdjust( //递归调整子树
ptr->subTree[i]);
}
};
};
};
///////////////////////////ParentAdjust()函数结束
/////////////////////////////////////////////////
//Display()公有成员函数
//递归:显示当前B树的缩进格式
/////////////////////////////////////////////////
template<class T>
void BTree<T>::Display(BTreeNode<T>* p,int i)
{
if(p!=NULL)
{
for(int j=0;j<i;j++)
cout<<" "; //控制缩进的格数
cout<<"当前结点是:关键码个数"<<p->n<<" "
<<"关键码的内容是";
for(int k=1;k<=p->n;k++)//显示当前结点所有关键码
cout<<p->key[k]<<" ";
cout<<endl;
for(k=0;k<=p->n;k++) //递归显示子树,递归向后缩进
Display(p->subTree[k],i+5);
};
};
////////////////////////////////Display()函数结束
#endif
以上探讨的细节问题是书本上没有涉及到的，真正体会到，
如果完全自己编写算法，你会理解得很深的，如果想学好
数据结构，学好算法和编程，必须自己动手的。
[[it] 本帖最后由 geninsf009 于 2008-11-23 21:09 编辑 [/it]]
