通用树中查找指定节点父节点的算法：基于广度优先遍历

import java.util.ArrayList;

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

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList; // 确保Node类所需的ArrayList也被导入

public class TreeOperations {

    /**
     * 在通用树中查找指定键值节点的父节点。
     * 使用广度优先遍历（BFS）实现。
     *
     * @param root  树的根节点。
     * @param token 要查找的子节点的键值。
     * @return 如果找到，返回目标节点的父节点；如果目标节点不存在、
     *         树为空或者目标节点是根节点（无父节点），则返回 null。
     */
    public static Node findParent(Node root, int token) {
        // 处理空树的情况
        if (root == null) {
            return null;
        }

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

        // 当队列不为空时，持续进行遍历
        while (!queue.isEmpty()) {
            // 从队列中取出一个节点，作为当前的“潜在父节点”
            Node p = queue.poll();

            // 遍历当前节点 p 的所有子节点
            for (Node c : p.children) {
                // 检查子节点 c 的键值是否与目标 token 匹配
                if (c.key == token) {
                    // 如果匹配，说明 p 就是 c 的父节点，直接返回 p
                    return p;
                }
                // 如果不匹配，将子节点 c 加入队列，以便在后续迭代中作为潜在的父节点进行检查
                queue.add(c);
            }
        }
        // 如果队列为空，且在遍历过程中没有找到目标 token 的父节点，则返回 null
        return null;
    }

    // 示例用法
    public static void main(String[] args) {
        // 构建一个示例通用树
        // 结构:
        //      1
        //     / \
        //    2   3
        //   / \   \
        //  4   5   6

        Node root = new Node();
        root.key = 1;

        Node child2 = new Node();
        child2.key = 2;
        Node child3 = new Node();
        child3.key = 3;

        root.children.add(child2);
        root.children.add(child3);

        Node child4 = new Node();
        child4.key = 4;
        Node child5 = new Node();
        child5.key = 5;

        child2.children.add(child4);
        child2.children.add(child5);

        Node child6 = new Node();
        child6.key = 6;
        child3.children.add(child6);

        System.out.println("通用树结构已构建。");

        // 测试用例
        System.out.println("\n--- 查找父节点测试 ---");

        // 查找键值为 5 的节点的父节点 (预期: 2)
        Node parentOf5 = findParent(root, 5);
        if (parentOf5 != null) {
            System.out.println("键值为 5 的节点的父节点是: " + parentOf5.key);
        } else {
            System.out.println("未找到键值为 5 的节点的父节点。");
        }

        // 查找键值为 6 的节点的父节点 (预期: 3)
        Node parentOf6 = findParent(root, 6);
        if (parentOf6 != null) {
            System.out.println("键值为 6 的节点的父节点是: " + parentOf6.key);
        } else {
            System.out.println("未找到键值为 6 的节点的父节点。");
        }

        // 查找键值为 1 的节点的父节点 (预期: null, 因为它是根节点)
        Node parentOf1 = findParent(root, 1);
        if (parentOf1 != null) {
            System.out.println("键值为 1 的节点的父节点是: " + parentOf1.key);
        } else {
            System.out.println("未找到键值为 1 的节点的父节点 (预期)。");
        }

        // 查找不存在的键值 99 的节点的父节点 (预期: null)
        Node parentOf99 = findParent(root, 99);
        if (parentOf99 != null) {
            System.out.println("键值为 99 的节点的父节点是: " + parentOf99.key);
        } else {
            System.out.println("未找到键值为 99 的节点的父节点 (预期)。");
        }
    }
}