二叉树迭代式中序遍历返回含None结果的问题求助

我实现了一个用于创建二叉树的BinaryTree类，代码如下：

class BinaryTree:

    def __init__(self):
        self._root = None
        self._left = None
        self._right = None

    def root(self):
        return self._root

    def left(self):
        return self._left

    def right(self):
        return self._right

    def isEmpty(self):
        return self._root is None

    def insert(self, element):
        if self.isEmpty():
            self._root = element
            self._left = BinaryTree()
            self._right = BinaryTree()
        elif element <= self._root:
            self._left.insert(element)
        elif element > self._root:
            self._right.insert(element)

    def inOrder(self):
        if self.isEmpty():
            return []
        l = self._left.inOrder()
        l.append(self._root)
        l += self._right.inOrder()
        return l

    def preOrder(self):
        if self.isEmpty():
            return []
        l = [self._root]
        l += self._left.preOrder()
        l += self._right.preOrder()
        return l

    def inOrder_iterative(self):
        stack = []
        res = []
        aux = self

        while aux or stack:
           
            while aux:
                stack.append(aux)
                aux = aux._left

            aux = stack.pop()
            res.append(aux._root)
            aux = aux._right

        return res

当我按顺序插入5、3、4、2、7、6、8构建二叉树后，调用迭代式中序遍历方法inOrder_iterative()得到的结果为：
[None, 2, None, 3, None, 4, None, 5, None, 6, None, 7, None, 8, None]
我期望得到的输出是：
[2, 3, 4, 5, 6, 7, 8]

补充的测试代码如下：

tree=BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(4)
tree.insert(2)
tree.insert(7)
tree.insert(6)
tree.insert(8)
print('The binary tree is: ')
print('inOrder recursive', tree.inOrder())
print('inOrden iterative', tree.inOrder_iterative())

问题原因 #

你的迭代遍历方法没有像递归版本那样判断节点是否为空（isEmpty()），直接把所有节点的_root值加入结果列表，包括那些空节点（_root为None的BinaryTree实例）。递归版本中，遇到空节点会返回空列表，不会添加任何元素，但迭代版本里，空节点被压入栈后，弹出时会把None加入结果。

修复方法 #

修改inOrder_iterative()方法，在遍历过程中只处理非空节点：

修正后的代码 #

def inOrder_iterative(self):
    stack = []
    res = []
    aux = self

    while aux or stack:
        # 仅遍历非空的左子树，避免空节点入栈
        while not aux.isEmpty():
            stack.append(aux)
            aux = aux._left

        aux = stack.pop()
        res.append(aux._root)
        # 切换到右子树，下一轮循环会自动判断是否为空
        aux = aux._right
    return res

解释 #

修正后的代码在遍历左子树时，通过not aux.isEmpty()过滤掉空节点，确保只有有效节点被压入栈。弹出节点时，栈中都是非空节点，直接将_root加入结果即可。切换到右子树后，下一轮循环会再次判断右子树是否为空，避免空节点被处理，最终得到和递归版本一致的结果：[2, 3, 4, 5, 6, 7, 8]。

内容的提问来源于stack exchange，提问作者DannyJ108