如何实现中序线索二叉树中指定节点的父节点查找算法？

现有一棵带有*中序线索（inorder threads）*的二叉树，特性如下：如果节点不存在左孩子（右孩子），则该节点的左线索（右线索）会直接指向它的中序前驱（inorder predecessor）（中序后继（inorder successor））。

需求为结合上述特性，实现查找指定节点父节点的算法，以上图为例，若给定节点为Q，查找得到的父节点应为I。

补充说明：该算法将用于实现二叉树后序后继查找的相关逻辑。

算法思路 #

我们利用中序遍历左-根-右的特性，结合中序线索的指向规则，通过目标节点的中序前驱和后继来推导父节点，具体逻辑如下：

1. 首先处理边界：如果目标节点是根节点，直接返回空
2. 查找目标节点x的中序前驱pre：
   • 若pre存在，pre就是x的父节点，可直接返回
   • 若pre不存在，说明x是整棵树的最左节点，x必然是其父节点的左孩子，父节点就是x的中序后继
3. 特殊场景补充校验：如果通过前驱推导的节点不符合父节点特征，可再通过x的中序后继反向验证，x的中序后继必然是其左子树的根节点或父节点

伪代码实现 #

// 输入：中序线索二叉树的根节点root，待查找父节点的目标节点x
// 输出：x的父节点，若x为根节点则返回null
function findParent(root, x):
    // 根节点无父节点
    if x == root:
        return null
    
    // 第一步：通过中序前驱查找
    pre = getInorderPredecessor(x)
    if pre != null:
        // 两种情况都满足pre是父节点：pre右孩子是x（x是pre的右孩子）；pre右孩子不是x（x是pre右子树的最左节点）
        return pre
    
    // 第二步：前驱为空说明x是整树最左节点，通过中序后继查找
    succ = getInorderSuccessor(x)
    return succ

辅助函数说明 #

• getInorderPredecessor(node)：获取节点的中序前驱
  • 如果node的左指针是线索标记（即无真实左孩子），直接返回node.left
  • 否则返回node左子树的最右节点
• getInorderSuccessor(node)：获取节点的中序后继
  • 如果node的右指针是线索标记（即无真实右孩子），直接返回node.right
  • 否则返回node右子树的最左节点

内容的提问来源于stack exchange，提问作者mrkupidooo