为什么我的二叉搜索树删除递归没有结束？

Question

我试图实现一个二叉查找树使用Java。我想创建的函数之一是删除函数。这将由两个方法组成，一个称为删除，另一个称为getNodeToDelete。getNodeToDelete方法是删除方法的辅助函数。

getNodeToDelete方法是递归的，基本上返回用户希望从树中删除的节点。使用此getNodeToDelete方法返回的节点，非递归删除方法基本上会根据不同情况（例如，它是叶节点还是根节点等）对如何删除此节点做出重要决定。

这是非递归删除方法：

 /**
     * Deletes the relevant node (according to the key inputted by the user), using two helper functions:
     * getNodeToDelete(int deleteKey, Node root) and getMinRight(Node nodeToDelete).
     * @param key
     */
    public void delete(int key) {
        if (root.left == null && root.right == null) {
            if (root.key == key) {
                root = null;
                System.out.println("It reached the first if-statement of the delete() method.");
            }
        }
        Node nodeToDelete = getNodeToDelete(key, root); //The node that is returned from its helper function.
        System.out.println("This is the node to delete: " + nodeToDelete.key);
        if (nodeToDelete.right == null && nodeToDelete.left == null) {  //If the nodeToDelete is a leaf.
            nodeToDelete = null;
//            System.out.println("This is the key of the deleted node: " + nodeToDelete.key);
            return;
        } else if (nodeToDelete.right == null) {  //If the nodeToDelete has an empty right tree.
            Node immediateLeftNode = nodeToDelete.left;
            nodeToDelete.key = immediateLeftNode.key;
            nodeToDelete.left = immediateLeftNode.left;
            nodeToDelete.right = immediateLeftNode.right;
        } else if (nodeToDelete.right != null) {  //If the nodeToDelete has a non-empty right tree
            if (nodeToDelete.right.left == null) {  //If the left branch of the right branch of nodeToDelete is empty.
                nodeToDelete.key = nodeToDelete.right.key;
                nodeToDelete.right = nodeToDelete.right.right;
            } else {
                Node replacementNode = getMinRight(nodeToDelete);
                nodeToDelete.key = replacementNode.key;
            }
        }
    }

这是递归的getNodeToDelete方法：

/**
     * Assumption: the key does exist in the tree.
     * Returns the node that the user wants to delete, based on the key that the user inputs.
     * @param deleteKey
     * @param startingRoot
     * @return
     */
    public Node getNodeToDelete(int deleteKey, Node startingRoot) {
        if (startingRoot == null) {
            return null;
        }

        if (startingRoot.key == deleteKey) {
            return startingRoot;
        }

        if (deleteKey < startingRoot.key) {
            getNodeToDelete(deleteKey, startingRoot.left);
        }

        getNodeToDelete(deleteKey, startingRoot.right);
        return startingRoot;
    }

问题是，helper函数getNodeToDelete沿着树向下遍历到它的一个节点，例如，值为-12的叶节点。然后返回该节点，但递归方法getNodeToDelete似乎没有结束。然后，它再次遍历回根节点，始终导致返回的值是根节点。

我知道在Java中实现二叉查找树有许多不同的方法，但是这个递归问题困扰着我，我真的很想知道失败背后的原因。

如果你需要更多的澄清，请告诉我。谢啦

Answer 1

有人在删除之前回答了我的问题，但他们的回答确实帮助我找到了解决方案。所以，不管是谁，谢谢你。

基本上，我的递归（在递归方法getNodeToDelete中）总是返回根节点，因为我没有返回递归的结果。因此，丢弃我想要的数据，而不是让它重现给我。这很难解释，但基本上，这是修复后的getNodeToDelete方法：

/**
     * Assumption: the key does exist in the tree.
     * Returns the node that the user wants to delete, based on the key that the user inputs.
     * @param deleteKey
     * @param startingRoot
     * @return
     */
    public List<List> getNodeToDelete(int deleteKey, Node startingRoot, Node parentNode, String directionFlag) {
        List<Node> nodes = new ArrayList<>();
        nodes.add(startingRoot);
        nodes.add(parentNode);

        List<List> nodeData = new ArrayList<>();
        nodeData.add(nodes);
        List<String> direction = new ArrayList<>();
        direction.add(directionFlag);

        nodeData.add(direction);

        if (startingRoot == null) {
            return null;
        }

        if (startingRoot.key == deleteKey) {
            System.out.println("This is node that is FINALLY RETURNED " + startingRoot.key);
            return nodeData;
        }

        if (deleteKey < startingRoot.key) {
            System.out.println("This is node that is returned " + startingRoot.key);
            return getNodeToDelete(deleteKey, startingRoot.left, startingRoot, "left"); //Added return statement here.
        }

        System.out.println("This is node that is returned " + startingRoot.key);
        return getNodeToDelete(deleteKey, startingRoot.right, startingRoot, "right");  //Added return statement here.
    }

除了我改变的其他几件事情，这是因为我的删除函数中的一些错误，让我的getNodeToDelete方法返回用户想要删除的节点，是通过在添加返回注释的地方添加返回语句以上代码片段中的语句。

对于我为什么忽略了递归背后的这一重要步骤，这仍然让我非常震惊，所以我需要更多地思考它。但是，基本上，这个故事的寓意是，确保从递归中实际返回结果，而不是简单地递归调用函数！