5

我在插入二项式堆时遇到问题，当我调用 insert 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();
        }
    }
}
4

2 回答 2

1

在您的方法中merge，您传递了一个BHeapobject y。您确实会更改任何内容，因为您在方法中创建并传递给的对象BHeap不会添加任何兄弟姐妹。while 循环永远不会运行。mergeinsert

另外，我认为您可能想查看您的merge方法。似乎您从未考虑过要合并的电流BHeap，而只是重新格式化给定的BHeap参数。

于 2013-10-29T18:45:49.183 回答
1

插入时，您正在创建一个新BHeap对象，然后将其传递给merge(). 你的 newBHeap没有rightSibling，所以你跳过整个while循环，只返回 new BHeap。所以新的BHeap变成了root整体BHeap，你扔掉了以前的东西。

更新：我不会写伪代码，因为它就在你的代码中。

所以你制作一个新的BHeapand Insert(1)。您的Insert方法创建第二个 newBHeap然后检查root当前BHeap. 那是空的，所以第二个BHeap变成了root. 没关系。

现在你Insert(2)。再次，创建另一个BHeap. 这次rootcurrentBHeap不为空，所以我们调用merge传入 new BHeap。请注意，这个新BHeap的现在（在内部merge）称为y. BHeap另请注意，除了设置字段之外，您没有对这个 new 做任何事情，key因此所有其他字段都是 null。

在里面merge你创建了另一个BHeap对象，并创建了另一个currentHeap引用y. （同样，只有key字段已设置，因此所有其他字段都为空。）您将 y 引用rightSibling为nextHeap，然后进入while循环。while循环说虽然ofrightSibling不currentHeap为空，但做一些事情。

但正如我上面所说，关于（又名你在其中创建的全新）的一切都是null。所以整个循环被跳过，你从.currentHeapyBHeapInsertwhileymerge

Insert然后接受 from 的返回值y并将其设置为rootcurrent 的BHeap。老人root被丢弃，坐在角落里，在垃圾收集器出现并将其拖入早期坟墓之前，为它悲惨的命运痛哭。新人root得意洋洋地欢呼，统治至高无上，国王BHeap（也是唯一的成员BHeap）......直到你打电话Insert(3)。

你呢？您将学习如何使用调试器。

于 2013-10-29T18:39:14.930 回答