我在插入二项式堆时遇到麻烦，当我调用插入1时，它会打印(1)，然后插入2时，它会显示(2)而不是(1(2))，然后三个它会显示(3)而不是( 3)(1(2))。如果有人可以帮助解决我的问题，我将不胜感激。先感谢您。这是我的代码
public class BHeap {
int key;
int degree;//The degree(Number of children)
BHeap parent, leftmostChild, rightmostChild, rightSibling,root,previous,next;
public BHeap(){
key =0;
degree=0;
parent =null;
leftmostChild=null;
rightmostChild=null;
rightSibling=null;
root=null;
previous=null;
next=null;
}
public BHeap merge(BHeap y){
BHeap newHeap = new BHeap();
BHeap currentHeap = y;
BHeap nextHeap = y.rightSibling;
while(currentHeap.rightSibling !=null){
if(currentHeap.degree==nextHeap.degree){
if(currentHeap.key<nextHeap.key){
if(currentHeap.degree ==0){
currentHeap.leftmostChild=nextHeap;
currentHeap.rightmostChild=nextHeap;
currentHeap.rightSibling=nextHeap.rightSibling;
nextHeap.rightSibling=null;
nextHeap.parent=currentHeap;
currentHeap.degree++;
}
else{
newHeap = currentHeap;
newHeap.rightmostChild.rightSibling=nextHeap;
newHeap.rightmostChild=nextHeap;
nextHeap.parent=newHeap;
newHeap.degree++;
nextHeap.rightSibling=null;
nextHeap=newHeap.rightSibling;
}
}
else{
if(currentHeap.degree==0){
nextHeap.rightmostChild=currentHeap;
nextHeap.rightmostChild.root = nextHeap.rightmostChild;//add
nextHeap.leftmostChild=currentHeap;
nextHeap.leftmostChild.root = nextHeap.leftmostChild;//add
currentHeap.parent=nextHeap;
currentHeap.rightSibling=null;
currentHeap.root=currentHeap;//add
nextHeap.degree++;
}
else{
newHeap=nextHeap;
newHeap.rightmostChild.rightSibling=currentHeap;
newHeap.rightmostChild=currentHeap;
currentHeap.parent= newHeap;
newHeap.degree++;
currentHeap=newHeap.rightSibling;
currentHeap.rightSibling=null;
}
}
}
else{
currentHeap=currentHeap.rightSibling;
nextHeap=nextHeap.rightSibling;
}
}
return y;
}
public void Insert(int x){
BHeap newHeap= new BHeap();
newHeap.key=x;
if(this.root==null){
this.root=newHeap;
}
else{
this.root = merge(newHeap);
}
}
public void Display(){
System.out.print("(");
System.out.print(this.root.key);
if(this.leftmostChild != null){
this.leftmostChild.Display();
}
System.out.print(")");
if(this.rightSibling!=null){
this.rightSibling.Display();
}
}
}
最佳答案
插入时，您要创建一个新的BHeap对象，然后将其传递给merge()。您的新BHeap没有rightSibling，因此您跳过了整个while循环，只返回了新的BHeap。因此，新的BHeap变成整个root的BHeap，然后您丢弃之前的内容。
更新:我不会编写伪代码，因为它就在您的代码中。
因此，您将创建一个新的BHeap和Insert(1)。您的Insert方法将创建第二个新的BHeap，然后检查当前root的BHeap。这是空的，因此第二个BHeap成为root。没关系。
现在您Insert(2)。再次，创建另一个BHeap。这次，当前root的BHeap不为null，因此我们将merge传入新的BHeap。请注意，此新的BHeap现在(在merge内部)称为y。还要注意，除了设置BHeap字段之外，您对此新的key都没有做任何事情，因此所有其他字段均为空。
在merge内，您可以创建另一个BHeap对象，并创建另一个引用currentHeap的引用y。 (同样，仅设置了key字段，因此所有其他字段均为空。)将y的rightSibling称为nextHeap，然后进入while循环。 while循环说，虽然rightSibling的currentHeap不为空，但要做很多事情。
但是正如我在上面说的，有关currentHeap(又称y或您在BHeap中创建的全新Insert)的所有信息都是 null 。因此，将跳过整个while循环，并从y返回merge。
然后Insert接受y的返回值，并将其设置为当前root的BHeap。旧的root被丢弃，在角落里因悲惨的命运而痛苦地哭泣，然后垃圾收集器出现并将其拖入早期的坟墓。新的root欢呼雀跃，并成为BHeap的王者(也是BHeap的唯一成员)至高无上的王位...直到您调用Insert(3)。
和你？您将学习如何使用调试器。
关于java - 二项式堆插入Java，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19666235/