寻找 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.getMin 的最小值。getMin() 只是在索引 0 处获取数组中的值（其中应该保持最小值。那么，当当前节点不是叶子时，我们应该从最小值点遍历到下一个子节点。一旦当前节点是叶子，它应该返回最小值。

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

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

DataItem、Node、Tree234以及程序运行的地方Tree234App

Answer 1

首先，为了更快地获得更好的帮助，请发布一个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给树中最左侧元素所附加的最小值。