计算 BST 中的插入次数

Question

我有一个 BST class 个字符串，它有一个名为 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

为您编写一个测试用例 class 并测试 class 是否正常运行。假设您的 class 名为 BST，您可以使用名为 'size()' 的方法访问实例变量 'numberOfInserts'，可以放置一个用于测试插入的简单测试用例（没有任何第 3 方库）在测试的主要方法中 class。类似于：

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

在此示例中，如果 class 行为不正常，将抛出异常。如果出现异常，您可以进入调试器（或使用 System.out.println）尝试调试应用程序。

计算 BST 中的插入次数

Count number of Insertions in BST

java

recursion

binary-search-tree