Метод вставки BinarySearchTree

Question

Я пытаюсь использовать рекурсивный для записи метод вставки для BST.

public void insert(DictEntry data) throws BSTException { 
    if (find(data.getPosition()) == data){ 
     throw new BSTException(); 
    } 
    else { 
     if (current == null){ 
      root.setRoot(data); 
    } 
     else { 
      while(current != null){ 
       if (data.getPosition().compareTo(root.getRoot().getPosition()) < 0){ 
        current = current.getLeft(); 
       } 
       else{ 
        if (data.getPosition().compareTo(root.getRoot().getPosition()) > 0){ 
         current = current.getRight(); 
        } 
        else 
         ; 
       } 
       insert(data); 
      } 
     } 

    } 
} 

Но я не знаю, почему по какой-либо причине тест всегда терпит неудачу. Может кто-нибудь помочь мне исправить это, пожалуйста?

Answer 1

Есть несколько проблем с этим кодом:

1. Вы перепутали рекурсивную реализацию с повторяющимся. При использовании рекурсии, как вы это делаете, вызывая «вставить (данные)» внутри функции «вставить», вам не нужен цикл «while»
2. Когда вы, наконец, попали в базовый регистр вашей рекурсии if (current == null){, вы вставляете в корень? Вы должны вставить в «токе», так как это суб дерева вы нашли, чтобы быть пустыми и соответствовать порядку
3. Вы всегда сравнить свои данные в «корне» вместо «текущих»

Дальнейших вопросов:

• Ваш код плохо отформатирован («}» после того, как первый «еще» должен быть отступ, «иначе,» ненужно)
• Вы используете рекурсию путем обновления переменной вне функции: " текущий". Это может сработать, но это плохой стиль. Ваш метод должен выглядеть public void insert(DictEntry data, BSTNode node), где вы начинаете с insert(data, root), а затем рекурсивный вызов insert(data, node.getLeft() или insert(data, node.getRight()