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

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 {

    /**
     * 在通用树中查找指定键值节点的父节点。
     * 使用广度优先遍历（BFS）实现。
     *
     * @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); // 将根节点加入队列，作为遍历的起点

        // 广度优先遍历
        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) {
        // 构建一个示例通用树
        //       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);

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

        Node parentOf7 = findParent(root, 7);
        if (parentOf7 != null) {
            System.out.println("节点 7 的父节点是: " + parentOf7.key); // 预期输出 4
        } else {
            System.out.println("未找到节点 7 的父节点。");
        }

        Node parentOf1 = findParent(root, 1); // 根节点无父节点
        if (parentOf1 != null) {
            System.out.println("节点 1 的父节点是: " + parentOf1.key);
        } else {
            System.out.println("未找到节点 1 的父节点（或其是根节点）。"); // 预期输出 未找到...
        }

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