通用树结构概述
通用树（General Tree）是一种非线性数据结构，其中每个节点可以拥有任意数量的子节点，与二叉树不同，二叉树的每个节点最多只有两个子节点。在处理通用树时，常见的操作包括遍历、查找和修改节点。本教程将专注于一个具体的查找问题：给定树的根节点和一个目标值（token），如何找到包含该目标值的节点的父节点。
为了实现这一功能，我们首先定义树的节点结构。一个典型的通用树节点会包含一个值（key）以及一个存储其所有子节点的列表。在Java中，可以定义如下：
import java.util.ArrayList;
public class Node {
int key; // 节点存储的值
ArrayList children = new ArrayList<>(); // 存储子节点的列表
/**
* 判断当前节点是否有子节点
* @return 如果有子节点返回true，否则返回false
*/
public boolean hasChildren(){
return !children.isEmpty(); // 更简洁的判断方式
}
} 这个Node类包含了节点的核心属性：一个整数key用于存储节点的值，以及一个ArrayList来存储其子节点。hasChildren()方法则提供了一个便捷的方式来检查节点是否有子节点。
基于广度优先搜索（BFS）的父节点查找
查找通用树中指定节点的父节点，可以采用多种遍历策略，其中广度优先搜索（BFS）是一种非常直观且高效的方法。BFS从根节点开始，逐层访问树中的所有节点。这种逐层遍历的特性使得在查找父节点时，当前被处理的节点自然而然地成为其子节点的潜在父节点。
算法思路
- 初始化队列： 创建一个队列（例如LinkedList实现的Queue），并将树的根节点加入队列。根节点是搜索的起点。
-
循环遍历： 当队列不为空时，持续执行以下步骤：
- 出队当前节点： 从队列中取出一个节点，我们称之为p。在本次迭代中，p是其所有子节点的父节点候选。
- 遍历子节点： 遍历p的所有子节点c。
-
检查匹配： 对于每一个子节点c：
- 如果c.key与我们要查找的目标值token相等，则说明我们找到了目标节点，此时p就是它的父节点。立即返回p。
- 如果c.key不匹配，则将c加入队列。这样，在后续的迭代中，c将作为父节点候选被处理，其子节点将被检查。
- 未找到： 如果队列为空，循环结束，这意味着树中不存在值为token的节点（或根节点本身就是token且我们不将其视为有父节点），此时返回null。
Java 实现示例
根据上述算法思路，我们可以编写如下Java函数来实现父节点的查找：
import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList; // 确保Node类能被正确编译
public class TreeParentFinder {
// Node类的定义，与上面保持一致
public static class Node {
int key;
ArrayList children = new ArrayList<>();
public Node(int key) {
this.key = key;
}
public boolean hasChildren(){
return !children.isEmpty();
}
// 方便测试，添加子节点的方法
public void addChild(Node child) {
this.children.add(child);
}
}
/**
* 在通用树中查找指定节点的父节点
*
* @param root 树的根节点
* @param token 要查找的目标节点的键值
* @return 如果找到目标节点的父节点，则返回该父节点；如果目标节点不存在或目标节点是根节点，则返回null。
*/
public static Node findParent(Node root, int token) {
// 如果树为空，或者根节点为空，直接返回null
if (root == null) {
return null;
}
// 使用LinkedList作为Queue的实现
Queue queue = new LinkedList<>();
queue.add(root); // 将根节点加入队列
// BFS遍历
while (!queue.isEmpty()) {
Node p = queue.poll(); // 出队当前节点，作为潜在的父节点
// 遍历当前节点p的所有子节点
for (Node c : p.children) {
// 如果子节点c的key与目标token匹配
if (c.key == token) {
return p; // 找到了，p就是c的父节点，返回p
}
// 如果不匹配，将子节点c加入队列，以便后续作为父节点候选进行处理
queue.add(c);
}
}
// 遍历完所有节点仍未找到，说明目标节点不存在或目标节点是根节点
return null;
}
public static void main(String[] args) {
// 构建一个示例通用树
// 10
// / | \
// 20 30 40
// / \ |
// 50 60 70
// / \
// 80 90
Node root = new Node(10);
Node node20 = new Node(20);
Node node30 = new Node(30);
Node node40 = new Node(40);
root.addChild(node20);
root.addChild(node30);
root.addChild(node40);
Node node50 = new Node(50);
Node node60 = new Node(60);
node20.addChild(node50);
node20.addChild(node60);
Node node70 = new Node(70);
node40.addChild(node70);
Node node80 = new Node(80);
Node node90 = new Node(90);
node70.addChild(node80);
node70.addChild(node90);
// 测试用例
System.out.println("查找节点 60 的父节点:");
Node parent60 = findParent(root, 60);
System.out.println(parent60 != null ? "父节点是: " + parent60.key : "未找到父节点"); // 预期: 20
System.out.println("查找节点 80 的父节点:");
Node parent80 = findParent(root, 80);
System.out.println(parent80 != null ? "父节点是: " + parent80.key : "未找到父节点"); // 预期: 70
System.out.println("查找节点 30 的父节点:");
Node parent30 = findParent(root, 30);
System.out.println(parent30 != null ? "父节点是: " + parent30.key : "未找到父节点"); // 预期: 10
System.out.println("查找根节点 10 的父节点:");
Node parent10 = findParent(root, 10);
System.out.println(parent10 != null ? "父节点是: " + parent10.key : "未找到父节点"); // 预期: null
System.out.println("查找不存在的节点 999 的父节点:");
Node parent999 = findParent(root, 999);
System.out.println(parent999 != null ? "父节点是: " + parent999.key : "未找到父节点"); // 预期: null
}
} 注意事项与性能分析
- 根节点无父节点： 根据定义，根节点没有父节点。如果token的值与根节点的key相同，findParent函数将返回null。这是符合逻辑的，因为根节点不会作为任何其他节点的子节点被添加到队列中，也不会被任何父节点遍历到。
- 重复键值： 如果树中存在多个节点拥有相同的key值，此findParent函数将返回在BFS遍历过程中第一个找到的匹配节点的父节点。如果需要查找所有匹配节点的父节点，则需要修改函数，返回一个Node列表。
- 时间复杂度： 该算法的时间复杂度为 O(N)，其中N是树中节点的总数。在最坏的情况下，需要访问树中的所有节点才能找到目标节点或确定其不存在。
- 空间复杂度： 空间复杂度为 O(W)，其中W是树的最大宽度（即在某一层上节点数量最多的那一层的节点数）。这是因为在BFS过程中，队列中最多会存储一层的所有节点。在极端情况下（例如，一个扁平的树，所有节点都是根节点的直接子节点），W可能接近N。
- 递归与迭代： 虽然原问题提到了递归，但对于查找父节点这种需要“记住”当前节点作为父节点的情况，迭代的BFS通常更为直接和易于理解。递归在DFS（深度优先搜索）中更常用，但在处理父节点关系时，需要额外的参数或数据结构来传递父节点信息。迭代的BFS避免了深度递归可能导致的栈溢出问题，尤其是在处理非常深的树时。
总结
本文详细介绍了如何利用广度优先搜索（BFS）策略在通用树数据结构中查找指定节点的父节点。通过使用队列来管理节点的遍历顺序，我们能够高效地识别目标节点的父级。所提供的Java示例代码清晰地展示了这一过程，并讨论了算法的关键特性和潜在的注意事项。掌握这种查找方法对于理解和操作通用树数据结构至关重要。
