在 AVL 树的删除方法中使用 NoSuchElementException 时遇到问题

Question

我正在尝试创建一个删除方法，从 AVL 树中删除节点。但是测试我的代码的程序给我一个错误，说我没有正确使用 NoSuchElementException。

这是我的删除方法（和removeRecursive 方法）的代码。

    public T remove(T data) {
        // Base case: if data is null, throw an exception
      if (data == null) {
         throw new IllegalArgumentException("Error: data cannot be null.");
      }
   
        // Recursive helper method for removing data from the tree
      AVLNode<T> removedNode = removeRecursive(root, data);
   
        // If the node is not found, throw NoSuchElementException
      if (removedNode == null) {
         throw new NoSuchElementException("Error: data not found in the tree.");
      }
   
        // Update the root after removal
      root = removedNode;
   
      return removedNode.getData();
   }
   
   private AVLNode<T> removeRecursive(AVLNode<T> current, T data) {
      if (current == null) {
         return null; // Data not found
      }
   
      // Compare data with the current node's data
      int compareResult = data.compareTo(current.getData());
   
      if (compareResult < 0) {
        // Data is smaller, go to the left subtree
         current.setLeft(removeRecursive(current.getLeft(), data));
      } else if (compareResult > 0) {
        // Data is larger, go to the right subtree
         current.setRight(removeRecursive(current.getRight(), data));
      } else {
        // Node with data found, perform removal based on cases
      
         if (current.getLeft() == null && current.getRight() == null) {
            // Case 1: Node is a leaf (no children)
            size--;
            return null;
         } else if (current.getLeft() != null && current.getRight() != null) {
            // Case 3: Node has two children
            // Replace the data with the successor's data
            AVLNode<T> successor = findSuccessor(current.getRight());
            current.setData(successor.getData());
            // Remove the successor node
            current.setRight(removeRecursive(current.getRight(), successor.getData()));
         } else {
            // Case 2: Node has one child
            size--;
            return (current.getLeft() != null) ? current.getLeft() : current.getRight();
         }
      }
   
      // Update height and balance factor, then balance the tree
      return balance(current);
   }

这是它给我的错误：

[测试失败：删除]：尝试删除不在树中的数据时不会引发 NoSuchElementException。

我很困惑，因为在检查removedNode是否为空时抛出NoSuchElementException。那么为什么说它没有被抛出呢？谢谢。

不知道还可以尝试什么。另外，我已经尝试过调试该程序，但它仍然说同样的事情。

Answer 1

问题在于，当

removeRecursive

找不到数据时，它只是在最深的递归级别返回

null

。递归树中上一层的调用者（也是

removeRecursive

）只需将

null

分配给

current

节点的左子节点或右子节点并返回

current

。因此

null

值通常不会“冒泡”回原始调用者 (

remove

)。相反，调用者将只返回

balance(current)

返回的内容，并且其调用者将执行相同的操作，...一直沿递归树向上，直到最终返回根节点（平衡因子没有变化）。

所以当没有找到数据时，

remove

不会得到

null

作为返回值。

实用的解决方案是从

null

中删除

remove

检查，而改为 在

NoSuchElementException

的基本情况下抛出

removeRecursive

，而不是在那里返回

null

。