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

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 的节点的父节点 (预期)。");         }     } }