如何在Python中遍历二叉搜索树（非递归）

Question

到目前为止，我有了

def tree_iterate():
parent, current = None, self.root
lst = []
while current is not None: 
 if current.left not None:
  lst.append(current.item) 
  parent, current = current, current.left
 if current.right not None:
  lst.append(current.item)
  parent, current = current, current.right

（抱歉，格式有点乱，我刚开始学这个）

我不太确定在当前节点有左子树和右子树的情况下，如何不使用递归来遍历树的两边。我的主要目标是得到这个二叉搜索树（BST）中所有节点的列表。

Answer 1

要想逐个获取二叉搜索树（BST）中的所有节点，可以使用广度优先搜索（BFS）的方法。不过要注意，这样得到的节点顺序并不是从小到大的排序：

queue = [root]
result = []
while queue:
    l = queue.pop(0)
    result.append(l)

    if l.left != None:
        queue.append(l.left)
    if l.right!= None:
        queue.append(l.right)

如果你想要节点按照从小到大的顺序排列，就需要用栈来模拟中序遍历：

result = []
stack = [root]
while stack:
    stack[-1].visited = True
    if stack[-1].left != None and not stack[-1].left.visited:
        stack.append(stack[-1].left)
    else:
        node = stack.pop()
        result.append(node)
        if stack[-1].right != None:
            stack.append(stack[-1].right)