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

Question

我正在尝试使用 Java 实现二叉搜索树。我要创建的功能之一是删除功能。这将包含两种方法，一种称为 delete，另一种称为 getNodeToDelete。 getNodeToDelete 方法是 delete 方法的辅助函数。

getNodeToDelete方法是递归的，基本上returns用户要从树中删除的节点。使用从这个 getNodeToDelete 方法返回的节点，非递归 delete 方法基本上根据不同的不同做出关于如何删除这个节点的重要决定情况（例如它是叶节点，它是根节点等）。

这是非递归的delete方法：

 /**
     * 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;
    }

问题是，辅助函数 getNodeToDelete 向下遍历树到其节点之一，例如，值为 -12 的叶节点。然后就是returns那个节点，但是递归的方法getNodeToDelete好像没有结束。然后它再次遍历回到根节点，总是导致返回值是根节点。

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

如果您需要更多说明，请告诉我。谢谢

Answer 1

有人在删除问题之前回答了我的问题，但他们的回答无疑帮助我找到了解决方案。所以，谢谢你。

基本上，我的递归（在递归方法中，getNodeToDelete）总是 returning 我的根节点，因为我没有 returning递归的结果。因此，丢弃我想要的数据而不是让它重新回到我身边。这很难解释，但基本上，这是修复后的 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.
    }

除了因为我的 delete 函数中的一些错误而改变的其他一些东西，允许我的 getNodeToDelete 方法 return 用户想要删除的节点，是通过在用 注释的地方添加 return 语句在此处添加 return 语句 在上面的代码片段中。

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

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

Why Is My Binary Search Tree Delete Recursion Not Ending?

java

recursion

binary-search-tree