How do I use a binary search tree to find prefix matches?-CodePudding

I have the following code for a Binary Search Tree, where if someone enters the prefix of a book title followed by an asterix, a recursive method will print all of the titles in a text file that match the prefix. For instance, if someone enters Cor*, the program might return 'Coraline', 'Coral Reefs', and 'Corpse Bride' all on different lines.

The method I have written below does not return anything, and I would really appreciate if someone could help me figure out where I went wrong as I am new to both recursion and BSTs. My insert and search methods work fine, so I know that the error is in my booksPrefix method.

private void booksPrefix(Node root, String prefix) {
    while (root != null) {
        String rootLow = root.key.toLowerCase();
        String prefixLow = prefix.toLowerCase();
        //if current node starts with given prefix, print data
        if (rootLow.startsWith(prefixLow)) {
            System.out.println(root.data);
        }
        if (root.right != null) {
            booksPrefix(root.right, prefix);
        } if (root.left != null) {
            booksPrefix(root.left, prefix);
        }
    }
}

Here is the part of the Tester class that calls booksPrefix():

else if(search.indexOf('*') > 0)
        {
            //call prefix search
            System.out.println("[Finding all movies that start with "   search.split("\\*")[0]   "..]");
            bst.booksPrefix(search);
        }

CodePudding user response：

Your algorythme is broken. Here something better :

if (rootLow.startsWith(prefixLow)) {
    System.out.println(root.data);
} 
if (root.hasChildren()) {
    root.children.forEach(child -> booksPrefix(child, prefix));
}

CodePudding user response：

Try this.

public class Node {
    String key;
    Node left, right;

    Node(String key, Node left, Node right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }

    private void booksPrefix(Node node, String prefix, List<String> results) {
        if (node == null) return;
        String nodeLow = node.key.toLowerCase();
        String prefixLow = prefix.toLowerCase();
        if (nodeLow.startsWith(prefixLow)) results.add(node.key);
        booksPrefix(node.right, prefixLow, results);
        booksPrefix(node.left, prefixLow, results);
    }

    public List<String> booksPrefix(Node root, String prefix) {
        List<String> results = new ArrayList<>();
        booksPrefix(root, prefix, results);
        return results;
    }
}

And

Node root = new Node("Coraline",
    new Node("Coral Reefs",
        new Node("Apocalypse", null, null),
        new Node("CorpseBride", null, null)),
    new Node("Oddessy", null, null));
System.out.println(root.booksPrefix(root, "Cor"));

output:

[Coraline, Coral Reefs, CorpseBride]

CodePudding user response：

Keeping it nice and simple:

private void booksPrefix(Node node, String prefix) {
    if (node != null) {
        booksPrefix(node.left, prefix);
        if (node.key.toLowerCase().startsWith(prefix.toLowerCase()))
            System.out.println(node.data);
        booksPrefix(node.right, prefix);
    }
}