在二叉搜索树中查找节点父节点的Java实现

1. 引言

二叉搜索树（BST）是一种高效解决实际问题的数据结构。本文将探讨如何在BST中查找任意节点的父节点，并提供多种实现方案。

2. 什么是二叉搜索树？

BST是一种每个节点最多指向两个子节点（左子节点和右子节点）的树结构，且每个节点的值大于其左子节点、小于其右子节点。

例如，三个节点A=2、B=1、C=4可以构成一个BST：A作为根节点，B作为左子节点，C作为右子节点。后续我们将使用带有默认insert()方法的BST实现来演示查找父节点的问题。

3. 二叉搜索树中的节点父节点问题

3.1. 问题描述

BST中的节点包含指向左右子节点的指针。以一个简单BST为例：

问题描述示例

节点8有两个子节点5和12，因此节点8是5和12的父节点。

核心问题：给定任意节点值，找到其父节点。 即查找某个子节点值等于目标值的节点。例如：

输入5 → 输出8
输入12 → 输出8

⚠️ 边界情况：

查找根节点（无父节点）
查找不存在的节点（无父节点）

3.2. 测试结构

在深入解决方案前，先定义基础测试结构：

class BinaryTreeParentNodeFinderUnitTest {

    TreeNode subject;

    @BeforeEach
    void setUp() {
        subject = new TreeNode(8);
        subject.insert(5);
        subject.insert(12);
        subject.insert(3);
        subject.insert(7);
        subject.insert(1);
        subject.insert(4);
        subject.insert(11);
        subject.insert(14);
        subject.insert(13);
        subject.insert(16);
    }
}

setUp()方法构建如下BST：

测试结构BST

4. 递归解决方案

最直观的方案是递归遍历树，当发现当前节点的子节点等于目标值时立即返回当前节点。

首先在TreeNode类中定义公共方法：

TreeNode parent(int target) throws NoSuchElementException {
    return parent(this, new TreeNode(target));
}

递归核心实现：

TreeNode parent(TreeNode current, TreeNode target) throws NoSuchElementException {
    if (target.equals(current) || current == null) {
        throw new NoSuchElementException(format("No parent node found for 'target.value=%s' " +
            "The target is not in the tree or the target is the topmost root node.",
            target.value));
    }

    if (target.equals(current.left) || target.equals(current.right)) {
        return current;
    }

    return parent(target.value < current.value ? current.left : current.right, target);
}

算法逻辑：

边界检查：若当前节点是根节点或节点不存在，抛出异常
匹配检查：若当前节点的子节点匹配目标值，返回当前节点
递归遍历：根据目标值大小选择左/右子树递归

✅ 测试验证：

@Test
void givenBinaryTree_whenFindParentNode_thenReturnCorrectParentNode() {
    assertThrows(NoSuchElementException.class, () -> subject.parent(1231)); // 不存在节点
    assertThrows(NoSuchElementException.class, () -> subject.parent(8));     // 根节点
    assertEquals(8, subject.parent(5).value);  // 5的父节点是8
    assertEquals(5, subject.parent(3).value);  // 3的父节点是5
    assertEquals(5, subject.parent(7).value);  // 7的父节点是5
    assertEquals(3, subject.parent(4).value);  // 4的父节点是3
    // 其他节点测试...
}

复杂度分析：

时间：最坏O(n)（退化为链表），平衡树O(log n)
空间：O(h)（h为树高，递归调用栈深度）

5. 迭代解决方案

递归方案通常可转为迭代实现，这里用栈和while循环替代递归。

在TreeNode类中添加接口方法：

TreeNode iterativeParent(int target) {
    return iterativeParent(this, new TreeNode(target));
}

核心迭代实现：

TreeNode iterativeParent(TreeNode current, TreeNode target) {
    Deque<TreeNode> parentCandidates = new LinkedList<>();

    String notFoundMessage = format("No parent node found for 'target.value=%s' " +
        "The target is not in the tree or the target is the topmost root node.",
        target.value);

    if (target.equals(current)) {
        throw new NoSuchElementException(notFoundMessage);
    }

    while (current != null || !parentCandidates.isEmpty()) {
        // 左子节点遍历
        while (current != null) {
            parentCandidates.addFirst(current);
            current = current.left;
        }

        current = parentCandidates.pollFirst();

        // 检查是否为父节点
        if (target.equals(current.left) || target.equals(current.right)) {
            return current;
        }

        current = current.right; // 转向右子树
    }

    throw new NoSuchElementException(notFoundMessage);
}

算法四步走：

外层循环：继续遍历直到处理完所有节点
内层循环：沿左子树向下，将候选父节点压栈
节点检查：弹出栈顶节点，检查是否为目标父节点
右子树处理：若未找到则转向右子树

✅ 测试验证：

@Test
void givenBinaryTree_whenFindParentNodeIteratively_thenReturnCorrectParentNode() {
    assertThrows(NoSuchElementException.class, () -> subject.iterativeParent(1231));
    assertThrows(NoSuchElementException.class, () -> subject.iterativeParent(8));
    assertEquals(8, subject.iterativeParent(5).value);
    assertEquals(5, subject.iterativeParent(3).value);
    assertEquals(5, subject.iterativeParent(7).value);
    assertEquals(3, subject.iterativeParent(4).value);
    // 其他节点测试...
}

复杂度分析：

时间：最坏O(n)，平衡树O(log n)
空间：O(h)（栈存储候选父节点）

6. 带父指针的BST实现

终极方案：修改BST结构，在节点中直接存储父节点引用。

创建新类ParentKeeperTreeNode：

class ParentKeeperTreeNode {

    int value;
    ParentKeeperTreeNode parent;  // 新增父节点引用
    ParentKeeperTreeNode left;
    ParentKeeperTreeNode right;

    // 构造方法、equals和hashCode...
}

自定义insert()方法维护父指针：

void insert(ParentKeeperTreeNode currentNode, final int value) {
    if (currentNode.left == null && value < currentNode.value) {
        currentNode.left = new ParentKeeperTreeNode(value);
        currentNode.left.parent = currentNode;  // 设置父节点
        return;
    }

    if (currentNode.right == null && value > currentNode.value) {
        currentNode.right = new ParentKeeperTreeNode(value);
        currentNode.right.parent = currentNode; // 设置父节点
        return;
    }

    if (value > currentNode.value) {
        insert(currentNode.right, value);
    }

    if (value < currentNode.value) {
        insert(currentNode.left, value);
    }
}

关键点：创建新子节点时，将当前节点设为其父节点。

✅ 测试验证：

@Test
void givenParentKeeperBinaryTree_whenGetParent_thenReturnCorrectParent() {
    ParentKeeperTreeNode subject = new ParentKeeperTreeNode(8);
    subject.insert(5);
    subject.insert(12);
    subject.insert(3);
    // 插入其他节点...

    assertNull(subject.parent);           // 根节点无父节点
    assertEquals(8, subject.left.parent.value);   // 5的父节点是8
    assertEquals(8, subject.right.parent.value);  // 12的父节点是8
    assertEquals(5, subject.left.left.parent.value); // 3的父节点是5
    // 其他节点测试...
}

优势分析：

时间复杂度：O(1)（直接访问父节点引用）
空间复杂度：O(1)（仅需存储一个引用）
✅ 适用场景：频繁需要获取父节点的操作

7. 总结

本文探讨了BST中查找父节点的三种实现方案：

递归方案：代码简洁，但受递归深度限制
迭代方案：避免递归栈溢出，逻辑稍复杂
父指针方案：空间换时间，适合高频查询场景

💡 踩坑提示：递归方案在树退化时可能导致栈溢出，生产环境建议用迭代方案；若父节点查询极其频繁，重构数据结构可能是更优解。

完整代码示例可在GitHub仓库获取。

Persistence

REST

Security

1. 引言

2. 什么是二叉搜索树？

3. 二叉搜索树中的节点父节点问题

3.1. 问题描述

3.2. 测试结构

4. 递归解决方案

5. 迭代解决方案

6. 带父指针的BST实现

7. 总结