Использование рекурсивно возвращенной ссылки на узел в дереве не позволяет изменять сам узел

Question

Мой класс структур данных работает с деревьями. Мы реализуем трехмерное дерево, содержащее 2 значения со ссылкой на левый, средний и правый узлы (левое поддерево меньше значения 1, среднее поддерево между значением 1 и значением 2, правое поддерево больше значения 2). Для класса Tree был предоставлен интерфейс, а методы поиска, вставки и удаления должны быть рекурсивными. Клиентский код, который будет протестирован против, повторно использует метод вставки для создания дерева, а корень начинается с null.

Я пытаюсь вставить значения в дерево рекурсивно, найдя родительский узел в отдельном частном методе, а затем, при необходимости, изменив возвращаемый узел. В настоящее время проблема заключается в том, что метод возвращает исходный узел, который является корнем, и правильно создает новый узел со значением, поскольку корень равен нулю. Однако корень остается равным нулю.

Я уверен, что это связано с тем, как ссылки и ценности работают на Java (аналогично C#, как описано в this article by Jon Skeet); учитывая ограничения, как мне изменить это, чтобы разрешить вставки в дерево? Ниже приведен текущий метод вставки в древовидном классе, а также аналогичный закрытый метод.

public void insert(AnyType newData) 
{ 
    // If insert node is null, make a new node with newData as first key 
    TernaryNode<AnyType> insert_node = findNode(newData, root); 
    if (insert_node == null) 
    { 
     insert_node = new TernaryNode<AnyType>(newData); 
    } 
    else 
    { 
     // Get the key that is equal if the insert node is not null 
     if (insert_node.getKey1() == null) 
     { 
      insert_node.setKey1(newData); 
     } 
     else 
     { 
      insert_node.setKey2(newData); 
     } 
    }// end else 
}// end insert 

private TernaryNode<AnyType> findNode(AnyType item, TernaryNode<AnyType> node) 
{ 
    TernaryNode<AnyType> current_node = node; 
    if (current_node != null) 
    { 
     if (current_node.getKey1() != item && 
       current_node.getKey2() != item) 
     { 
      // Comparator checks left 
      if (compare.compare(current_node.getKey1(), item) <= -1) 
      { 
       return findNode(item, current_node.left); 
      } // Comparator checks right 
      else if (compare.compare(current_node.getKey2(), item) >= 1) 
      { 
       return findNode(item, current_node.right); 
      }// Comparator checks middle 
      else 
      { 
       return findNode(item, current_node.middle); 
      } 
     }// end while 
    }// end if 
    // Return current node even if it is null 
    return current_node; 
}// end findNode 

Answer 1

Если вы не назначая что-то к root члену, он никогда не приобретет значение. Вам, вероятно, нужен какой-то внешний контейнер для вашего дерева, подобно тому, как XML-документ (который также является деревом) имеет внешний объект Document, который отличается от фактического корневого узла документа.

Answer 2

TernaryNode<AnyType> insert_node = findNode(newData, root); 
    if (insert_node == null) 
    { 
      insert_node = new TernaryNode<AnyType>(newData); 
      root = insert_node; 
    }