如何在二叉树中搜索一个节点并返回它？

Question

我正在尝试在二叉树中搜索一个节点并返回以防它存在，否则返回 null。顺便说一句，节点类有一个方法 name() 返回一个带有它的名字的字符串……我到目前为止是：

 private Node search(String name, Node node){

     if(node != null){
         if(node.name().equals(name)){
            return node;
         }

      else{
         search(name, node.left);
         search(name, node.right);
      }
    }
    return null;
}

这个对吗？？

原文由 besnico 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如果结果不为空，您需要确保对搜索的递归调用返回。

这样的事情应该工作…

 private Node search(String name, Node node){
    if(node != null){
        if(node.name().equals(name)){
           return node;
        } else {
            Node foundNode = search(name, node.left);
            if(foundNode == null) {
                foundNode = search(name, node.right);
            }
            return foundNode;
         }
    } else {
        return null;
    }
}

原文由 Tom Jefferys 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

public Node findNode(Node root, Node nodeToFind) {
    Node foundNode = null;
    Node traversingNode = root;

    if (traversingNode.data == nodeToFind.data) {
        foundNode = traversingNode;
        return foundNode;
    }

    if (nodeToFind.data < traversingNode.data
            && null != traversingNode.leftChild) {
        findNode(traversingNode.leftChild, nodeToFind);
    } else if (nodeToFind.data > traversingNode.data
            && null != traversingNode.rightChild) {
        findNode(traversingNode, nodeToFind);
    }

    return foundNode;

}

原文由 Puneet 发布，翻译遵循 CC BY-SA 3.0 许可协议