查找2-3-4树的最小值

Question

首先，这个问题不是家庭作业。我目前正在阅读Robert Lafore的"数据结构和算法第2版"一书。在第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的min值。盖明。getMin()只是获取索引0处数组的值（其中应保留最低值）。然后，当当前节点不是叶子时，我们应该从最小点遍历到下一个子节点。一旦当前节点是叶子，它应该返回最小值。

但这是行不通的。有没有人对如何实现这个想法？提示或建议或其他什么？

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

数据资料, 节点, 树234, ，以及程序运行的位置, 树234app

Answer 1

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

其次，您需要详细说明"这不起作用"的含义-即确切地告诉我们它在做什么或不做什么是出乎意料的。为了代替你这样做，我们怎么能确切地告诉你为什么这样做呢？

然而，有一件事跳出来:你在实例化 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 到附加到树中最左边元素的最小值。

Answer 2

为了提高效率，请注意，您不需要调用 getNextChild(curNode, min), ，因为节点中的项目总是在2-3-4树中按升序排序，而最小的项目总是在索引处 0.在开始时也没有必要声明min。所以你的程序可能是这样的:

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}