我一直在寻找一些指针,但一直没有找到。 我有一个项目任务,需要通过扩展给定的234树类来实现b树。
当树仍为234树时,
这里是我的b树类链接:http://pastebin.com/TcP0UMA2 我从命令提示符中使用所有这些内容。 运行时,以下是输出结果。
“nullPointerException”出现在这个语句所在的行:
当我看到这段代码时,我可以理解它正在检查
因为从这一点开始实际上没有子元素。我主要不确定如何从这个点开始修复它。
提前感谢,任何帮助都将不胜感激! -Frank
编辑: 看起来我的类链接有点被埋没了。如果以下更容易,请发布它。
当树仍为234树时,
234Tree
类是有效的。 似乎在尝试将其用作b树时,使用此类中的插入方法会导致错误。 为了防止234树分裂失效,我已将其复制到我的b树类中,以便可以进行重写。这里是我的b树类链接:http://pastebin.com/TcP0UMA2 我从命令提示符中使用所有这些内容。 运行时,以下是输出结果。
Enter first letter of show, insert, find, change, read, or quit: s<br/>
level=0 child=0 /20/30/50/70/<br/>
level=1 child=0 /10/<br/>
level=1 child=1 /25/<br/>
level=1 child=2 /35/40/45/<br/>
level=1 child=3 /60/<br/>
level=1 child=4 /80/90/100/<br/>
Enter first letter of show, insert, find, change, read, or quit: i<br/>
Enter value to insert: 85<br/>
Moving 2 items. Those values are 50, 70.<br/>
Exception in thread "main" java.lang.NullPointerException<br/>
at frankaddeliaproject2.BTree.insert(BTree.java:115)<br/>
at frankaddeliaproject2.Tree234App.main(Tree234App.java:43)<br/>
Java结果:1
我注意到的问题是当父节点变满时(在这个例子中它的顺序是5,所以它想在第5次插入时拆分节点)。这就是为什么尝试插入85时会在这一点上中断的原因。
while(true)
{
if( curNode.isFull() ) // if node full,
{
split(curNode); // split it
curNode = curNode.getParent(); // back up
// search once
curNode = getNextChild(curNode, dValue);
} // end if(node is full)
“nullPointerException”出现在这个语句所在的行:
if( curNode.isFull())
当我看到这段代码时,我可以理解它正在检查
curNode
是否已满,所以它会第一次运行,问题似乎出现在...curNode = getNextChild //...
因为从这一点开始实际上没有子元素。我主要不确定如何从这个点开始修复它。
提前感谢,任何帮助都将不胜感激! -Frank
编辑: 看起来我的类链接有点被埋没了。如果以下更容易,请发布它。
public class BTree extends Tree234 {
public void split(Node thisNode) // split the node
{
// assumes node is full
int tmp = Node.getOrder();
int counter = 0;
//figures out number of children to move during a move (2^n < x < 2^n+1)
while(tmp >= 2)
{
tmp /= 2;
counter++;
}
DataItem[] items = new DataItem[counter + 1];
for(int x = counter; x > 0; x--)
{
items[x] = thisNode.removeItem();
}
DataItem itemB;
Node parent;
Node[] children = new Node[counter];
int itemIndex;
itemB = thisNode.removeItem(); // this node
//makes array of children to move
int tmpcount = 0;
for(int i = counter; i > 0; i--)
{
children[tmpcount] = thisNode.disconnectChild(Node.getOrder() - i);
tmpcount++;
}
Node newRight = new Node(); // make new node
if(thisNode==root) // if this is the root,
{
root = new Node(); // make new root
parent = root; // root is our parent
root.connectChild(0, thisNode); // connect to parent
}
else // this node not the root
parent = thisNode.getParent(); // get parent
// deal with parent
itemIndex = parent.insertItem(itemB); // item B to parent
int n = parent.getNumItems(); // total items?
for(int j=n-1; j>itemIndex; j--) // move parent's
{ // connections
Node temp = parent.disconnectChild(j); // one child
parent.connectChild(j+1, temp); // to the right
}
// connect newRight to parent
parent.connectChild(itemIndex+1, newRight);
// deal with newRight
// moves items to newRight
// then alerts how many items are being moved and the values
String msg = "Moving " + counter + " items. Those values are ";
for(int y = 0; y < counter + 1; y++)
{
if(items[y] == null)
{
continue;
}
newRight.insertItem(items[y]);
//build output message
if(y < counter)
msg += items[y].dData + ", ";
else
msg += items[y].dData + ". ";
}
//outputs message
System.out.println(msg);
//reconnect children to new parent
for(int j = 0; j < counter; j++)
{
newRight.connectChild(j, children[j]);
}
} // end split()
// -------------------------------------------------------------
// gets appropriate child of node during search for value
public void insert(long dValue)
{
Node curNode = root;
DataItem tempItem = new DataItem(dValue);
while(true)
{
if( curNode.isFull() ) // if node full,
{
split(curNode); // split it
curNode = curNode.getParent(); // back up
// search once
curNode = getNextChild(curNode, dValue);
} // end if(node is full)
else if( curNode.isLeaf() ) // if node is leaf,
break; // go insert
// node is not full, not a leaf; so go to lower level
else
curNode = getNextChild(curNode, dValue);
} // end while
curNode.insertItem(tempItem); // insert new DataItem
} // end insert()
// -------------------------------------------------------------
}