java - 使用递归查找在二叉树中保存给定字符串的节点

我有使用递归的方法来查找在二进制树中保存指定的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;
}

任何可能是问题的见解将不胜感激。

最佳答案

我建议考虑tail recursions，因为从性能角度来看，这是一个主要因素:

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

附加的是在an online compiler上执行的完整代码:

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

关于java - 使用递归查找在二叉树中保存给定字符串的节点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49961695/