完成前退出二进制前序遍历

Question

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

这是预序遍历回避函数，我在下面调用它：

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);
}
. . .

完成前退出二进制前序遍历

Exit binary pre order traversal before completion

java

binary-tree

preorder