二叉树迭代中序遍历

Question

我正在尝试实现二叉树的迭代中序遍历。

node.py:

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

inorder_traversal.py:

from node import Node

def in_order(root):
    stack = nodes = []
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            current = stack.pop()
            nodes.append(current.node)
            root = current.right
    return nodes


def main():
    '''
    Construct the below binary tree:

            15
           /  \
          /    \
         /      \
        10      20
       /  \    /  \
      8   12  16  25

    '''
    root = Node(15)
    root.left  = Node(10)
    root.right = Node(20)
    root.left.left  = Node(8)
    root.left.right = Node(12)
    root.right.left  = Node(16)
    root.right.right = Node(25)

    print(in_order(root))

if __name__ == '__main__':
    main()

我得到：AttributeError：'int'对象没有属性'node'。

我该如何解决这个错误？

Answer 1

stack = nodes = [] 创建对同一列表对象的两个引用。当您执行 stack.append(root) 或 nodes.append(current.node) 时，这会同时影响 stack 和 nodes，因为它们是相同的。您想要的是 2 个不同的对象：

stack = []
nodes = []

然后你会得到这个输出：[8, 10, 12, 15, 16, 20, 25]

Answer 2

节点变量的值在您的代码中被初始化为一个 Int（例如 Node(5)）并且您的 in_order 方法将该值压入堆栈，稍后将其弹出并尝试访问其节点变量，这将导致错误。

这是一个没有该错误并使用递归进行顺序遍历的实现（可以更简单地遵循）。

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

def in_order(node):
    nodes = []
    if node.left:
      nodes.extend(in_order(node.left))
    nodes.append(node.value)
    if node.right:
      nodes.extend(in_order(node.right))
    return nodes

二叉树迭代中序遍历

Binary Tree Iterative Inorder Traversal

python

algorithm

binary-tree

tree-traversal