强制 return 进入 while 循环

Question

我正在写一个二叉树。在尝试删除具有两个子节点的节点时，我编写了一种方法来搜索右子分支的最左节点。

我收到一个奇怪的错误 - 在返回值之前，尽管不满足条件（标志为假），但我似乎再次进入了 while 循环。在while循环之后，它递归地调用自己并以一个空节点结束，因为它在树中走得太远了。

谁能告诉我为什么会这样？

protected Key rlmost (BSTreeNode node){

    BSTreeNode leafnode = null;

    if ((node.right!=null)&&(node.left!=null)&&(flag==false)){
        flag = true; // set flag to true
        System.out.println("left node" + node.left.kvPair.key);
        rlmost(node.left);
        System.out.println();
    }

    while (flag==true){
        if (node.right != null){
        System.out.println("right node" + node.right.kvPair.key);
        rlmost(node.right);
        }

        else {
            leafnode = node; 
            System.out.println("rlmost node" + leafnode.kvPair.key);
            flag = false;
        }

    }


    return leafnode.kvPair.key;
}

Answer 1

我认为问题出在你的递归上。让我们假设一个非常简单的结构。没有左或右的节点（均为空）。

首先，叶节点一开始是空的。鉴于结构，我们不能进入 if 块。鉴于 flag==false，我们不能进入 while 循环。因此，当您 return.

时，您将获得 NPE

如果我们让它更复杂一些，有一个节点有左节点和右节点，但没有孙子节点，我们会遇到同样的问题。

您将遇到第一个 if 块。您使用 flag == true 进行递归，但是将递归的结果扔到左边。在第一次递归调用时，您不能进入第一个 if 块。您将进入 while 循环，然后进入 else 块。 leafnode 被设置为一个节点。您将 return 返回到第一个调用（在 if 块中）。此时 leafnode 仍为 null。繁荣，NPE。

如何初始化叶节点由您决定。您应该将其设置为 rlmost 的递归调用。

强制 return 进入 while 循环

Forced to return into while loop

java

binary-tree

while-loop