通用树中节点父节点的查找：基于广度优先遍历的实现

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

/**
 * 通用树节点定义
 */
public class Node {
    int key; // 节点存储的键值
    ArrayList<Node> children; // 子节点列表

    /**
     * 构造函数
     * @param key 节点的键值
     */
    public Node(int key) {
        this.key = key;
        this.children = new ArrayList<>();
    }

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

    /**
     * 添加子节点
     * @param child 要添加的子节点
     */
    public void addChild(Node child) {
        this.children.add(child);
    }
}

// 为了运行示例，这里假设 Node 类和必要的 import 语句已经定义
// import java.util.ArrayList;
// import java.util.LinkedList;
// import java.util.Queue;

public class TreeOperations {

    /**
     * 在通用树中查找指定节点的父节点
     * 使用广度优先遍历（BFS）实现
     *
     * @param root 树的根节点
     * @param token 要查找的子节点的键值
     * @return 目标节点的父节点；如果目标节点是根节点或未找到，则返回null
     */
    public static Node findParent(Node root, int token) {
        // 如果树为空，或者目标节点是根节点（根节点没有父节点），则直接返回null
        // 注意：如果token就是root.key，此函数也会返回null，符合根节点无父节点的逻辑
        if (root == null) {
            return null;
        }

        // 使用LinkedList作为队列实现BFS
        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);
            }
        }

        // 遍历完所有节点仍未找到目标token，或者目标token是根节点本身
        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);

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

        System.out.println("\n查找节点 70 的父节点:");
        Node parent70 = findParent(root, 70);
        System.out.println(parent70 != null ? "父节点是: " + parent70.key : "未找到父节点或目标是根节点"); // 预期: 40

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

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

        System.out.println("\n查找不存在的节点 99 的父节点:");
        Node parent99 = findParent(root, 99);
        System.out.println(parent99 != null ? "父节点是: " + parent99.key : "未找到父节点或目标是根节点"); // 预期: null
    }
}