使用递归在二叉树中查找包含给定字符串的节点

Question

我有一个使用递归来查找二叉树中包含指定String的节点的方法。问题在于，当它应该返回包含指定名称的节点时，它返回了null，而我不知道原因。

这是方法：

public Node getNode(Node currentNode, String name) { 
    Node retrieved = null;
    if (currentNode.getName().equals(name)) { retrieved = currentNode; }
    else 
    {
        if (currentNode.right != null) {
            getNode(currentNode.right, name);
        } 
        if (currentNode.left != null) {
            getNode(currentNode.left, name);
        }
    }
    return retrieved;
}

如果有任何关于问题的见解，将不胜感激。

- user6246171

---

你不觉得你需要递归调用的返回值吗？为了某些事情？ - Andreas

Answer 1

你需要捕获两个递归调用的返回值。否则你就是在白白地进行递归，并且扔掉了递归的结果。

public Node getNode(Node currentNode, String name){ 
    Node retrieved = null;
    if (currentNode.getName().equals(name)) { retrieved = currentNode; }
    else 
    {
        if (currentNode.right != null){
            retrieved = getNode(currentNode.right, name);
        } 
        if (retrieved == null && currentNode.left != null){
            retrieved = getNode(currentNode.left, name);
        }
    }
    return retrieved;
}

以下解决方案在风格上可能更好，因为您将null检查留给了基本情况。请注意，您不再需要检查currentNode.right != null或currentNode.left != null，因为它们在经过一次递归后被基本情况所覆盖。

public static Node getNode(Node currentNode, String name){
    // Base case: currentNode is null, nothing left to search
    if (currentNode == null) {
        return null;
    }

    Node retrieved = null;
    if (currentNode.getName().equals(name)) {
        retrieved = currentNode;
    } else {
        // Try to search right subtree
        retrieved = getNode(currentNode.right, name);

        // If not found in right subtree, then search left subtree
        if (retrieved == null){
            retrieved = getNode(currentNode.left, name);
        }
    }
    return retrieved;
}

- k_ssb

---

这段代码将会因为空指针异常而崩溃。你能看出为什么会发生吗？ - Tim Biegeleisen

请勿在帖子中使用“编辑：”块：https://meta.stackexchange.com/questions/127639/when-is-edit-update-appropriate-in-a-post - Neuron

@pkpnd 谢谢。虽然我会争辩第二个解决方案是否比第一个更好，但为什么不删除第一个呢？ - Neuron

因为第一种解决方案对OP更有帮助（从意义上讲，它更类似于他们现有的方法）。在学习时，先看到“最小”的修复方案比尝试理解更高级的修复方案更有帮助。 - k_ssb

修复比一行代码稍微复杂一些。请注意，您必须在以下if语句中添加一个检查retrieved == null。因此，在我看来，最好提供整个解决方案以获得上下文和清晰度。 - k_ssb

Answer 2

解决方案

getNode(currentNode.right, name);

你调用了 getNode(...) 方法，但你没有对其进行任何操作。

更好的解决方案

如果你愿意使用 Google 的 Guava（在我看来每个项目都必须拥有）和 Java 8，你可以采取以下方法：

public static final Traverser<Node> TREE_TRAVERSER = 
        Traverser.forTree((SuccessorsFunction<Node>) node ->
                Stream.of(node.right, node.left)
                        .filter(Objects::nonNull)
                        .collect(Collectors.toList()));

然后在需要遍历树的任何位置调用它：

for (Node n : TREE_TRAVERSER.depthFirstPreOrder(root)) {
    if (n.getName().equals("foo")) {
        // todo: do stuff with node foo
    }
}

Java 8遍历树的方式如下：

Iterable<Node> nodes = TREE_TRAVERSER.depthFirstPreOrder(root);
Optional<Node> result = StreamSupport.stream(nodes.spliterator(), false)
        .filter(n -> n.getName().equals("foo")) // find node with name "foo"
        .findAny(); // we assume there is <= 1 node, so we take any.
// node.isPresent() to check if you found a Node and result.get() to get the Node

---

这是怎么回事？

嗯，Guava有一个很好的类叫做Traverser<N>。你只需要给它一个参数，即SuccessorsFunction<N>。它接受任何对象N并返回一个Iterable<? extends N>，这些是子节点。

我们使用Stream来实现这一点。首先，我们创建一个包含两个子节点的Stream。然后我们对它们进行过滤，只保留nonNull Node的Stream，并将它们收集到一个List中（因为SuccessorsFunction<Node>想要返回一个Iterable<Node>）。

这个Traverser<N>只需要被创建一次，所以我们把它做成了public static final。现在你可以选择一个迭代顺序。我们选择了depthFirstPreOrder，它返回一个能够迭代的Iterable<N>。

---

如果您之前没有听说过“流(Stream)”，我建议您参考这篇教程。

- Neuron

---

写得很好的回答！（+！） - Rann Lifshitz

@KamilTomaszJarmusik 你为什么这么想？ - Neuron

@KamilTomaszJarmusik 不，SuccessorsFunction<Node> 只接受一个节点并返回它的后继节点。如果它将自身作为后继节点返回，则会得到一个图而不是树。正如 Iterable<N> breadthFirst(N startNode) 所指出的那样：如果图中存在循环，则遍历不会终止。 - Neuron

如果我正确理解了作者的意图，一般情况是：(1) "否"和(2) "是"，都不会起作用，但是如果你将节点对象转换为非递归形式，就可以使用forGraph()。(来自Java文档) - Kamil Tomasz Jarmusik

对于（Node n：TREE_TRAVERSER.depthFirstPreOrder（root））的循环，结构在迭代期间是不可修改的，因此必须加载完整结构？请原谅我的好奇心，我要检查一下我的知识和直觉。 - Kamil Tomasz Jarmusik

Answer 3

我建议考虑尾递归，因为从性能角度来看，这是一个重要因素：

public static Node getNode(Node currentNode, String name){
    // Base case: currentNode is null, nothing left to search
    if (currentNode == null) {
        return null;
    }

    Node retrieved = null;
    if (currentNode.name.equals(name)) {
        return currentNode;
    } else {
        // Tail recursions
        if(currentNode.left == null) {
            return getNode(currentNode.right, name);
        }
        else if(currentNode.right == null) {
            return getNode(currentNode.left, name);
        }
        // Non Tail recursion
        else {
        retrieved = getNode(currentNode.left, name);

            // If not found in left subtree, then search right subtree
            if (retrieved == null){
                retrieved = getNode(currentNode.right, name);
            }
        }
    }
    return retrieved;
}

附上完整的代码，该代码已在在线编译器上执行：

public class MyClass {
    static class Node {
    public String name;
    public Node left;
    public Node right;

    Node(String name) {
        this.name = name;
        right = null;
        left = null;
    }

    @Override
    public String toString() {
        return "name = " + name + " hasLeft = " + (left != null) + " hasRight = " + (right != null);
    }

}

static class Tree {

    Node root;

    public Node getRoot() {
        return root;
    }

    private Node addRecursive(Node current, String value) {
    if (current == null) {
        return new Node(value);
    }

    if (value.compareTo(current.name) < 0) {
        current.left = addRecursive(current.left, value);
    } else if (value.compareTo(current.name) > 0) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
    }

    public Tree add(String value) {
        root = addRecursive(root, value);
        return this;
    }

    public void traverseInOrder(Node node) {
        if (node != null) {
            traverseInOrder(node.left);
            System.out.print(" " + node.name);
            traverseInOrder(node.right);
        }
    }

    public void traverseInOrder() {
        traverseInOrder(root);
         System.out.println("");
    }

}

public static void main(String args[]) {
    Tree tree = new Tree();
    tree.add("a").add("ab").add("bbb").add("cc").add("zolko").add("polip").traverseInOrder();

    Node found = getNode(tree.getRoot(),"vv");
    System.out.println(found);
    found = getNode(tree.getRoot(),"ab");
    System.out.println(found);
    found = getNode(tree.getRoot(),"polip");
    System.out.println(found);
    found = getNode(tree.getRoot(),"java");
    System.out.println(found);
    found = getNode(tree.getRoot(),"zolko");
    System.out.println(found);

}

public static Node getNode(Node currentNode, String name){
    // Base case: currentNode is null, nothing left to search
    if (currentNode == null) {
        return null;
    }

    Node retrieved = null;
    if (currentNode.name.equals(name)) {
        return currentNode;
    } else {
        // Tail recursions
        if(currentNode.left == null) {
            return getNode(currentNode.right, name);
        }
        else if(currentNode.right == null) {
            return getNode(currentNode.left, name);
        }
        // Non Tail recursion
        else {
        retrieved = getNode(currentNode.left, name);

            // If not found in left subtree, then search right subtree
            if (retrieved == null){
                retrieved = getNode(currentNode.right, name);
            }
        }
    }
    return retrieved;
}
}

主方法执行的输出：

 a ab bbb cc polip zolko
null
name = ab hasLeft = false hasRight = true
name = polip hasLeft = false hasRight = false
null
name = zolko hasLeft = true hasRight = false

- Rann Lifshitz