python은 두 갈래 트리의 앞뒤 순서를 차원 순서대로 반복합니다. 귀속과 비귀속

앞의 순서가 두루 미치다.

# ------ coding:utf-8 -------
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def pre_order_recursive(root_node):
    if not root_node:
        return
    print root_node.val
    pre_order_recursive(root_node.left)
    pre_order_recursive(root_node.right)

def pre_order_non_recursive(root_node):
    if not root_node:
        return
    node_stack = []
    node = root_node
    while node_stack or node:
        #  ， 
        while node:
            print node.val
            node_stack.append(node)
            node = node.left
        #   while   node  ， 
        node = node_stack.pop()
        #  
        node = node.right

중순으로 두루 다니다.

# ------ coding:utf-8 -------
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def mid_order_recursive(root_node):
    if not root_node:
        return
    mid_order_recursive(root_node.left)
    print root_node.val
    mid_order_recursive(root_node.right)

def mid_order_non_recursive(root_node):
    if not root_node:
        return
    node_stack = []
    node = root_node
    while node_stack or node:
        #  ， 
        while node:
            node_stack.append(node)
            node = node.left
        #   while   node  ， 
        node = node_stack.pop()
        print node.val
        #  
        node = node.right

후순이 두루 다니다

# ------ coding:utf-8 -------
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def post_order_recursive(root_node):
    if not root_node:
        return
    post_order_recursive(root_node.left)
    post_order_recursive(root_node.right)
    print root_node.val


def post_order_non_recursive(root_node):
    if not root_node:
        return
    stack1 = [root_node]
    stack2 = []
    while stack1:
        #   while  ，  stack2  
        node = stack1.pop()
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
        stack2.append(node)
    while stack2:
        print stack2.pop().val

차례차례

# ------ coding:utf-8 -------
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def level_order(root_node):
    if not root_node:
        return
    node_queue = [root_node]
    while node_stack:
        # python list pop ， ， pop ， 
        node = node_queue.pop(0) 
        print node.val
        if node.left:
            node_queue.append(node.left)
        if node.right:
            node_queue.append(node.right)

Reference

https://blog.yangx.site/2016/07/22/Python-binary-tree-traverse/