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


def PreOrderTraverse(root):
    """先序遍历"""
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            # 一入栈便获取当前节点值
            print(root.value, end=' ')
            root = root.left
        # 该节点不存在左节点时,该节点出栈,搜索该节点右节点
        root = stack.pop()
        root = root.right


def INOrderTraverse(root):
    """中序遍历"""
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        # 没有左孩子便获取当前节点值
        root = stack.pop()
        print(root.value, end=' ')
        root = root.right


def PostOrderTraverse(root):
    """后序遍历"""
    stack1 = [root]
    stack2 = []
    while stack1:
        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().value, end=' ')


def levelOrderTraverse(root):
    """层序遍历"""
    stack = [root]
    while stack:
        node = stack.pop(0)
        print(node.value, end=' ')
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)


def routeTraverse(root):
    """路径遍历"""
    stack = [(root, root.value)]
    while stack:
        node, path = stack.pop()
        if not node.left and not node.right:
            print(path)
        if node.left:
            stack.append((node.left, path + ' ' + node.left.value))
        if node.right:
            stack.append((node.right, path + ' ' + node.right.value))


if __name__ == "__main__":
    node1 = TreeNode('1')
    node2 = TreeNode('2')
    node3 = TreeNode('3')
    node4 = TreeNode('4')
    node5 = TreeNode('5')
    node6 = TreeNode('6')
    node7 = TreeNode('7')
    node8 = TreeNode('8')
    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5
    node3.left = node6
    node3.right = node7
    node6.right = node8

    PreOrderTraverse(node1)
    INOrderTraverse(node1)
    PostOrderTraverse(node1)
    levelOrderTraverse(node1)
    routeTraverse(node1)