通用树数据结构中查找指定节点父节点的广度优先搜索实现

import java.util.ArrayList;

public class Node {
    int key; // 节点的键值
    ArrayList<Node> children = new ArrayList<>(); // 存储子节点的列表

    /**
     * 判断当前节点是否有子节点
     * @return 如果有子节点返回true，否则返回false
     */
    public boolean hasChildren() {
        return !children.isEmpty();
    }
}

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

public class TreeOperations {

    // Node class (as defined above, repeated here for completeness)
    static class Node {
        int key;
        ArrayList<Node> children = new ArrayList<>();

        public Node(int key) {
            this.key = key;
        }

        public boolean hasChildren() {
            return !children.isEmpty();
        }

        // Optional: for easier tree construction/testing
        public void addChild(Node child) {
            this.children.add(child);
        }
    }

    /**
     * 使用广度优先搜索（BFS）在通用树中查找指定键值节点的父节点。
     *
     * @param root  树的根节点。
     * @param token 要查找的子节点的键值。
     * @return 如果找到，返回目标节点的父节点；如果目标节点是根节点或未找到，则返回null。
     */
    public static Node findParent(Node root, int token) {
        // 如果树为空，或者根节点为空，直接返回null
        if (root == null) {
            return null;
        }

        // 如果要找的token是根节点本身的key，那么根节点没有父节点，也返回null
        // 这一步是可选的，取决于业务逻辑，但通常根节点被认为是无父节点的
        if (root.key == token) {
            return null;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root); // 将根节点加入队列

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll(); // 取出当前层的一个节点，它可能是我们目标节点的父节点

            // 遍历当前节点的所有子节点
            for (Node child : currentNode.children) {
                // 如果子节点的键值与目标token匹配
                if (child.key == token) {
                    return currentNode; // 找到父节点，返回当前节点
                }
                // 如果不匹配，将子节点加入队列，以便后续探索其子树
                queue.add(child);
            }
        }
        // 遍历完所有节点仍未找到，说明目标节点不存在于树中（或者就是根节点本身）
        return null;
    }

    public static void main(String[] args) {
        // 示例树结构:
        //      10
        //     / | \
        //    20 30 40
        //   / \    /
        //  50 60  70
        Node root = new Node(10);
        Node node20 = new Node(20);
        Node node30 = new Node(30);
        Node node40 = new Node(40);
        Node node50 = new Node(50);
        Node node60 = new Node(60);
        Node node70 = new Node(70);

        root.addChild(node20);
        root.addChild(node30);
        root.addChild(node40);

        node20.addChild(node50);
        node20.addChild(node60);

        node40.addChild(node70);

        // 测试用例
        Node parentOf50 = findParent(root, 50);
        System.out.println("节点50的父节点是: " + (parentOf50 != null ? parentOf50.key : "未找到/无父节点")); // 预期: 20

        Node parentOf70 = findParent(root, 70);
        System.out.println("节点70的父节点是: " + (parentOf70 != null ? parentOf70.key : "未找到/无父节点")); // 预期: 40

        Node parentOf30 = findParent(root, 30);
        System.out.println("节点30的父节点是: " + (parentOf30 != null ? parentOf30.key : "未找到/无父节点")); // 预期: 10

        Node parentOf10 = findParent(root, 10); // 根节点
        System.out.println("节点10的父节点是: " + (parentOf10 != null ? parentOf10.key : "未找到/无父节点")); // 预期: 未找到/无父节点 (null)

        Node parentOf99 = findParent(root, 99); // 不存在的节点
        System.out.println("节点99的父节点是: " + (parentOf99 != null ? parentOf99.key : "未找到/无父节点")); // 预期: 未找到/无父节点 (null)
    }
}