python版本树的遍历——递归与非递归实现

发表于 | 分类于 ， | 阅读次数:

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# ------ 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

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# ------ 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

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# ------ 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

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# ------ 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/