Python的中序遍历非递归算法

下面是Python中的非递归中序遍历算法实现：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def inorder_traversal(root):
    if root is None:
        return []

    stack = []
    result = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.value)
        current = current.right

    return result

在这个实现中，我们使用一个栈来存储遍历的节点。首先，我们初始化一个空栈、一个空结果列表和一个指向根节点的指针。然后，我们进入一个循环，只要当前节点不为空或者栈不为空，就进行以下操作：

1. 将当前节点及其所有左子节点依次入栈，直到当前节点为空。

2. 弹出栈顶元素并将其值添加到结果列表中。

3. 将当前指针指向弹出节点的右子节点。

重复这个过程，直到遍历完所有节点。最后，返回结果列表，即为中序遍历的结果。

你可以使用以下代码创建一个二叉树并调用中序遍历函数进行测试：

# 创建二叉树
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# 调用中序遍历函数
result = inorder_traversal(root)
print(result)  # 输出: [4, 2, 5, 1, 3]

这将输出中序遍历结果 [4, 2, 5, 1, 3]。