通用树中查找指定节点的父节点：基于广度优先搜索的实现

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.LinkedList;
import java.util.Queue;
import java.util.ArrayList; // 确保Node类能被正确编译

public class TreeParentFinder {

    // Node类的定义，与上面保持一致
    public static class Node {
        int key;
        ArrayList<Node> children = new ArrayList<>();

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

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

        // 方便测试，添加子节点的方法
        public void addChild(Node child) {
            this.children.add(child);
        }
    }

    /**
     * 在通用树中查找指定节点的父节点
     *
     * @param root 树的根节点
     * @param token 要查找的目标节点的键值
     * @return 如果找到目标节点的父节点，则返回该父节点；如果目标节点不存在或目标节点是根节点，则返回null。
     */
    public static Node findParent(Node root, int token) {
        // 如果树为空，或者根节点为空，直接返回null
        if (root == null) {
            return null;
        }

        // 使用LinkedList作为Queue的实现
        Queue<Node> queue = new LinkedList<>();
        queue.add(root); // 将根节点加入队列

        // BFS遍历
        while (!queue.isEmpty()) {
            Node p = queue.poll(); // 出队当前节点，作为潜在的父节点

            // 遍历当前节点p的所有子节点
            for (Node c : p.children) {
                // 如果子节点c的key与目标token匹配
                if (c.key == token) {
                    return p; // 找到了，p就是c的父节点，返回p
                }
                // 如果不匹配，将子节点c加入队列，以便后续作为父节点候选进行处理
                queue.add(c);
            }
        }
        // 遍历完所有节点仍未找到，说明目标节点不存在或目标节点是根节点
        return null;
    }

    public static void main(String[] args) {
        // 构建一个示例通用树
        //       10
        //      / | \
        //     20 30 40
        //    / \   |
        //   50 60  70
        //          / \
        //         80 90

        Node root = new Node(10);

        Node node20 = new Node(20);
        Node node30 = new Node(30);
        Node node40 = new Node(40);

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

        Node node50 = new Node(50);
        Node node60 = new Node(60);
        node20.addChild(node50);
        node20.addChild(node60);

        Node node70 = new Node(70);
        node40.addChild(node70);

        Node node80 = new Node(80);
        Node node90 = new Node(90);
        node70.addChild(node80);
        node70.addChild(node90);

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

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

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

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

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