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

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 的父节点。"); // 预期输出 未找到...         }     } }