5

首先，这个问题不是家庭作业。我目前正在阅读 Robert Lafore 的《Data Structures and Algorithms 2nd Edition》一书。在第 10 章中，我们学习了 2-3-4 树，然后被要求编写一个方法来找到该树中的最小值。

从概念的角度来看，我了解最小值在哪里。它只是叶子中最左边的数据项。

从编程的角度来看，我对如何实现查找此数据项的方法有点困惑。我有一个布尔值，可以判断节点是否是叶子。所以我最初做的是这样的：

  public long minValue() {
   Node curNode = root; // current node = root
   long min = curNode.getMin();
   while(!curNode.isLeaf()) { // while current node is NOT a leaf
       curNode = getNextChild(curNode, min);
   } // end while
   return min;
} // end minValue()

这是做什么的（至少我认为它应该做的，是创建一个从根节点开始的 curNode。然后创建一个存储 curNode.getMin 的最小值。getMin() 只获取索引 0 处数组的值（其中应该保持最小值）。然后，当当前节点不是叶子时，我们应该从最小值点遍历到下一个孩子。一旦当前节点是叶子，它应该返回最小值。

但这不起作用。有谁知道如何实现这一点？提示或建议或其他任何东西？

编辑：要查看每个类以及它们如何交互，这里是每个单独类的链接。我把最小值方法放在我的 Tree234 类中

DataItem、Node、Tree234以及运行程序的位置Tree234App

4

2 回答 2

3

首先，为了尽快获得更好的帮助，请发布一个SSCCE，它为我们提供了整个程序的最小实现 - 我们可以将其 c/p 到我们自己的 IDE 中并自己运行以查看发生了什么。当我们只看到您的这段代码时，很难说出为什么“这不起作用”。

其次，您需要详细说明“这不起作用”是什么意思——即准确地告诉我们它在做什么或不做什么是出乎意料的。代替你这样做，我们怎么能肯定地告诉你它为什么这样做。

但是，会跳出一件事：您将实例min化为根节点的最小（直接）子节点，然后（可能）遍历树以找到其中最左边的元素，但随后您将返回相同的min值您最初创建的。换句话说，虽然您的迭代例程可能完全按照您的意愿行事，但您并没有因此而对返回值做任何事情。

我怀疑您需要执行以下操作：

  public long minValue() {
      Node curNode = root;
      long min = curNode.getMin();
      while(!curNode.isLeaf()) { // 
           curNode = getNextChild(curNode, min); //it's not immediately clear what min is doing here 
       } 
       //curNode is now the leftmost non-leaf element in the tree
       min = curNode.getMin();
       return min;

请注意，我所做的唯一更改是在 return 语句上方插入一行，该语句重新分配min给树中最左侧元素的最小值。

于 2014-07-29T01:49:59.667 回答
0

为了提高效率，请注意您不需要调用getNextChild(curNode, min)，因为 node 中的项目始终在 2-3-4 树中按升序排序，并且最小的项目始终位于 index 0。在开始时也不需要声明 min。所以你的程序可能是这样的：

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}
于 2016-04-07T09:35:15.280 回答