Finding parent nodes in a general tree: Implementation Guide based on breadth-first traversal

This tutorial details how to find the parent node of a specified node in a general tree data structure. We will use the Broadness-first traversal (BFS) algorithm to systematically explore the nodes of the tree layer by layer, and efficiently locate the parent of the target node. The article will cover node structure definition, BFS algorithm principles, Java code implementation, time and space complexity analysis, and related precautions to help readers master this core tree operation skills.

1. General tree node structure definition

First, we define the node structure of the general tree. A common tree node usually contains a key for identification, and a child node list, because each node of a common tree can have any number of child nodes.

 import java.util.ArrayList;

public class Node {
    int key; // Node key value ArrayList<node> children = new ArrayList(); // Store the list of child nodes/**
     * Determine whether the current node has child nodes.
     * Although not used directly in the logic of finding parent nodes, it helps to understand node characteristics.
     * @return Return true if there are children, otherwise return false.
     */
    public boolean hasChildren(){
        return !children.isEmpty(); // A more concise way of judgment}
}</node>

2. Find parent node: Broaden-first traversal (BFS) principle

To find the parent node of a node with a specified key value (token), we can use the Breadth-First Search (BFS) algorithm. BFS is an algorithm that explores tree or graph layer by layer, which is ideal for solving problems that need to find the nearest relationship or the shortest path, such as finding the parent node.

Core idea of ​​the algorithm: BFS uses queues (Queues) to manage nodes to be accessed. It starts with the root node, first accesses all the child nodes of the current node, then adds these child nodes to the queue, and then takes the next node from the queue for the same operation until the queue is empty or the target is found.

In a scenario where we look up a parent node, when we take a node p (as a potential parent) from the queue, we will iterate through all its child nodes c. If we find that the key value of a child node c matches the token we are looking for, then the current p is the parent node of our target node, and we can return p immediately. If c does not match, we queue c so that it can be checked as a potential parent in subsequent iterations.

3. Java implementation

The following is the Java implementation code based on the above principle:

 import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class TreeOperations {

    /**
     * Find the parent node of the specified key-value node in the general tree.
     * Implemented using Broadness-first traversal (BFS).
     *
     * @param root tree root node.
     * @param token The key value of the child node to be found.
     * @return If found, return the parent node of the target node; if not found or the target node is the root node (no parent node), return null.
     */
    public static Node findParent(Node root, int token) {
        // If the tree is empty or the root node is empty, return null directly
        if (root == null) {
            return null;
        }

        // Use LinkedList as the implementation of Queue Queue<node> queue = new LinkedList();
        queue.add(root); // Add the root node to the queue as the starting point of the traversal // Breadth priority traversal while (!queue.isEmpty()) {
            Node currentNode = queue.poll(); // Take the current node from the queue, it will serve as a potential parent node // traverse all children of the current node for (Node child : currentNode.children) {
                // If the key value of the child node matches the target token if (child.key == token) {
                    return currentNode; // Found, the current node is the parent node of the target node}
                // If the child node does not match, add it to the queue so that it can be checked as a potential parent node later queue.add(child);
            }
        }

        // After traversing all nodes, it still has not been found, indicating that the target node does not exist or it is the root node (no parent node)
        return null;
    }

    public static void main(String[] args) {
        // Build a sample generic tree // 1
        // /|\
        // 2 3 4
        // / \ \
        // 5 6 7
        Node root = new Node();
        root.key = 1;

        Node node2 = new Node(); node2.key = 2;
        Node node3 = new Node(); node3.key = 3;
        Node node4 = new Node(); node4.key = 4;
        root.children.add(node2);
        root.children.add(node3);
        root.children.add(node4);

        Node node5 = new Node(); node5.key = 5;
        Node node6 = new Node(); node6.key = 6;
        node2.children.add(node5);
        node2.children.add(node6);

        Node node7 = new Node(); node7.key = 7;
        node4.children.add(node7);

        // Test to find Node parentOf6 = findParent(root, 6);
        if (parentOf6 != null) {
            System.out.println("The parent node of node 6 is: " parentOf6.key); // Expected output 2
        } else {
            System.out.println("Not found parent node 6.");
        }

        Node parentOf7 = findParent(root, 7);
        if (parentOf7 != null) {
            System.out.println("The parent node of node 7 is: " parentOf7.key); // Expected output 4
        } else {
            System.out.println("Not found parent node of node 7.");
        }

        Node parentOf1 = findParent(root, 1); // The root node has no parent node if (parentOf1 != null) {
            System.out.println("The parent node of node 1 is: " parentOf1.key);
        } else {
            System.out.println("Not found parent node (or it is the root node)."); // The expected output is not found...
        }

        Node parentOf99 = findParent(root, 99); // Node that does not exist if (parentOf99 != null) {
            System.out.println("The parent node of node 99 is: " parentOf99.key);
        } else {
            System.out.println("Not found parent node of node 99."); // The expected output is not found...
        }
    }
}</node>

4. Complexity analysis

• Time complexity: O(N), where N is the total number of nodes in the tree. In the worst case, we need to access all nodes in the tree to find the parent node of the target node (e.g., the target node is the last leaf node to be accessed, or the target node does not exist). Each node is accessed at most once (enter once, dequeue once).
• Space complexity: O(W), where W is the maximum width of the tree (i.e. the maximum number of nodes in any layer). In the worst case, for example, a complete binary tree, the number of nodes in the last layer is close to N/2, and at this time, close to N/2 nodes may be stored in the queue. For a perfectly balanced tree with a height of H, the spatial complexity is O(N). In extreme cases (for example, a flat tree with only one layer and containing all child nodes), the spatial complexity is also O(N).

5. Precautions and summary

• Parent node of root node: The root node has no parent node. If token happens to be the key value of the root node, the findParent function will return null, which is logical.
• The target node does not exist: if there is no node matching the token in the tree, the function will also return null.
• Advantages of BFS: For problems such as finding parent nodes that require traversing all possible paths, BFS can ensure that we discover nodes in hierarchical order and return immediately when the first match is found, which is more efficient.
• Choice of recursion and iteration: Although some tree traversal problems often adopt recursion (such as depth-first traversal DFS), for problems such as finding parent nodes, breadth-first traversal (BFS) is usually more intuitive and efficient by iterating and coordinating queues. When the currentNode is processed as a potential parent node, if its child matches the token, then the currentNode is immediately its parent node. This hierarchical relationship is naturally reflected in BFS. It is more complicated to directly use recursion (DFS) to find the parent node, and may require additional parameters to pass the parent node information or return a result containing a parent-child pair.

Through this tutorial, you should have mastered the method of finding the parent node of a specified node using breadth-first traversal in a general tree. understand

The above is the detailed content of Finding parent nodes in a general tree: Implementation Guide based on breadth-first traversal. For more information, please follow other related articles on the PHP Chinese website!