Нахождение минимального значения дерева 2-3-4

Question

Во-первых, этот вопрос не является домашним заданием.Сейчас я читаю книгу Роберта Лафора "Структуры данных и алгоритмы, 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

Элемент данных, Узел, Дерево 234, и где выполняется программа, Tree234App

Answer 1

Во-первых, чтобы быстрее получить лучшую помощь, опубликуйте SSCCE это дает нам минимальную реализацию всей вашей программы - то, что мы можем скопировать в нашу собственную среду 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 к минимальному значению, привязанному к самому левому элементу в дереве.

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();
}