-1

我目前需要实现一个最大节点堆，我的节点类在其中跟踪数据、父节点，然后是左右子节点。我的最大堆插入方法需要永远填充 100 个字符串的数组。这是我的代码：` 

public void insert(String name) {
MyNode node = new MyNode(name);
if (root ==null) {
        root = node;

    }
    else {
        MyNode parent = findSpot(root);
        if(parent.lChild==null) {
            parent.lChild=node;
            node.setParent(parent);

        }
        else {
            parent.rChild=node;
            node.setParent(parent);

        }


    }


}

public MyNode findSpot(MyNode curr) {
    if (curr.lChild == null) {
        return curr;
    }
    else if (curr.rChild==null) {
        return curr;
    }
    else {
        if (findSpot(curr.lChild).findHeight(root, curr, 1) > findSpot(curr.rChild).findHeight(root, curr, 1)) {
            return findSpot(curr.lChild);
        }
        else {
            return findSpot(curr.rChild);
        }
    }
}`

如果有人代码提供建议或告诉我出了什么问题，我们将不胜感激。

4

1 回答 1

1

如果您想了解为什么您的findSpot函数需要这么长时间，请在开头添加一行输出"findSpot <node>"，其中是正在搜索的节点的详细信息。您会发现递归算法被多次调用。而且看起来findHeight也经常被调用。我不确定，但看起来您正在对每次插入进行详尽的树搜索。

二叉堆必须保持 Shape 属性：它是一个完整的二叉树，除了可能是底部行，它是左填充的。因此，如果您知道堆中有多少节点，则可以轻松找到下一个节点的插入点。考虑这个堆：

      1
  2       3
4   5   6

堆中有 6 个节点。每当堆中有 6 个节点时，树将如下所示，并且下一个节点的插入点将是最右侧节点的右子节点（在本例中为 3 个）。

有趣的是，节点号的二进制表示告诉我们该节点在哪里。例如，二进制中的 6 是110. 去掉第一个数字 1，剩下的就是10。现在，从根开始并取数字中的下一个数字，如果数字为 0，则向左走，如果数字为 1，则向右走。然后取下一个数字并做同样的事情。重复直到你的数字用完。

在 6 的情况下，我们会从根到节点 3，然后从左到节点 6。

添加新节点时，增加计数并按照上述过程定位插入点。7是111二进制的。你砍掉高位，离开11。然后，从根开始向右，插入点是节点 3 的右子节点。

当然，一旦将节点放置在树中以满足形状属性，则必须执行标准的 re-heapify 以调整树中的节点以保持堆属性。

于 2018-03-29T13:33:49.257 回答