如何给Java二叉树节点添加名称并实现BFS路径查询

Hey there! Let's tackle your two main questions one by one—adding node names without hardcoding, and implementing BFS to find the path to the node with value 288.

1. Adding Node Names (No Hardcoding Needed) #

The tutorial you looked at uses named nodes, but your current btNode class only has an integer data field. Here's a clean, automated way to add unique names to each node so you don't have to manually assign them every time:

Step 1: Modify the btNode Class #

Add a name field, plus a static counter to generate unique names automatically. We'll also fix a small typo (visted → visited) to avoid bugs later:

package cs351_uninformed_search;

public class btNode {
    btNode left, right;
    int data;
    boolean visited;
    private String name;
    private static int nodeCounter = 1; // Static counter for unique names

    /* Constructor */
    public btNode() {
        left = null;
        right = null;
        data = 0;
        visited = false;
        this.name = "Node-" + nodeCounter++; // Auto-generate unique name
    }

    /* Constructor */
    public btNode(int n) {
        left = null;
        right = null;
        data = n;
        visited = false;
        this.name = "Node-" + nodeCounter++; // Auto-generate unique name
    }

    // Existing getters/setters for left, right, data...

    /* New getter for name */
    public String getName() {
        return name;
    }

    /* Optional setter if you want to override the auto-generated name */
    public void setName(String name) {
        this.name = name;
    }

    // Fixed typo in these methods
    public void setVisited() {
        visited = false;
    }

    public boolean isVisited() {
        return visited;
    }
}

How This Works #

• The static nodeCounter increments every time a new btNode is created, so each node gets a unique label like Node-1, Node-2, etc.
• If you ever want to rename a specific node (e.g., call the target node "Target-288"), you can use setName() later to override the auto-generated label.
• You don't need to change your existing insert method—this naming happens automatically when nodes are created.

2. Implementing BFS to Find the Path to Value 288 #

BFS is perfect for finding the shortest path in an unweighted tree, but to track the path from root to target, we need to keep track of each node's parent. Here's how to build this in your binaryTree class:

Step 1: Add the BFS Path Method to binaryTree #

package cs351_uninformed_search;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.HashMap;
import java.util.Collections;

public class binaryTree {
    protected btNode root;
    btNode startNode;
    btNode goalNode;

    /* Constructor */
    public binaryTree() {
        root = null;
    }

    // Existing methods (isEmpty, insert)...

    /* Method to find path from root to node with target data using BFS */
    public ArrayList<btNode> bfsFindPath(int targetData) {
        if (root == null) return null;

        Queue<btNode> queue = new LinkedList<>();
        Map<btNode, btNode> parentMap = new HashMap<>(); // Tracks each node's parent
        boolean found = false;
        btNode targetNode = null;

        queue.add(root);
        parentMap.put(root, null); // Root has no parent

        while (!queue.isEmpty()) {
            btNode current = queue.poll();

            // Check if current node is the target
            if (current.getData() == targetData) {
                targetNode = current;
                found = true;
                break;
            }

            // Enqueue left child if it exists
            if (current.getLeft() != null) {
                parentMap.put(current.getLeft(), current);
                queue.add(current.getLeft());
            }

            // Enqueue right child if it exists
            if (current.getRight() != null) {
                parentMap.put(current.getRight(), current);
                queue.add(current.getRight());
            }
        }

        // Build path by backtracking from target to root
        if (found) {
            ArrayList<btNode> path = new ArrayList<>();
            btNode current = targetNode;
            while (current != null) {
                path.add(current);
                current = parentMap.get(current);
            }
            Collections.reverse(path); // Reverse to get root-to-target order
            return path;
        } else {
            return null; // Target node not found
        }
    }
}

Step 2: Test the BFS Path in test.java #

Update your main method to call the new bfsFindPath method and print the path (including node names):

package cs351_uninformed_search;

import java.util.Random;
import java.util.ArrayList;

public class test {
    public static void main(String[] args) {
        /* Creating object of BST */
        binaryTree bst = new binaryTree();
        System.out.println("Binary Search Tree Test\n");
        int flag = 0;
        Random r = new Random(100);
        while (flag < 20) {
            bst.insert(r.nextInt(500));
            flag++;
        }
        BTreePrinter.printNode(bst.root);
        System.out.println("Hello from CS351: This is the first programming assignment!");
        System.out.println("You will practice the uninformed search algorithm");
        System.out.println("The goal of you is to find node with value 288 and print the path from root to it");
        System.out.println("Warm up your JAVA ^^");

        // Test BFS Path
        System.out.println("\n=== Task 1: BFS Path to 288 ===");
        ArrayList<btNode> bfsPath = bst.bfsFindPath(288);
        if (bfsPath != null) {
            System.out.print("Path from root to 288: ");
            for (int i = 0; i < bfsPath.size(); i++) {
                btNode node = bfsPath.get(i);
                System.out.print(node.getData() + " (" + node.getName() + ")");
                if (i != bfsPath.size() - 1) {
                    System.out.print(" → ");
                }
            }
            System.out.println();
        } else {
            System.out.println("Node with value 288 not found in the tree!");
        }

        // You can add DFS implementation similarly later
        System.out.println("\nTask 2: Please use the DFS to find the path. You should implement the method in binaryTree.java class, and test the method in test.java class");
    }
}

How the BFS Path Works #

1. We use a Queue to process nodes level by level (standard BFS behavior).
2. A HashMap (parentMap) records which node is the parent of each node—this lets us trace back from the target to the root once we find it.
3. Once the target is found, we traverse backwards from the target to the root using the parent map, then reverse the list to get the path in root-to-target order.
4. We print both the node's data and its auto-generated name, so you can reference nodes just like the tutorial does.

Bonus: Quick DFS Tip #

For Task 2, you can implement DFS using a similar parent map approach, or track the current path recursively. When you find the target node, return the current path (or reverse it if needed) to get the root-to-target route.

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