引言：通用树与父节点查找问题
通用树（General Tree）是一种非线性数据结构，与二叉树不同，它的每个节点可以拥有任意数量的子节点。在处理通用树时，一个常见的操作是查找特定节点的父节点。给定树的根节点和一个目标值（或称为“令牌”），我们的任务是编写一个函数，返回拥有该目标值的节点的父节点。这对于理解树的结构、进行路径追踪或执行其他依赖于层级关系的操作至关重要。
本教程将详细介绍如何使用广度优先遍历（BFS）策略来实现这一功能。BFS通过逐层探索树的节点来查找目标，这使得它非常适合于查找父节点这类需要检查直接子节点关系的场景。
节点数据结构定义
首先，我们定义通用树的节点结构。每个节点包含一个键（key）用于标识自身，以及一个子节点列表（children）来存储其所有直接子节点。
import java.util.ArrayList;
public class Node {
int key; // 节点的键值
ArrayList children = new ArrayList<>(); // 存储子节点的列表
/**
* 判断当前节点是否有子节点。
* @return 如果有子节点返回 true，否则返回 false。
*/
public boolean hasChildren() {
if (children.size() != 0) {
return true;
} else {
return false;
}
}
} 广度优先遍历（BFS）算法原理
广度优先遍历（BFS）是一种图或树的遍历算法，它从起始节点开始，首先访问其所有相邻节点（在树中即为所有子节点），然后是这些子节点的相邻节点，依此类推。在树的上下文中，这意味着BFS会先访问当前层的所有节点，然后再进入下一层。
对于查找父节点的问题，BFS的优势在于：
- 层序探索： BFS天然地按照层级顺序遍历节点。当我们从队列中取出一个节点 p 时，p 的所有子节点 c 都会被检查。如果 c 是我们正在寻找的目标节点，那么 p 自然就是它的父节点。
- 队列管理： BFS使用队列来管理待访问的节点。当前节点的所有子节点在被检查后，如果它们不是目标节点，就会被加入队列，等待在后续的迭代中作为“潜在父节点”被处理。
Java实现与代码解析
下面是使用BFS实现查找指定节点父节点的Java代码：
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 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 的节点的父节点 (预期)。");
}
}
} 注意事项与边界情况
在使用上述 findParent 函数时，需要考虑以下几点：
- 空树处理： 如果传入的 root 为 null（即树为空），函数会立即返回 null，这是正确的行为，因为空树中不存在任何节点，自然也找不到其父节点。
- 目标节点是根节点： 如果要查找的 token 恰好是根节点的键值，findParent 函数将返回 null。这是符合逻辑的，因为根节点在树结构中没有父节点。算法在遍历过程中，根节点本身会作为 p 出队，但它的子节点不会匹配根节点的 key，因此根节点永远不会被识别为某个节点的子节点，从而其父节点也不会被找到。
- 目标节点不存在： 如果树中不存在与 token 匹配的节点，while 循环将遍历完所有可达节点，最终队列变空，函数将返回 null。
- 重复键值： 如果树中存在多个节点具有相同的 key，此算法将返回在BFS遍历过程中遇到的第一个匹配 token 的节点的父节点。BFS的特性决定了它会优先找到离根节点更近（层级更浅）的节点。
- 时间复杂度： 算法会访问树中的每个节点和每条边一次。因此，其时间复杂度为 O(V + E)，其中 V 是节点的数量，E 是边的数量。在树中，E = V - 1，所以可以简化为 O(V)，即与树中节点总数成正比。
- 空间复杂度： 算法需要一个队列来存储待访问的节点。在最坏的情况下（例如，一个非常宽的树），队列可能需要存储一整层的节点。因此，空间复杂度为 O(W)，其中 W 是树的最大宽度。
总结
通过广度优先遍历（BFS），我们可以高效且清晰地在通用树数据结构中查找指定节点的父节点。利用队列的先进先出特性，算法能够系统地逐层探索树的节点，确保在找到目标节点时，其父节点已被正确识别。这种方法不仅逻辑直观，而且在大多数情况下能提供良好的性能。理解并掌握BFS在树遍历中的应用，对于处理各种树相关的算法问题都至关重要。
