通用树节点结构定义
在通用树（General Tree）中，一个节点可以拥有任意数量的子节点，这与二叉树每个节点最多只有两个子节点的结构有所不同。为了实现对通用树的操作，我们首先需要定义其节点结构。一个典型的通用树节点通常包含一个用于标识节点的值（或键），以及一个存储其所有子节点的列表。
以下是本文示例中使用的Java语言节点定义：
import java.util.ArrayList;
import java.util.LinkedList; // For Queue
import java.util.Queue; // For Queue
/**
* 通用树节点定义
*/
public class Node {
int key; // 节点存储的键值
ArrayList children; // 子节点列表
/**
* 构造函数
* @param key 节点的键值
*/
public Node(int key) {
this.key = key;
this.children = new ArrayList<>();
}
/**
* 检查节点是否有子节点
* @return 如果有子节点返回true，否则返回false
*/
public boolean hasChildren(){
return !children.isEmpty();
}
/**
* 添加子节点
* @param child 要添加的子节点
*/
public void addChild(Node child) {
this.children.add(child);
}
} 在这个 Node 类中：
- key：表示当前节点的值或标识符。
- children：一个 ArrayList，用于存储当前节点的所有子节点。
- Node(int key)：构造函数，用于初始化节点。
- hasChildren()：一个辅助方法，用于判断当前节点是否有子节点。
- addChild(Node child)：一个辅助方法，用于向当前节点添加子节点。
问题描述：查找指定节点的父节点
我们的目标是编写一个函数，给定通用树的根节点（root）和一个目标键值（token），该函数需要返回拥有该目标键值的节点的父节点。如果目标节点是树的根节点（根节点没有父节点），或者树中不存在具有该键值的节点，则函数应返回 null。
广度优先遍历（BFS）策略
广度优先遍历（BFS）是一种图或树的遍历算法，它从起始节点开始，首先访问其所有邻居节点，然后访问这些邻居节点的邻居节点，依此类推。在树结构中，BFS会逐层地访问节点：先访问根节点，然后是其所有子节点（第一层），接着是第一层节点的所有子节点（第二层），以此类推。
BFS非常适合解决查找父节点的问题，原因如下：
- 逐层探索： BFS的特性使其能够一层一层地搜索树。当它遍历到某个节点 p 时，它会检查 p 的所有子节点 c。如果 c 的键值与 token 匹配，那么 p 自然就是 c 的父节点。
- 简单直接： 这种策略避免了深度优先遍历（DFS）中可能需要的复杂回溯逻辑，使得父节点的查找过程更加直观。
算法实现与解析
我们将使用一个队列（Queue）来实现广度优先遍历。算法步骤如下：
- 初始化队列： 创建一个 LinkedList 作为队列，并将树的根节点 root 加入队列。
-
循环遍历： 当队列不为空时，持续执行以下操作：
- 出队： 从队列中取出一个节点 p（当前正在处理的节点）。
-
检查子节点： 遍历 p 的所有子节点 c。
- 匹配判断： 如果 c.key 等于目标 token，则说明我们找到了目标节点，此时 p 就是它的父节点，立即返回 p。
- 入队： 如果 c.key 不匹配 token，则将 c 加入队列，以便在后续迭代中处理其子节点。
- 未找到： 如果循环结束，队列为空，但仍未找到匹配 token 的节点，则表示树中不存在该节点或目标节点是根节点（根节点无父节点），此时返回 null。
以下是该算法的Java实现：
// 为了运行示例，这里假设 Node 类和必要的 import 语句已经定义
// 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
// 注意：如果token就是root.key，此函数也会返回null，符合根节点无父节点的逻辑
if (root == null) {
return null;
}
// 使用LinkedList作为队列实现BFS
Queue 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);
}
}
// 遍历完所有节点仍未找到目标token，或者目标token是根节点本身
return null;
}
public static void main(String[] args) {
// 构造一个通用树示例
// 10
// / | \
// 20 30 40
// / \ |
// 50 60 70
Node root = new Node(10);
Node node20 = new Node(20);
Node node30 = new Node(30);
Node node40 = new Node(40);
Node node50 = new Node(50);
Node node60 = new Node(60);
Node node70 = new Node(70);
root.addChild(node20);
root.addChild(node30);
root.addChild(node40);
node20.addChild(node50);
node20.addChild(node60);
node40.addChild(node70);
// 测试用例
System.out.println("查找节点 50 的父节点:");
Node parent50 = findParent(root, 50);
System.out.println(parent50 != null ? "父节点是: " + parent50.key : "未找到父节点或目标是根节点"); // 预期: 20
System.out.println("\n查找节点 70 的父节点:");
Node parent70 = findParent(root, 70);
System.out.println(parent70 != null ? "父节点是: " + parent70.key : "未找到父节点或目标是根节点"); // 预期: 40
System.out.println("\n查找节点 30 的父节点:");
Node parent30 = findParent(root, 30);
System.out.println(parent30 != null ? "父节点是: " + parent30.key : "未找到父节点或目标是根节点"); // 预期: 10
System.out.println("\n查找节点 10 (根节点) 的父节点:");
Node parent10 = findParent(root, 10);
System.out.println(parent10 != null ? "父节点是: " + parent10.key : "未找到父节点或目标是根节点"); // 预期: null
System.out.println("\n查找不存在的节点 99 的父节点:");
Node parent99 = findParent(root, 99);
System.out.println(parent99 != null ? "父节点是: " + parent99.key : "未找到父节点或目标是根节点"); // 预期: null
}
} 注意事项与性能分析
-
时间复杂度：
- 该算法的时间复杂度为 O(N)，其中 N 是树中节点的总数。在最坏情况下，我们需要访问树中的所有节点才能找到目标节点或确定其不存在。
-
空间复杂度：
- 空间复杂度取决于队列中存储的最大节点数。在最坏情况下（例如，一个非常宽的树），队列可能需要存储一整层的节点。因此，空间复杂度为 O(W)，其中 W 是树的最大宽度。在极端情况下，如果树是一个链表（只有一个子节点），W=1；如果树是完全平衡的，W 可能是 N/2。因此，最坏情况下的空间复杂度可以达到 O(N)（例如，一个只有根节点和大量直接子节点的树）。
-
根节点的处理：
- 如果 token 的值与根节点的 key 相同，findParent 函数将返回 null。这是符合逻辑的，因为根节点没有父节点。
-
未找到目标节点：
- 如果树中不存在具有 token 值的节点，函数将遍历完整个树，最终队列为空，并返回 null。
-
空树处理：
- 如果传入的 root 为 null，函数会立即返回 null，避免了空指针异常。
总结
通过广度优先遍历（BFS）查找通用树中指定节点的父节点是一种高效且直观的方法。它利用队列的特性，逐层检查节点及其子节点，从而在找到目标节点时能够直接确定其父节点。这种方法不仅易于理解和实现，而且在大多数情况下具有良好的性能表现。掌握BFS在树结构中的应用，对于处理各种树相关的查找和遍历问题都至关重要。
