Количество отсчетов в BST

Question

У меня есть класс строк BST с глобальной переменной, называемый numInsertions, который подсчитывает количество вставок, которые я делаю в BST. Я не уверен, что это дает правильные результаты, как я не знаю рекурсии очень хорошо, пожалуйста, помогите мне проверить

public void insert(String key) 
    { 
    if(isEmpty()) 
    { 
     root = new Node(key); 
     numInsertions++; 
    } 
    else 
     numInsertions = 1+insert(key, root); 
    } 
    public int insert(String key, Node curr) 
    { 
    int result = 1; 
    if(key.compareTo(curr.getKey())<0) 
    { 
     if(curr.getLeftChild()==null) 
     { 
     Node newNode = new Node(key); 
     curr.setLeftChild(newNode); 
     } 
     else 
     result = result +insert(key,curr.getLeftChild()); 
    } 
    else 
    { 
     if(curr.getRightChild()==null) 
     { 
     Node newNode = new Node(key); 
     curr.setRightChild(newNode); 
     } 
     else 
     result = result +insert(key,curr.getRightChild()); 
    } 
    return result; 
    } 

Answer 1

написать тест для вас класса и теста, что класс ведет себя правильно. Предположим, что ваш класс называется BST, и вы можете получить доступ к переменной экземпляра 'numberOfInserts' с помощью метода с именем 'size()', простой тестовый пример для тестирования вставок (без каких-либо сторонних библиотек) можно поместить в основной метод вашего испытательный класс. Что-то вроде:

BST bst = new BST(); 
//test insertion of 100 items 
for (int i = 0; i < 100; i++){ 
    bst.insert(String.valueOf(i)); 
    if (bst.size() != i+1){ 
     throw new Exception("Invalid BST size " + bst.size()); 
    } 
} 

В этом примере исключение будет выбрано, если класс не ведет себя правильно. Если это неверно, вы можете войти в отладчик (или использовать System.out.println), чтобы попробовать и отладить приложение.