# https://blog.csdn.net/yuesoda/article/details/89925738
# 树
class Node:
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right
# 树深度
def max_depth(tree):
    if not tree:
        return 0
    return max(max_depth(tree.left), max_depth(tree.right))+1
# 前序遍历
def pre_order(tree):
    if not tree:
        return
    print(tree.root, end=' ')
    pre_order(tree.left)
    pre_order(tree.right)
# 中序遍历
def mid_order(tree):
    if not tree:
        return
    mid_order(tree.left)
    print(tree.root, end=' ')
    mid_order(tree.right)
# 后序遍历
def post_order(tree):
    if not tree:
        return
    post_order(tree.left)
    post_order(tree.right)
    print(tree.root, end=' ')
# 层次遍历
def bfs(tree):
    if not tree:
        return 
    queue = []  # 队列先进先出
    queue.append(tree)
    while queue:
        cur_node = queue.pop(0)
        print(cur_node.root, end=' ')
        if cur_node.left is not None:
            queue.append(cur_node.left)
        if cur_node.right is not None:
            queue.append(cur_node.right)
# 深度遍历
def dfs(tree):
    if not tree:
        return 
    print(tree.root, end=' ')
    dfs(tree.left)
    dfs(tree.right)
# 深度遍历
def dfs_stack(tree):
    if not tree:
        return
    stack = []
    stack.append(tree)
    while stack:
        cur_node = stack.pop()
        print(cur_node.root, end=' ')
        if cur_node.right is not None:
            stack.append(cur_node.right)
        if cur_node.left is not None:
            stack.append(cur_node.left)
# 中序遍历
def mid_order_stack(tree):
    stack=[]
    while stack or tree:
        while tree:
            stack.append(tree)
            tree=tree.left
        tree=stack.pop()
        print(tree.root, end=' ')
        tree=tree.right
# 后序遍历
def post_order_stack(tree):
    if not tree:
        return
    stack = []
    stack.append(tree)
    res = []
    while stack:
        cur_node = stack.pop()
        if cur_node.left is not None:
            stack.append(cur_node.left)
        if cur_node.right is not None:
            stack.append(cur_node.right)
        res.append(cur_node.root)
    for i in res[::-1]:
        print(i, end=' ')


tree =  Node(5, Node(3,Node(2),Node(4)), Node(7,Node(6)))
print('deepth of the tree: \n', max_depth(tree))

print('pre_order: ')
pre_order(tree)

print('\nmid_order: ')
mid_order(tree)

print('\nmid_order_stack: ')
mid_order_stack(tree)

print('\npost_order: ')
post_order(tree)

print('\npost_order_stack: ')
post_order_stack(tree)


print('\nlevel_order: ')
bfs(tree)


print('\ndeep_order: ')
dfs(tree)


print('\ndeep_order: ')
dfs_stack(tree)