BayerTree.java
public class BayerTree
{
private int m; //m为B_树的阶
private BayerTreeNode bt;
// bt为树根指针
final int MaxKey=1000;
//关键字为最大值标记
private class BayerTreeNode
{ //B_树中的节点定义
int keyNum; //关键字的个数域
BayerTreeNode parent; //父节点指针
Object []key=new Object[m+1]; //保存n个关键字的域
BayerTreeNode []ptr=new BayerTreeNode[m+1];
// 保存n+1个指向子树的指针
int []rec=new int[m+1];
//保存记录的下标位置
}
public BayerTree(int mm)
{
m=mm;
bt=null; //构造方法
}
public void clear()
{
bt=null; //清除B_树
}
public int getM()
{
return m; //返回阶数
}
public int countKey()
{
return countKey(bt); //
}
public int countNode()
{return countNode(bt);}
public int depth()
{return depth(bt);}
public void print()
{
print(bt);
System.out.println();
}
public boolean insert(Object k,int num)
{ //向B_树中插入元素
if(bt==null)
{
bt=new BayerTreeNode();
bt.keyNum=1;
bt.parent=null;
bt.key[1]=k;
bt.key[2]=MaxKey;
bt.rec[1]=num;
bt.ptr[0]=bt.ptr[1]=null;
return true;
}
int i=0;
BayerTreeNode xp=bt,p=null;
while(xp!=null)
{
i=1;
while(((Comparable)k).compareTo(xp.key[i])>0)
i++;
if(((Comparable)k).compareTo(xp.key[i])==0)
return false;
else
{ p=xp;xp=xp.ptr[i-1];}
}
BayerTreeNode ap=null;
while(true)
{
int j,c;
for(j=p.keyNum;j>=i;j--)
{
p.key[j+1]=p.key[j];
p.rec[j+1]=p.rec[j];
p.ptr[j+1]=p.ptr[j];
}
p.key[i]=k;
p.rec[i]=num;
p.ptr[i]=ap;
p.keyNum++;
if(p.keyNum<=m-1)
{
p.key[p.keyNum+1]=MaxKey;
return true;
}
c=(m%2!=0? (m+1)/2 : m/2);
ap=new BayerTreeNode();
ap.keyNum=m-c;
ap.parent=p.parent;
for(j=1;j<ap.keyNum;j++)
{
ap.key[j]=p.key[j+c];
ap.rec[j]=p.rec[j+c];
}
for(j=0;j<ap.keyNum;j++)
{
ap.ptr[j]=p.ptr[j+c];
if(ap.ptr[j]!=null)
ap.ptr[j].parent=ap;
}
ap.key[m-c+1]=MaxKey;
p.keyNum=c-1;
k=p.key[c];
num=p.rec[c];
p.key[c]=MaxKey;
if(p.parent==null)
{
bt=new BayerTreeNode();
bt.keyNum=1;
bt.parent=null;
bt.key[1]=k;
bt.key[2]=MaxKey;
bt.rec[1]=num;
bt.ptr[0]=p;bt.ptr[1]=ap;
p.parent=ap.parent=bt;
return true;
}
p=p.parent;
i=1;
while(((Comparable)k).compareTo(p.key[i])>0)
i++;
} //while
}
public int search(Object k)
{ // 从B_树种查找关键字为k的记录的存储位置
int i;
BayerTreeNode p=bt;
while(p!=null)
{
i=1;
while(((Comparable)k).compareTo(p.key[i])>0)
i++;
if(((Comparable)k).compareTo(p.key[i])==0)
return p.rec[i];
else
p=p.ptr[i-1];
}
return -1;
}
private int countKey(BayerTreeNode btn)
{ //求B_树中所有关键字的总数
if(btn==null)
return 0;
else
{
int c=0;
for(int i=0;i<=btn.keyNum;i++)
c+=countKey(btn.ptr[i]);
return c+btn.keyNum;
}
}
private int countNode(BayerTreeNode btn)
{ //求B_树中所有节点数
if(btn==null)
return 0;
else
{
int c=0;
for(int i=0;i<=btn.keyNum;i++)
c+=countNode(btn.ptr[i]);
return c+1;
}
}
private int depth(BayerTreeNode btn)
{ //求B_树中所有关键字的总数
if(btn==null)
return 0;
else return 1+depth(btn.ptr[0]);
}
private void print(BayerTreeNode btn)
{ //中序遍历B_树中所有关键字和记录的存储位置
if(btn!=null)
{
print(btn.ptr[0]);
for(int i=1;i<=btn.keyNum;i++)
{
System.out.print("("+btn.key[i]+","+btn.rec[i]+")");
print(btn.ptr[i]);
}
}
}
}
Example10_4.java
public class Example10_4
{
public static void main(String [] args)
{
Integer []a={18,46,58,32,65,24,50,38,35,
47,82,93,20,33,48,15,26,44,78};
BayerTree t=new BayerTree(5);
for(int i=0;i<a.length;i++)
t.insert(a[i],i);
System.out.print("zhong xu bian li B- shu jie guo:");
t.print();
System.out.println("shu de jie:"+t.getM());
System.out.println("shu de shen du:"+t.depth());
System.out.println("shu de jie dian shu :"+t.countNode());
System.out.println("shu de guan jian zi shu :"+t.countKey());
System.out.println("guan jian zi wei 50 de 记录 wei zi :"+t.search(50));
System.out.println("guan jian zi wei 60 de 记录 wei zi :"+t.search(60));
t.clear();
}
}
求大牛啊!
3 个解决方案
#1
BayerTree t=new BayerTree(19);
你原来只初始化了5个
但A中有19个数据
你原来只初始化了5个
但A中有19个数据
#2
一针见血，高手啊
#3
教科书真坑啊? 书上的错误太多了
#1
BayerTree t=new BayerTree(19);
你原来只初始化了5个
但A中有19个数据
你原来只初始化了5个
但A中有19个数据
#2
一针见血，高手啊
#3
教科书真坑啊? 书上的错误太多了