本教程详细介绍了如何在通用树数据结构中，通过广度优先搜索（BFS）算法查找指定键值节点的父节点。文章将从节点结构定义入手，逐步阐述BFS遍历过程，并提供Java示例代码，帮助读者理解并实现高效的节点父级查找功能，同时讨论了算法的边界情况和注意事项。
1. 通用树节点结构定义
在处理通用树（或称多叉树）时，每个节点除了包含自身的数据（键值）外，还需要维护一个指向其所有子节点的引用集合。以下是一个典型的java语言节点类定义：
import java.util.ArrayList; public class Node { int key; // 节点的键值 ArrayList<Node> children = new ArrayList<>(); // 存储子节点的列表 /** * 判断当前节点是否有子节点 * @return 如果有子节点返回true，否则返回false */ public boolean hasChildren() { return !children.isEmpty(); } }
这个Node类包含了节点的key属性和一个ArrayList用于存储其所有子节点。hasChildren()方法提供了一个便捷的方式来检查节点是否为叶子节点。
2. 问题阐述：查找指定节点的父节点
给定一个通用树的根节点和一个目标键值（token），我们的任务是编写一个递归或迭代函数，该函数能够返回包含该目标键值的节点的父节点。如果目标节点是根节点（无父节点）或树中不存在该键值，则应返回特定值（例如null）。
3. 解决方案：广度优先搜索（BFS）
对于此类查找问题，广度优先搜索（BFS）是一种非常有效的遍历策略。BFS从根节点开始，逐层地访问树中的所有节点。这种层级遍历的特性使得我们能够很自然地在访问子节点时，同时知道其对应的父节点。
BFS实现思路：
- 初始化队列： 创建一个队列（如LinkedList实现的Queue），并将树的根节点加入队列。
- 循环遍历： 当队列不为空时，持续进行以下操作：
- 从队列中取出一个节点，我们称之为当前节点p（potential parent，潜在父节点）。
- 检查子节点： 遍历p的所有子节点c。
- 如果某个子节点c的key与目标token匹配，那么p就是我们正在寻找的父节点。此时，可以直接返回p。
- 如果子节点c的key不匹配，则将c加入队列，以便在后续的迭代中对其子节点进行检查。
- 未找到情况： 如果队列为空，且在整个遍历过程中都没有找到匹配的子节点，这意味着目标token不在树中（或者目标节点是根节点，而根节点没有父节点），此时返回null。
Java代码实现：
import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; public class TreeOperations { // Node class (as defined above, repeated here for completeness) static class Node { int key; ArrayList<Node> children = new ArrayList<>(); public Node(int key) { this.key = key; } public boolean hasChildren() { return !children.isEmpty(); } // Optional: for easier tree construction/testing public void addChild(Node child) { this.children.add(child); } } /** * 使用广度优先搜索（BFS）在通用树中查找指定键值节点的父节点。 * * @param root 树的根节点。 * @param token 要查找的子节点的键值。 * @return 如果找到，返回目标节点的父节点；如果目标节点是根节点或未找到，则返回null。 */ public static Node findParent(Node root, int token) { // 如果树为空，或者根节点为空，直接返回null if (root == null) { return null; } // 如果要找的token是根节点本身的key，那么根节点没有父节点，也返回null // 这一步是可选的，取决于业务逻辑，但通常根节点被认为是无父节点的 if (root.key == token) { return null; } 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) { // 示例树结构: // 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); // 测试用例 Node parentOf50 = findParent(root, 50); System.out.println("节点50的父节点是: " + (parentOf50 != null ? parentOf50.key : "未找到/无父节点")); // 预期: 20 Node parentOf70 = findParent(root, 70); System.out.println("节点70的父节点是: " + (parentOf70 != null ? parentOf70.key : "未找到/无父节点")); // 预期: 40 Node parentOf30 = findParent(root, 30); System.out.println("节点30的父节点是: " + (parentOf30 != null ? parentOf30.key : "未找到/无父节点")); // 预期: 10 Node parentOf10 = findParent(root, 10); // 根节点 System.out.println("节点10的父节点是: " + (parentOf10 != null ? parentOf10.key : "未找到/无父节点")); // 预期: 未找到/无父节点 (null) Node parentOf99 = findParent(root, 99); // 不存在的节点 System.out.println("节点99的父节点是: " + (parentOf99 != null ? parentOf99.key : "未找到/无父节点")); // 预期: 未找到/无父节点 (null) } }
4. 注意事项与总结
- 时间复杂度： BFS算法会访问树中的每个节点一次。在最坏情况下（目标节点是最后一个被访问的节点，或者不存在），算法需要遍历所有N个节点。因此，时间复杂度为O(N)，其中N是树中节点的总数。
- 空间复杂度： 空间复杂度主要取决于队列中存储的最大节点数。在最坏情况下，队列可能需要存储一层的所有节点。对于一个宽度为W的树，空间复杂度为O(W)。在极端情况下（例如，一个扁平的树，所有节点都是根的直接子节点），W可能接近N。
- 根节点特殊处理： 如果目标token是根节点的键值，findParent函数会返回null，因为根节点没有父节点。这符合通常的逻辑，但如果业务场景需要区分“未找到”和“是根节点”，则需要额外的逻辑来处理。
- 空树或空根： 在函数开始处，对root为null的情况进行了检查，确保了程序的健壮性。
- 适用性： BFS非常适合查找最短路径（在无权图中）或按层级顺序处理节点的问题。在本例中，它自然地维护了父子关系，使得查找父节点变得直观。
通过广度优先搜索，我们能够高效且清晰地在通用树数据结构中实现指定节点的父节点查找功能。这种方法不仅易于理解和实现，而且在性能上也表现良好。
评论（已关闭）
评论已关闭