为什么在Python运行中不递归遍历中序树会无穷大？

Question

我试图在不使用递归的情况下对二叉树进行中序树遍历，但似乎 while 循环无限地保持运行。任何帮助将不胜感激。

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


def inOrder(root):
    s = []
    while s is not None or root is not None:
        if root is not None:
            s.append(root.left)
            if root.left:
                root = root.left
        else:
            root = s.pop()
            print(root.data)
            if root.right:
                root = root.right


if __name__=='__main__':

    root = Node(5)
    root.left = Node(3)
    root.left.right = Node(2)
    root.left.left = Node(4)
    root.right = Node(10)
    root.right.left = Node(9)
    root.right.right = Node(20)

#            5 
#          /   \ 
#         3     10 
#       /  \   /  \
#      4    2 9    20

    inOrder(root)

Answer 1

中序遍历检查如下代码：

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


def inOrder(root):
    s = []
    s.append(root)
    while len(s) > 0: # Check if stack is not empty
        if root.left: #Case 1: Traverse left if there is an element left of the current root
            s.append(root.left)
            root = root.left
        else:
            root = s.pop() #Case 2: If there is no element on the left, print the current root
            print(root.data)
            if root.right: #Case 3: If there is an element on the right, traverse right of the current root
                s.append(root.right)
                root = root.right


if __name__=='__main__':

    root = Node(5)
    root.left = Node(3)
    root.left.right = Node(2)
    root.left.left = Node(4)
    root.right = Node(10)
    root.right.left = Node(9)
    root.right.right = Node(20)
    inOrder(root)

Answer 2

你总是s初始化一个空列表，永远不会是None。您想要检查是否 not s，而不是是否 s is not None.

Answer 3

你的想法是对的，但问题是

s is not None

与

不一样

s!=[]

你的 s 是一个始终存在的堆栈，你实际上想检查你的堆栈是否为空。

为什么在Python运行中不递归遍历中序树会无穷大？

Why is inorder tree traversal without recursion in Python running infinitely?

python

python-3.x

binary-tree

tree-traversal

inorder