java - 在完成之前退出二进制前序遍历

Question

我有一个由各种节点组成的二叉树。我想使用前序递归遍历树，找到一个具有匹配描述（desc）的节点，如果存在则返回它。然而，遍历继续完成。我犯了一个逻辑错误，还是遍历算法不合适？

这是前序遍历recusion函数，我在下面调用它：

public Node replaceNodes(Node currentNode, int itemId, String desc) {

if (currentNode == null) {
    System.out.println("null");
}

if (currentNode != null) {
    //System.out.println(desc + " " + currentNode.getDesc());
    if (currentNode.getDesc().matches(desc) 
            && currentNode.getKey() != itemId) {
        System.out.println("returned");
        return currentNode;
        //System.out.println(currentNode.getDesc());
    } else {
        replaceNodes(currentNode.leftChild, itemId, desc);
        replaceNodes(currentNode.rightChild, itemId, desc);
        //System.out.println("replace");
    }
} 

return null;
}


  Node replaceItem = r1Items.replaceNodes(r1Items.
                            getRoot(), searchId, searchNode.getDesc());
                    //check suitable item found

谢谢。如果需要，我很乐意进一步澄清。

Answer 1

您递归地调用您的方法，但您没有存储从递归调用返回的值。目前，只有当您要查找的节点是根节点时，您才会得到正确的结果。

我认为您希望在 else 语句中具有以下内容。

. . . 
} else {
   Node left = replaceNodes(currentNode.leftChild, itemId, desc);
   if(left != null) { return left; }
   Node right = replaceNodes(currentNode.rightChild, itemId, desc);
   if(right != null) { return right; }
}
. . . 

下面稍微简化一下

. . . 
} else {
   Node left = replaceNodes(currentNode.leftChild, itemId, desc);
   if(left != null) { return left; }
   return replaceNodes(currentNode.rightChild, itemId, desc);
}
. . .