二叉排序树非递归插入节点

二叉排序树（Binary Search Tree）是一种特殊的二叉树，其中每个节点的值都大于其左子树中的任何节点的值，且小于其右子树中的任何节点的值。要在二叉排序树中插入一个节点，可以使用非递归的方法来进行操作。

以下是非递归插入节点的步骤：

1. 如果树为空，则将要插入的节点作为根节点。
2. 如果树不为空，则从根节点开始遍历树，找到合适的插入位置。
- 从根节点开始，将要插入的节点与当前节点进行比较。
- 如果要插入的节点的值小于当前节点的值，则继续在当前节点的左子树中查找。
- 如果要插入的节点的值大于当前节点的值，则继续在当前节点的右子树中查找。
- 重复上述步骤，直到找到一个叶子节点位置，即左子树或右子树为空。
3. 将要插入的节点插入到找到的位置上，作为叶子节点。
- 如果要插入的节点的值小于当前节点的值，则将其作为当前节点的左子节点。
- 如果要插入的节点的值大于当前节点的值，则将其作为当前节点的右子节点。

以下是一个示例代码，演示了如何在二叉排序树中插入节点的非递归实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insertNode(root, val):
    if root is None:
        root = TreeNode(val)
        return root
    
    curr = root
    while curr:
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right

# 示例用法
root = TreeNode(5)
insertNode(root, 3)
insertNode(root, 8)
insertNode(root, 2)
insertNode(root, 4)
insertNode(root, 7)
insertNode(root, 9)

通过以上代码，可以将节点依次插入到二叉排序树中。插入节点的时间复杂度为 O(log n)，其中 n 是二叉排序树的节点数目。