先驱和后驱的非递归算法如何写

先驱和后驱的非递归算法可以使用栈来实现。

先驱算法的非递归实现：

1. 创建一个栈，并将根节点入栈。
2. 取出栈顶节点，将其左子节点入栈。
3. 如果当前节点没有右子节点，则返回该节点；否则将右子节点入栈。
4. 重复步骤2-3，直到栈为空。

后驱算法的非递归实现：

1. 创建一个栈，并将根节点入栈。
2. 如果栈不为空，取出栈顶节点，并将该节点的右子节点入栈。
3. 如果当前节点有左子节点，则将左子节点入栈，并重复步骤2。
4. 如果当前节点没有左子节点，说明该节点为后驱节点，返回该节点。
5. 重复步骤2-4，直到栈为空。

下面是先驱和后驱的非递归算法的Python实现：

先驱算法的非递归实现：

def inorder_successor(root, node):
    stack = []
    curr = root
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            if curr.val == node.val:
                if curr.right:
                    curr = curr.right
                    while curr.left:
                        curr = curr.left
                    return curr
                else:
                    if stack:
                        return stack.pop()
                    else:
                        return None
            curr = curr.right
    return None

后驱算法的非递归实现：

def inorder_predecessor(root, node):
    stack = []
    curr = root
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.right
        else:
            curr = stack.pop()
            if curr.val == node.val:
                if curr.left:
                    curr = curr.left
                    while curr.right:
                        curr = curr.right
                    return curr
                else:
                    if stack:
                        return stack.pop()
                    else:
                        return None
            curr = curr.left
    return None