试写一个算法,在先序后继线索二叉树中,查找给定结点*p在先序序列中的后继(假设二叉树的根结点未知)

在先序后继线索二叉树中，每个节点都有三个指针：一个指向它的前驱（predecessor）、一个指向它的自身（self），还有一个指向它的后继（successor）。查找给定节点 \( p \) 的后继可以分为几个步骤：

1. 首先，我们需要找到 \( p \) 的后继节点。由于 \( p \) 自身的后继指针是指向其后继，所以可以直接访问。

   successor_node = p.successor;

2. 然而，如果后继节点本身没有后继（也就是说它是叶子节点），那么需要沿着其父亲节点的右儿子（因为在先序遍历时，右子节点总是出现在左子节点之后）寻找后继。我们从 \( p \) 的父亲节点开始，直到找到一个有右孩子（或者到达根节点）为止。

   while successor_node.is_leaf() and successor_node.parent is not None:
       successor_node = successor_node.parent.right_successor;  // 使用右后继指针

这里的 `is_leaf()` 是判断节点是否为叶子节点的函数，`right_successor` 是获取节点右后继的属性。

完整的算法如下：

def find_successor(p):
    successor_node = p.successor;

    if successor_node.is_leaf():
        current = p.parent;
        while current is not None and current.right_child == p:
            successor_node = current;
            current = current.parent;
        
        if current is None:
            successor_node = None;  // 根节点没有后继
        else:
            successor_node = current.right_successor;
    
    return successor_node;