如何在二叉搜索树中按首字母检索字符串？附现有搜索代码

Hey there! Since you're new to programming and already have a full-name search working for your binary search tree (BST), let's walk through how to tweak this to search by the first character of a name. I'll break this down into easy-to-follow steps that fit with your existing code:

If your BST is organized by dictionary order (the natural sort order of strings), this makes first-character searches way simpler. All names starting with 'L' will sit in a continuous range: they'll come right after all names starting with letters before 'L', and right before those starting with letters after 'L'.

Your current searchByName method looks for exact full-name matches. We'll adjust this to collect all names where the first character matches your target. Here are two solid approaches:

Approach A: Full tree traversal (simple, no ordering dependency) #

If your BST isn't sorted by name, or you want a straightforward solution that works regardless, you can do a full traversal of the tree and collect every node where the first character matches your target. An in-order traversal is ideal here since it will return names in sorted order.

First, add a helper method to collect matches:

private void collectByFirstChar(Node current, char target, List<String> results) {
    if (current == null) return;
    
    // Traverse left subtree first
    collectByFirstChar(current.left, target, results);
    
    // Check if current node's name starts with the target character
    if (Character.toUpperCase(current.name.charAt(0)) == target) {
        results.add(current.name);
    }
    
    // Traverse right subtree next
    collectByFirstChar(current.right, target, results);
}

Then update your searchByName method to use this helper:

public void searchByName() throws IOException {
    boolean end = false; // Pro tip: use lowercase booleans for Java conventions!
    Scanner scanner = new Scanner(System.in); // Initialize scanner once instead of inside the loop
    
    while (!end) {
        System.out.print("Enter a starting character to search (or 'exit' to quit): ");
        String input = scanner.nextLine().trim();
        
        if (input.equalsIgnoreCase("exit")) {
            end = true;
            continue;
        }
        
        if (input.length() != 1) {
            System.out.println("Oops, please enter a single character!");
            continue;
        }
        
        char target = Character.toUpperCase(input.charAt(0)); // Normalize to uppercase for case-insensitive search
        List<String> matches = new ArrayList<>();
        collectByFirstChar(root, target, matches);
        
        if (matches.isEmpty()) {
            System.out.println("No names found starting with '" + target + "'");
        } else {
            System.out.println("Names starting with '" + target + "':");
            for (String name : matches) {
                System.out.println("- " + name);
            }
        }
    }
    scanner.close(); // Don't forget to close the scanner!
}

Approach B: Optimized search using BST ordering (faster for large trees) #

If your BST is sorted by name dictionary order, you can skip traversing irrelevant parts of the tree. Here's how:

1. Find the first node where the name starts with your target character
2. Collect all subsequent nodes that also start with the target (since sorted BST will group these together)

Here's a helper method for this optimized approach:

private void findMatchingNames(Node current, char target, List<String> results) {
    if (current == null) return;
    
    // If current node's first char is less than target, only check right subtree
    if (Character.toUpperCase(current.name.charAt(0)) < target) {
        findMatchingNames(current.right, target, results);
        return;
    }
    
    // If current node's first char is greater than target, only check left subtree
    if (Character.toUpperCase(current.name.charAt(0)) > target) {
        findMatchingNames(current.left, target, results);
        return;
    }
    
    // We found a match! Add it, then check both subtrees for more matches
    results.add(current.name);
    findMatchingNames(current.left, target, results);
    findMatchingNames(current.right, target, results);
}

Just replace the collectByFirstChar call in your searchByName method with findMatchingNames to use this faster approach.

• Case insensitivity: Always normalize both the input character and the name's first character to the same case (uppercase or lowercase) so 'l' and 'L' return the same results.
• Empty tree: Make sure your helper methods handle current == null gracefully to avoid null pointer exceptions.
• No matches: Your code should clearly inform the user when no names match their search.

Try these scenarios to make sure everything works:

• Search for a character with multiple matching names
• Search for a character with no matches
• Test lowercase and uppercase inputs
• Test with an empty tree

内容的提问来源于stack exchange，提问作者Marty